Burrows-Wheeler Transform
Burrows-Wheeler 変換 (BWT) は、テキストのすべての巡回シフトをソートして最終列を取り出し、類似した文字を集約することで、後段の圧縮に適したデータを得る変換である。
目的
テキストを圧縮しやすい形（類似文字の集約）へ書き換える可逆変換であり、bzip2 パイプラインの第一段階を担う。
メカニズム
テキストのすべての巡回シフトから行列を構築し、行をソートして、最終列を BWT 出力として取り出すとともに元の行の番号を記録する。逆変換は LF 写像とその番号によってテキストを復元する。
ユースケース
- bzip2 圧縮の前段変換
- ゲノム配列の解析
- 全文インデックスの構築