Compressed format index based on suffix arrays and it's implementing in bioinformatics

摘要

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.