Burrows-Wheeler変換(BWT)入門：圧縮と検索を支える基盤技術と実装の要点
エバープレイ編集部Burrows-Wheeler変換とは — 概要
Burrows-Wheeler変換（BWT）は、1994年に Michael Burrows と David Wheeler によって提案された可逆変換で、元データを“ブロック単位”で並べ替え圧縮に有利な形に変換します。重要な点は「変換自体は圧縮ではない」ことですが、文字列の局所的な文脈（似た前後関係）を集めて同じ文字の連続（ラン）を作りやすくし、その後に続く移動最前処理（Move-to-Front）やランレングス圧縮（RLE）、エントロピー符号化（ハフマン／算術符号化）などと組み合わせることで高い圧縮率を得られる点です。実運用例としては bzip2 が有名で、BWT を核にしたブロック圧縮を行っています。
基本的な考え方とアルゴリズム
BWT の標準的な定義は次のようになります。長さ n の文字列 S（末尾にユニークな終端記号 $ を付けることが多い）について、S の全ての循環回転（rotation）を列挙し、それらを辞書順にソートします。そのソート済み行列の各行の「最後の文字」を縦に取り出した列が BWT(S) です。元の文字列を識別するために元の行（元文字列が何行目に来るか）を保存するか、あるいはユニークな終端記号 $ を使うことで可逆性を担保します。
具体例（"banana$"）
元文字列: banana$ 循環回転: banana$ anana$b nana$ba ana$ban na$bana a$banan $banana 辞書順にソート: $banana -> 最後の文字: a a$banan -> 最後の文字: n ana$ban -> 最後の文字: n anana$b -> 最後の文字: b banana$ -> 最後の文字: $ na$bana -> 最後の文字: a nana$ba -> 最後の文字: a 結果（BWT）: annb$aa
逆変換（復元）の要点 — LFマッピング
BWT は単に最後の列だけあれば元に戻せます。復元の中心概念は「LFマッピング（Last-to-First mapping）」です。BWT の列を L とし、その列をソートした列を F とすると、BWTの同一行に属する L の k 回目の文字は、F における同じ文字の k 回目と対応します。これを利用して文字列を復元できます。
実装上は次の手順が基本です。
- L（BWT の列）を読み、各文字の出現順位（その文字が i 番目に出るか）を記録する（rank）。
- F（L のソート列）を理論的に構築し、各文字 c より小さい文字の総数 C[c] を求める。
- LF(i) = C[L[i]] + rank(L, i) を定義すると、LF によって行を一つ前方（元の文字列の前の文字）へたどれる。
- 終端記号 $ の位置から LF を繰り返し適用することで元の文字列を逆順に復元する。
この方法は O(n) 時間（各文字について一定回数の操作）で復元できます（ただし rank 構築などを配慮した実装詳細が必要）。
なぜ圧縮に効くのか（直感と理屈）
BWT は「文脈が似た文字列をまとめる」働きをします。ある文字の前に起こりやすい語群（右文脈）がソートによって近くに寄せられるため、L 列（最後の文字列）は同じ文字が連続して現れやすくなります。つまり同一文字のランが増える。ランが増えると RLE（ランレングス圧縮）や MTF（移動最前）と組み合わせたときに後続のエントロピー符号化が効率化します。シンプルに言えば、「似た文脈の後に来る文字は似た文字列になりやすい」ことを利用するテクニックです。
圧縮パイプラインの典型例（bzip2）
- 入力をブロックに分割（bzip2 では 100KB〜900KB の範囲で設定可能）
- 各ブロックに BWT を適用（block-sorting）
- BWT 出力に対して MTF（Move-to-Front）変換を適用
- 続けて RLE（特に短いランの符号化）を行う
- 最後にハフマン符号化等でエントロピー圧縮
この組み合わせにより、bzip2 はテキスト圧縮で良好な性能を発揮します。
応用例 — 検索とバイオインフォマティクス
BWT は圧縮だけでなく、全文検索や配列マッピングにも重要です。Ferragina と Manzini の FM-index は BWT の性質を用いた圧縮インデックスで、テキスト中のパターン検索（出現位置の列挙や頻度の計算）を圧縮空間内で効率的に行えます。これにより、大規模ゲノム配列の短い読み取り配列（リード）のマップを高速に行うツール（BWA、Bowtie など）が実現されました。これらは BWT とラベル付きランレングス、rank/select データ構造を組み合わせています。
計算量と実装上の注意
- 単純に回転を列挙してソートする方法は O(n^2 log n)（回転を比較するたびに長さ n まで比較されるため）で、実用には向きません。
- Suffix Array（接尾辞配列）を作成し、それに基づいて BWT を作る方法は O(n log n) あるいは線形（特定の SA アルゴリズム使用時）で実装できます。実際の実装では libdivsufsort のような高速実装がよく使われます。
- メモリ使用量は文字列長に比例します。巨大テキストでは外部記憶や分割（ブロック）処理、あるいは外部メモリ向け BWT 構築アルゴリズムが必要です。
- BWT 自体はブロック毎に行うため、ブロックサイズの選び方が圧縮率とメモリのトレードオフになります。大きいと高圧縮だがメモリ消費が増える、という具合です。
実装上のポイントと注意点
- 可逆性を簡潔に保つには、必ず一意の終端記号（$）を用いるか、元文字列がソート行列で何行目かを保存する（primary index）方法を採る。
- ユニコードやバイナリデータを扱う場合は終端記号の選択やバイト列扱いに注意（バイナリをそのまま扱う実装が一般的）。
- 小さなブロックでは BWT のオーバーヘッドが目立ちやすい。圧縮効果を得るには一定以上の文脈情報（ブロック長）が必要。
- ランダムアクセスを伴う用途では、単純な BWT 出力だけでは不十分で、インデックス（rank/select）やサンプリングなどの追加データ構造が必要。
派生と発展
近年は巨大・重複性の高いテキスト（ゲノムデータなど）を扱うための BWT 構築アルゴリズムや、圧縮索引の並列化・外部メモリ化、prefix-free parsing（大規模データの BWT 構築を容易にする手法）など研究が進んでいます。また、BWT を用いる索引構造（FM-index）はさらに rank/select 構造の改良や軽量化が進み、実運用での適用範囲が拡大しています。
短所・限界
- BWT 単体は圧縮ではないため、後続の処理が不可欠。
- ブロック境界での文脈切断により圧縮効率が落ちる場合がある。
- 構築に一時的なメモリが必要な場合が多く、極めて大きなデータでは外部メモリ手法が必要。
まとめ
Burrows-Wheeler変換は、データ圧縮および圧縮索引の基礎技術として極めて重要な役割を果たします。単体では圧縮効果を持ちませんが、文脈を集約してランを作る特性により、MTF・RLE・エントロピー符号化と組み合わせることで高い圧縮率を実現します。さらに BWT を核にした FM-index によって、圧縮空間上での高速検索やゲノム配列アラインメントの実装など、応用範囲は広く、理論と実装の両面で洗練が進んでいます。実務で使う際はブロックサイズ・メモリ・インデックスの有無といったトレードオフに注意してください。
参考文献
- M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm", 1994.
- Wikipedia: Burrows–Wheeler transform
- Wikipedia: FM-index（Ferragina & Manzini による解説）
- bzip2 公式サイト（bzip2 の設計と実装）
- libdivsufsort（高速接尾辞配列構築ライブラリ）
- SDSL-lite（succinct data structure ライブラリ、rank/select 実装など）
- Boucher et al., "Prefix-free parsing for building big BWTs"（大規模データ向けの BWT 構築に関する研究）
- H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform"（BWA）
投稿者プロフィール
