一种后缀数组与滑动窗口结合的压缩算法.doc

一种后缀数组与滑动窗口结合的压缩算法 赵友桥1, 王坚1, 路松峰1, 吴志杰2 ZHAO Youqiao1, WANG Jian1, LU Songfeng1, WU Zhijie2 1.华中科技大学 计算机科学与技术学院, 武汉 430074 2.中国工程物理研究院 计算机应用研究所, 四川 绵阳 621900 1.School of Computer Science and Technology，Huazhong University of Science and Technology，Wuhan 430074，China 2. Institute of Computer Application Technology，China Academy of Engineering Physics，Mianyang，Sichuan 621900，China E-mail: lusongfeng@，Phn: +86 A Sliding Window Compression Algorithm Based on Suffix Array Abstract：suffix array-based sliding window compression algorithms are inefficient since they will rebuild suffix array for dictionary window after each sliding window. To solve the problem, after analyzing the characteristics of the future suffix array in sliding window, a new method of building a suffix array is proposed. Based the new method, suffix array just need be rebuild partly which makes the efficiency of the presented algorithm is improved, at the mean time, the compression rate of the algorithm can be maintained. The experiment results show that the effectiveness of the proposed algorithm. Key words：; Sliding Window; Suffix Array 摘 要：关键词; 滑动窗口; 后缀数组 文献标识码: A 中图分类号: TP391 引言 LZ77算法通过使用编码器或解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。压缩编码机制Ferreira首先开始关注这个问题，对滑动窗口与后缀树及后缀数组相结合的问题进行了深入研究，研究结果表明后缀数组比后缀树在滑动窗口压缩算法中更有优越性，其需要的内存要远远小于后缀树，但压缩效果稍差。他们在滑动窗口压缩算法中使用后缀数组的基本思路就是，首先对字典窗口建立后缀数组，然后再在后缀数组中查找要匹配的字串，匹配后窗口进行滑动，重新对新的字典建立后缀数组，再重复进行上述匹配，算法的效率在于后缀数组的构建。由于每次都需要完全重构后缀数组，因此算法效率没有达到最优。 在研究了滑动窗口下后缀数组的特点后，提出完全后缀数组的概念。利用完全后缀数组，我们可以在窗口滑动后，只需要部分重构后缀数组即可，进而提出一种新的效率更高的基于后缀数组的滑动窗口压缩算法。 基于后缀数组的滑动窗口压缩算法 完全后缀数组 后缀数组是字符串匹配中常用的数据结构之一。给定一个长度为n的字符串S, 称Sx(i)为S的一个后缀，其中Sx(i) = S[i…n]，即Sx(i)为起始位置为i至n的S的一个子串。 S的后缀数组SA(Suffix Array)定义为按照递增顺序排列的S的所有后缀的集合，并把排序后的位置i放入到数组SA中，因此每个后缀可以用Sx(SA[i])表示。 给定两个字符串x和y，如果对于1≤i≤k有x[i] = y[i]，但x[k+1]≠y[k+1]，则x和y的最长公共前缀L(x,y)为k。 给定一个长度为n的字符串S，S的后缀数组SA和SA的一个后缀Sx(i)，如果存在SA另一个后缀Sx(j)，使得L(Sx(i), Sx(j)) = n-i+1，则称Sx(i)为S的一个完全后缀，否则Sx(i)不是S的一个完全后缀。 称S的所有完全后缀组成的数组叫完全后缀数组，记作CSA，而所有非完全后缀组成的数组