Burrows Wheeler Transform

bzip2 圧縮に利用されていることで有名な圧縮アルゴリズム。1994年に M.Burrows 氏と D.J.Wheeler 氏により考案されたことからこの名前がついている。別名BlockSorting法(ブロック・ソート)。略称 BWT。

BWT そのものは、入力を圧縮するアルゴリズムではない。入力を圧縮しやすい形に変換するのが BWT の役割である。例えば "abracadabra" という文字列は BWT により "rdarcaaaabb" という文字列に変換される。文字列の開始位置の数字一つさえ分かれば、この変換後の文字列からオリジナルの入力に逆変換することが可能になっている。

"rdarcaaaabb" を見ると、オリジナルではばらばらだった a や b が近い位置に固まっていることが分かる。このように、BWT を文字列に適用することで同一の記号が連続しやすい文字列へと変換することができる。同一の記号が連続する文字列は圧縮しやすい。よって変換後の文字列に先頭移動法 (MTF) や連長圧縮法 (RLE) を適用し、ハフマン符号や算術符号でエントロピー符号化することにより高い圧縮効果を得ることができる。