哪種算法最適合Burrows-Wheeler變換？

看來很多實現BWT的壓縮器都將它與算術編碼或霍夫曼編碼一起使用。（隨意提名更多，尤其是如果他們更好的話。）哪種算法最適合Burrows-Wheeler變換？

我的第一個問題是：爲什麼字典編碼器，比如LZW或LZSS，與BWT一起使用會更糟？

我的第二個問題是：哪個是最好的全能算法？

2013-03-31 catfish_deluxe_call_me_cd

對於每種類型的數據和每臺計算機都沒有最佳算法。很大程度上取決於被壓縮的數據，計算機具有多少RAM，CPU高速緩存的大小以及其他許多因素。 –

BWT使用環境的全部尺寸，而實際執行LZ很難用較短尺寸然後從一個塊中每場比賽3
BWT利益的背景下，而正常LZ實現只發現在看比賽 - 前進窗口。

但在許多情況下，LZ並不是一個糟糕的選擇。 LZ是一種在線算法，可以在流上工作，而BWT必須在大塊上工作並且耗費大量內存。 LZ的減壓效率非常高，而BWT仍然需要至少5n的額外空間。

BWT的表現與後綴排序有關。有許多實用的後綴排序算法：MSufSort/DivSufSort/Archon/QSufSort/DeepSwallow，以及具有O（n）時間的理論最優算法：SA-IS/SA-DS。 PS /如果您正在編寫基於BWT的壓縮器，請注意編碼BWT的輸出，但不要使用BWT本身，因爲BWT轉換有許多實用的庫，並且它們大多數共享相同的接口。只需在你的項目中使用其中的一個。

來源

2013-03-31 14:29:11 richselian

很好的答案！ SACA-K的最新線性時間SA構造算法無需額外內存：https：//code.google.com/p/ge-nong/ – kvark

哪種算法最適合Burrows-Wheeler變換？

回答

相關問題