摘要
实现了一种基于模拟后缀数组的索引的结构,并在实现索引功能的同时对索引结构进行有效压缩。首先,对传统的哈夫曼编码压缩小波树时出现的空白编码进行了处理,应用正则哈夫曼编码有效的去掉了空白编码;其次,通过相关函数操作在已压缩的小波树上模拟实现了后缀数组功能。理论分析和实验结果表明,这种结构具有很小的空间占用,并不影响索引结构的运行效率。
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.
出处
《情报科学》
CSSCI
北大核心
2009年第12期1834-1836,1862,共4页
Information Science
基金
吉林省教育厅科技规划项目(2007248
2008257)
