バロウズ・ウィーラー変換(BWT)

テキストのすべての巡回シフトをソートすると、同じ接尾辞を持つシフト同士が隣り合わせになります。最終列 — 各ソート済み接頭辞の直前の文字 — は、元のテキストで同じ文脈の前にあった文字を集めます。繰り返しパターンがあると多くのシフトが共通の接尾辞を持つため、同じ先行文字が最終列で何度も連続して現れます。このランこそが、RLEやmove-to-front符号化が活用するものです。この変換が可逆である理由は、先頭列F(ソート済みBWT)と最終列L(BWTそのもの)が合わせて完全な対応関係 — LF写像 — を符号化しており、この2つの列とキーだけから元のテキストを1文字ずつ復元できるからです。

BWT単体ではテキストは小さくなりません。出力は元とまったく同じ長さ・同じ文字で、順序だけが変わります。その本当の役割は可逆的な前処理として同じ文字を近くにまとめることで、後段の圧縮器 — move-to-front、ランレングス符号化、そしてハフマン符号化や算術符号化 — が働きやすくなります。要点は、BWTの出力サイズそのものではなく、その出力がどれだけ圧縮しやすくなるかにあります。

ある圧縮のアイデアが、静かにゲノミクスの土台になりました。FM索引と呼ばれる構造に組み込むと、BWTは30億文字のヒトゲノムの中から短いDNA断片を検索でき、しかもそのゲノムをわずか数ギガバイトで保持できます。BowtieやBWA（Burrows-Wheeler Aligner）といったアライナーはこれを土台にしており、1994年の圧縮の技が、今や日々何百万ものシーケンシングリードの照合を支えています。