【作者】 李龙；

【导师】 霍红卫； 张小宁；

【作者基本信息】 西安电子科技大学 ， 计算机技术， 2014， 硕士

【摘要】 后缀数组是一种简单的、功能强大的数据结构，在全文索引设计、数据压缩算法、生物信息学等领域中都有着广泛的应用。但是，后缀数组需要庞大的空间进行存储，因此研究后缀数组的压缩算法有着重大的意义。本文提出基于小波树的后缀数组压缩算法，对后缀数组的占有空间进行了有效的压缩。在研究压缩后缀数组(CSA)的基础上，分析CSA的建立过程，对CSA进行了局部优化。结合后缀数组上的后向搜索算法以及CSA数据结构特点，探究后缀数组的压缩算法应具备的特性，据此特性提出问题转化，并验证了利用小波树压缩后缀数组的可行性。详细设计了基于小波树的后缀数组压缩算法，降低了后缀数组所需的存储空间。在两种不同树形的小波树编码方式上，分析算法能获得的压缩比。进一步提出利用二进制压缩编码对小波树进行压缩，使算法达到更高的压缩比。经过理论及实验分析得出，采用Huffman形的小波树对后缀数组进行压缩编码，进一步采用Run-Length编码对小波树进压缩，能够在合理的时间内完成后缀数组的压缩编码过程，并取得较好的压缩比。更多还原

【Abstract】 Suffix array is a simple, powerful data structure which is widely used in full-textindex designing, data compression algorithm and bioinformatics fields. Since itoccupies a huge storage space, the research of suffix array compression algorithm hasgreat significance.In this paper, an algorithm of compressing suffix array based on wavelet tree isproposed, which could effectively reduce the space occupied by suffix array. On thestudy of compressed suffix array (CSA) basically, the paper analyzes CSA·s buildingprocess, and makes a local optimization of CSA. By running the back search algorithmon suffix array and analysis of the CSA building process, we explore the characteristicsthat suffix array compression algorithm should have. Based the characteristics, aconversation of the question is made, thus the feasibility of us ing wavelet tree tocompress suffix array is verified. The algorithm of compressing suffix array based onthe wavelet tree is designed in detail, which reduces the storage space required bysuffix array. We use three different shapes wavelet tree to complete the encodingprocess, at the same time, analyze the compression ratio of the algorithm. To make thealgorithm to achieve a higher compression ratio, we use the compression encoding onbinary sequence to compress the wavelet tree.Through experimental and theoretical analysis, in the algorithm of compressingsuffix array based on wavelet tree, the Huffman-shaped wavelet tree is adopted tocompress the suffix array and the Run-Length gamma is adopted to encode the wavelettree. Thus, we can get a higher compression ratio within a reasonable time in theprocess of compressing suffix array.更多还原