algorithm - Burrows-Wheeler Transform (BWT) - 保存データ

Question

BWT を使用した後、エンコードされたデータにはどのデータ セットが必要ですか? Suffix Array をエンコード (またはエクスポート) する必要がありますか?

入力：

stackoverflow

BWT 出力:

wtavrcfkle$soo

サフィックス配列:

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

Answer 1

変換を反転するために必要なのは、出力文字列 (wtavrcfkle$soo例では) だけです。

Answer 2

BWT 出力のみを送信する必要があります。

この変換の驚くべき点は、並べ替えられた出力文字列だけから元の文字列を再構築できることです。

ウィキペディアの記事には、この逆を行うためのコード例が含まれています。

通常の操作モードでは、ランレングス コーディングを使用して、送信前に BWT 出力をエンコードします (または、圧縮を行っていません)。

変換の良いところは、(ソース マテリアルに構造がある場合) 似たような文字が長く続く傾向があるため、ランレングス コーディングがうまく機能することです。

Answer 3

明確にするために、サフィックス配列と BWT 出力は同じものです。例のサフィックス配列を見ると、BWT 入力 (1 から始まる) から取得された BWT 出力の文字のインデックスが含まれています: 13 -> w、2 -> t、3 -> a など。 .. 接尾辞配列の使用は、線形時間で BWT の出力を計算するメカニズムにすぎません。サフィックス配列または BWT 出力を送信することは、同じ情報を送信することを意味します。