Burrows-Wheeler變換（BWT） - 存儲數據

Question

使用BWT後，我們需要在編碼數據中使用哪組數據？我們是否需要編碼（或導出）後綴數組？

輸入：

stackoverflow

BWT輸出：

wtavrcfkle$soo

後綴數組：

13, 2, 3, 7, 9, 4, 10, 5, 11, 8, 0, 1, 6, 12

Answer 1

後綴數組只需要計算bwt變換，變換完成後就可以丟棄。

BWT("stackoverflow")="wtavrcfkle$soo" 

UNBWT("wtavrcfkle$soo")="stackoverflow" 

您也可以恢復從轉換輸出的後綴數組，如果你喜歡:)

Answer 2

所有你需要反轉跨表單是輸出字符串（在您的示例中爲wtavrcfkle$soo）。

Answer 3

您只需要傳輸BWT輸出。

這個轉換令人驚訝的是，原始字符串可以從排列後的輸出字符串重建。

wikipedia article包含用於做這個反演的示例代碼。

請注意，正常操作模式是使用運行長度編碼在傳輸之前對BWT輸出進行編碼（或者您尚未實現任何壓縮）。

轉換的好處在於，它傾向於產生相似字符的長時間運行（如果源材料中存在結構）並且運行長度編碼運行良好。

Answer 4

要反轉BWT，只需要原始最後一個字符的索引，而不是整個後綴數組。如果你沒有這個索引，我相信選擇一個任意索引會導致原始字符串的旋轉版本。

需要注意的是，如果包括結束行的代碼（如你的例子），原來的最後一個字符是顯而易見的，因此指數並不需要單獨提供...

Answer 5

需要明確的是，後綴陣列和BWT輸出是一樣的。如果您查看示例中的後綴數組，它包含從BWT輸入（從1開始）獲取的BWT輸出中字母的索引：13 - > w，2 - > t，3 - > a等。 .. 使用後綴數組只是一種計算線性時間內BWT輸出的機制。傳輸後綴數組或BWT輸出意味着傳輸相同的信息。