一种基于后缀排序快速实现Burrows-Wheeler变换的方法

近年来,Bzip2压缩算法凭借其在压缩率方面的优势,得到了越来越多的应用,Bzip2的核心算法是Burrows-Wheeler变换(BWT),BWT能有效的将数据中相同的字符聚集到一起,为进一步压缩创造条件。在硬件实现BWT时,常用的基于后缀排序的算法能有效克服BWT消耗存储资源大的问题,该文对基于后缀排序实现BWT的方法进行了详细分析,并且在此基础上提出了一种快速实现BWT的方法后缀段算法。仿真结果表明后缀段算法在处理速度上比传统的基于后缀排序的算法有很大的提高。

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

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