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