DocumentCode
1659096
Title
A Compressed Format Index Based on the Wavelet Tree and Its Implement
Author
Yi, Zhang ; Xiao-qi, Li ; Yan, Lu ; Xiao-hui, Zhao
Author_Institution
Mil. Simulation Technol. Inst., Air Force Aviation Univ., Changchun, China
fYear
2010
Firstpage
139
Lastpage
142
Abstract
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.
Keywords
Huffman codes; data compression; indexing; text analysis; tree data structures; wavelet transforms; BWT transform; Burrows-Wheeler transform; Canonical Huffman code; compressed format index; data structure; function rank; suffix arrays; wavelet tree; Information processing; BWT transform; Huffman code; full text index; suffix arrays;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Processing (ISIP), 2010 Third International Symposium on
Conference_Location
Qingdao
Print_ISBN
978-1-4244-8627-4
Type
conf
DOI
10.1109/ISIP.2010.141
Filename
5669018
Link To Document