MTF
MTFはMove-to-Front変換の略称で、BWT出力を多数の小さい整数に変換し、エントロピー符号化に有利な分布を作る。
目的
BWTの後、文字のクラスタリングをインデックスのクラスタリングに変え、頻出文字が小さいインデックスに対応するようにする。
メカニズム
シンボル表を維持し、各シンボルの現在のインデックスを出力してから先頭へ移動する。逆変換は同じ表操作で元のシンボルを復元する。
ユースケース
- bzip2パイプライン
- BWT後の後処理
- ローカリティを活かす符号化
MTFはMove-to-Front変換の略称で、BWT出力を多数の小さい整数に変換し、エントロピー符号化に有利な分布を作る。
BWTの後、文字のクラスタリングをインデックスのクラスタリングに変え、頻出文字が小さいインデックスに対応するようにする。
シンボル表を維持し、各シンボルの現在のインデックスを出力してから先頭へ移動する。逆変換は同じ表操作で元のシンボルを復元する。