> bwt | transform | compress <
// Burrows-Wheeler Transform - 可逆な変換でテキストを再配置し圧縮を助けます
>> 特長
完全に可逆
元のテキストを正確に復元できるロスレスな変換です。
文字のクラスタリング
似た文字をまとめて並べることで、その後のエンコーダーによる圧縮効率を高めます。
bzip2 の中心技術
bzip2 系の多くの圧縮アルゴリズムで利用される基盤となる変換です。
>> 技術情報
BWT の仕組み
Burrows-Wheeler 変換は入力文字列のすべての循環シフトを生成し、それらを辞書順にソートして、ソート済み行列の最後の列と元の行のインデックスを出力します。これにより似た文字が連続して並びやすくなり、RLE や Move-to-Front、エントロピー符号化などの圧縮アルゴリズムと相性の良いデータになります。
BWT の例
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
BWT を使う理由
- テキストデータの圧縮効率を向上させる
- 完全に可逆でロスレス
- 似たコンテキストの文字列をまとめる
- bzip2 圧縮アルゴリズムの基盤となる技術
- 他の符号化処理の前段として有効な前処理
>> よくある質問
Burrows-Wheeler 変換とは何ですか？
Burrows-Wheeler 変換 (BWT) は、文字列を並べ替えて同じ記号が連続して現れるようにする可逆アルゴリズムです。1994 年に Michael Burrows と David Wheeler によって提案され、bzip2 のような圧縮ソフトで圧縮率を高めるための前処理として使われています。
なぜ BWT は圧縮に有利なのですか？
BWT は似たコンテキストで出現する文字をまとめ、出力中に同じ記号が長いランになりやすくします。こうしたランはランレングス符号化、Move-to-Front、Huffman 符号化などのエントロピー符号化と組み合わせることで非常に高い圧縮率が得られます。
EOF マーカーとは何ですか？
EOF (End Of File) マーカーは通常 '$' などの一意な記号で、すべての回転行が互いに区別できるようにし、元の行の位置を特定できるようにします。EOF マーカーがないと、一意な表現を持たない文字列が存在してしまいます。逆変換ではこのマーカーを取り除きます。
BWT 自体は圧縮アルゴリズムですか？
いいえ。BWT 自体は圧縮を行うのではなく、データを圧縮しやすい形に並べ替える変換です。実際の圧縮では Move-to-Front や RLE、Huffman 符号化などと組み合わせて bzip2 のようなスキームとして利用されます。