BWT
BWT は Burrows-Wheeler 変換の略称であり、テキストを類似した文字が集まる形へ書き換える、bzip2 の第一段階である。
目的
同一文字を集約して RLE やエントロピー符号化の効率を高める、可逆な前処理である。
メカニズム
すべての巡回シフトのソート済み行列を構築し、最終列を取り出して、元の行番号を記録する。逆変換は、最終列と行番号から LF 写像により元のテキストを復元する。
ユースケース
- bzip2 での圧縮
- ゲノムアライメント
- 全文インデックス構築
BWT は Burrows-Wheeler 変換の略称であり、テキストを類似した文字が集まる形へ書き換える、bzip2 の第一段階である。
同一文字を集約して RLE やエントロピー符号化の効率を高める、可逆な前処理である。
すべての巡回シフトのソート済み行列を構築し、最終列を取り出して、元の行番号を記録する。逆変換は、最終列と行番号から LF 写像により元のテキストを復元する。