how long for a BWT process usually take

I know the time complexity is of O(n^2) but anyone knows how long does it generally take in practice , 开发者_JAVA百科with the most common available method that is adopted these days, to transform a, say, 20M text file? Thanks.

The bottleneck for BWT is typically the sorting step (O(n2)). However, fast implementations rely on suffix sorting than can be achieved in linear time (such as Suffix Array Induction Sorting). Also, the size of the block matters. Finally, the implementations details matter.

But, to give you a ball park estimate, here is a run (with 1MB block size) of my block compressor (BWT+MTFT+ZLT+Huffman) on a Windows 7 system with Intel Core i7 @ 3.4 GHz. The code is available here:http://code.google.com/p/kanzi/

Keep in mind that the BWT step alone is faster.

Encoding ...

File size: 57795262 Encoding took 7061 ms Ratio: 0.28658637 Encoded: 16563336 Troughput (KB/s): 7993

Decoding ...

Decoding took 2712 ms Decoded: 57795262 Troughput (KB/s): 20811