基于后缀结构进行数据块优化的重复数据删除系统

为进一步提高重复数据删除系统的性能,提出基于数据分块的后缀数组SA和最长公共前缀LCP进行数据块优化的重复数据删除系统。系统首先将输入的数据流进行第一次分块,识别出相同的分块并给分块编号,创建分块编号序列的SA和LCP表,识别出最大重复队列和非重复数据块,进一步得出优化的超级块大小,然后以超级块为单元进行第二次数据分块并保存数据压缩结果。实验表明,相比于固定分块,该系统能实现给定输入流较好的压缩性和数据重构性。

一种有效的后缀树建立方法

基于自顶向下的后缀树建立思想,提出一种分步建立后缀树的方法。首先对字符串中所有后缀按照字母表顺序进行排序,然后求出有序相邻后缀之间的最长公共前缀,并根据后缀顺序和最长公共前缀建立后缀树。该方法无需使用后缀链,并且可以在线性时间建立后缀树。