基于模拟后缀数组索引结构的实现  

A Compressed Format Index Based on Suffix Arrays and Its Implement

作　　者：杨炜鸿[1] 张毅[1] 于洪梅[2] 

机构地区：[1]吉林工商学院信息工程分院,吉林长春130062 [2]吉林大学网络中心,吉林长春130011

出　　处：《情报科学》2009年第12期1834-1836,1862,共4页Information Science

基　　金：吉林省教育厅科技规划项目(2007248;2008257)

摘　　要：实现了一种基于模拟后缀数组的索引的结构,并在实现索引功能的同时对索引结构进行有效压缩。首先,对传统的哈夫曼编码压缩小波树时出现的空白编码进行了处理,应用正则哈夫曼编码有效的去掉了空白编码;其次,通过相关函数操作在已压缩的小波树上模拟实现了后缀数组功能。理论分析和实验结果表明,这种结构具有很小的空间占用,并不影响索引结构的运行效率。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.

关 键 词：全文索引 后缀数组 BW变换 哈夫曼编码 

分 类 号：G354[文化科学—情报学] TP311[自动化与计算机技术—计算机软件与理论]