BurrowsWheeler變換（BWT）的最佳分類算法

我被困在了Burrows Wheeler變換的一個問題上。這是一個大學項目，但這只是其中的一小部分。整個項目由3個不同的算法組成，用於數據壓縮。BurrowsWheeler變換（BWT）的最佳分類算法

我只是想弄清楚在Burrows Wheeler Transformation中用於後綴排序的內存和時間效率最高的排序算法是什麼？編碼需要儘可能高效。

對於較小的數組，排序實際上並不會真正影響它，但是當我們正在壓縮的文本文件變得越來越大時，使用低效排序算法消耗的時間確實會破壞時間和內存效率。

任何幫助將不勝感激，在此先感謝！

編輯

在Java中，我們代碼的方式，才意識到我從來沒有提出過。

來源

2013-04-12 nickcorin

如果沒有任何特殊屬性需要排序，快速，堆或合併有什麼問題，可選地交換到插入排序足夠小的子陣列？ – Patashu

他們沒有錯，我現在正在使用快速排序。我只是要求提供一些有關用於此特定示例的最有效算法的意見。 – nickcorin

許多實用的基於BWT的壓縮工具都基於DivSufSort和MSufSort。但它們的性能最差（O^2），因此在排序前必須對數據使用一些預處理方法。

對於理論的最佳時間/空間成本，儘量SA-是和SA-DS。

如果你想自己寫一個後綴排序算法，我建議你從快速簡單的QSufSort開始。

來源

2013-04-12 10:41:17 richselian

我建議你不要使用java來進行壓縮工具項目，它太慢了。 – richselian

其實Java不慢:-) – kensai

正如richselian所述，排序是二次的，而基於後綴數組的算法是線性的。如果你的數組很小，那沒關係，但是更大的數組會產生更好的壓縮結果。您可以在這裏找到一個完整的基於後綴數組的BWT實現：https://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java（數組最大爲16MB）。至於說「java很慢」的說法，我會恭敬地不同意。

來源

2013-12-04 06:17:42 flanglet

BurrowsWheeler變換（BWT）的最佳分類算法

回答

相關問題