距離編碼（DC）BWT

Question

我正嘗試使用Huffman壓縮程序編寫BWT。在BWT我想實現距離編碼（DC）。我正在尋找一些例子，但沒有那麼多。

我發現這個例子：

http://www.cs.ucr.edu/~stelo/cpm/cpm07/move_to_front_gagie.pdf

DC開始與29頁。但由於沒有評論，所以很難理解。

也許有人實施了DC或知道理論如何在實際代碼中實現它？ :)

我明白那個首先需要寫出什麼字符的部分。但隨着距離我沒有得到它。

我發現，對於每個字符，DC在序列中找到它的下一個出現，並將其寫入S並輸出距離。如果沒有發生，則寫0。

謝謝。

Answer 1

我已經用Java編寫的實現： http://code.google.com/p/kanzi/source/browse/java/src/kanzi/function/DistanceCodec.java

你可以在代碼（完整的示例）的開頭看到的算法的解釋。 此外，看一看塊編碼器（它包括BWT + MoveToFront +零長度變換+熵編碼）： http://code.google.com/p/kanzi/source/browse/java/src/kanzi/function/BlockCodec.java

我曾嘗試使用距離編碼，而不是移至前面。與MTFT相比，DC輸出更小（更好的壓縮）。然而，在熵編碼之後，結果相反：MTFT看起來更適合於熵壓縮。