Improving Lookup Time Complexity of Compressed Suffix Arrays using Multi-ary Wavelet Tree

다국어 초록 (Multilingual Abstract)

In a given text T of size n, we need to search for the information that we are interested. In order to support fast searching, an index must be constructed by preprocessing the text. Suffix array is a kind of index data structure. The compressed suffix array (CSA) is one of the compressed indices based on the regularity of the suffix array, and can be compressed to the k<SUP>th</SUP> order empirical entropy. In this paper we improve the lookup time complexity of the compressed suffix array by using the multi-ary wavelet tree at the cost of more space. In our implementation, the lookup time complexity of the compressed suffix array is O(log<SUP>ε/(1-ε)</SUP>σn logr σ), and the space of the compressed suffix array is ε?¹ nHk(T) + O(n log log n/log<SUP>ε</SUP>σ n) bits, where σ is the size of alphabet, Hk is the kth order empirical entropy, r is the branching factor of the multi-ary wavelet tree such that 2 ≤ r ≤ √n and r ≤ O(log<SUP>1-ε</SUP>σn), and 0 ＜ ε ＜ 1/2 is a constant.

목차 (Table of Contents)

• 1. INTRODUCTION
• 2. PRELIMINARIES
• 3. COMPRESSED SUFFIX ARRAY
• 4. COMPRESSED SUFFIX ARRAYS USING MULTI-ARY WAVELET TREES
• 5. CONCLUSION
• ACKNOWLEDGMENTS
• REFERENCES