A Compressed Format Index Based on the Wavelet Tree and Its Implement
Yi Zhang, Li Xiao-qi, Yan Lu, Xiaohui Zhao · 2010
In this paper, we use the function rank and the function select in wavelet tree to implement the faction of the suffix arrays. We also introduce the Canonical Huffman code to encode the Burrows-Wheeler transform (BWT) of a text T. First of all, we use the canonical Huffman code to encode wavelet tree in order to reduce the space of the wavelet tree with Huffman code, we also implement some functions of suffix arrays. Based on this data structure, we implement the suffix automaton in a space economical way.