论文部分内容阅读
本文基于对一种新的ST逆变换算法的分析，实现了快速ST正向变换算法，并将两者结合实现了一个快速有限阶BWT算法。此算法实现的目的在于验证新逆ST算法的可行性及其能否保持ST正向变换相对于BWT的时间复杂度优势，同时使新的逆ST算法能够实际应用。ST是针对BWT正向变换中超线性排序时间复杂度改进的一个BWT变种。现存逆ST算法由于采用了哈希表而导致了较高的复杂度，影响了sT正向变换带来的优势。新的逆ST算法的提出使得ST正向变换相对于BWT的优势能得以保持。因此要验证新的逆ST算法的理论意义，ST正、逆变换的快速实现尤为关键。实现sT正向变换的主要难点是如何在线性的复杂度内实现正向变换中的排序操作。本文采用了一种改进的基数排序来解决此问题。为了验证新的逆ST算法的可行性，本文对所实现的快速有限阶BWT算法与无限阶BWT算法进行对比实验，在Calgary数据集上进行验证和性能分析。实验数据表明新的快速有限阶BwT算法可在保持压缩率为无限阶BWT算法的99.83﹪的同时，提高运行速度69.08﹪。显示了新的逆sT算法在高性能无损数据压缩应用中的潜力。