Abstract:

To solve the problem of index structures compression of full-text indexes,we introduce the canonical Huffman code to encode the BWT(Burrows-Wheeler Transform) of a text. In the end, we present an efficient construction algorithm for this index, which is on-line and linear.Experimental results show that, without reducing the efficiency, the effective storage space compression is gained, which improves the effectiveness of the method.

Key words: full-text indexes, compressed, canonical Huffman code