BWT过程通常需要多长时间

Question

我知道时间复杂度为O(n^2)，但是任何人都知道它在实践中通常需要多长时间才能完成，比如现在采用的最常用的方法将20M文本文件？谢谢。

Answer 1

BWT的瓶颈通常是分拣步骤（O（n2））。但是，快速实现依赖于后缀排序，而不是线性时间内的排序（例如后缀阵列感应排序）。 此外，块的大小很重要。 最后，实现细节很重要。但是，为了给你一个球场评估，这里是我的块压缩器（BWT + MTFT + ZLT + Huffman）在带有Intel Core i7 @ 3.4 GHz的Windows 7系统上的运行（1MB块大小）。 该代码可在此处获得：http：//code.google.com/p/kanzi/

请记住，单独使用BWT步骤会更快。

编码...

文件大小：57795262 编码了7061毫秒 率：0.28658637 编码：16563336 吞吐量（KB /秒）：7993

解码...

解码需要2712 ms 解码：57795262 吞吐量（KB/s）：20811