> mtf | move | front <
// Move-to-Front - 圧縮を改善するための動的なリスト並べ替え
自己適応型
データ内の局所的なパターンに自動的に適応します。
局所性の活用
最近使用されたシンボルに小さなインデックスを割り当て、圧縮率を高めます。
bzip2 の一部
bzip2 圧縮パイプラインで BWT の後段として使用されます。
>> 技術情報
MTF の仕組み:
MTF は、取りうるすべてのシンボルのリストを保持します。シンボルをエンコードするときは、リスト内の現在位置を出力し、その後シンボルを先頭に移動します。こうすることで、最近使われたシンボルには小さいインデックスが割り当てられ、後続のエントロピー符号化で効率よく圧縮できます。
エンコード例:
テキスト: "banana" 初期リスト: [a,b,c,d,...] "b": インデックス 1、b→先頭 [b,a,c,d,...] "a": インデックス 1、a→先頭 [a,b,c,d,...] "n": インデックス 13、n→先頭 [n,a,b,c,...] "a": インデックス 1、a→先頭 [a,n,b,c,...] "n": インデックス 1、n→先頭 [n,a,b,c,...] "a": インデックス 1、a→先頭 [a,n,b,c,...] 出力: [1,1,13,1,1,1]
MTF を使う理由:
- >局所的な冗長性を改善
- >BWT と組み合わせて動作
- >実装がシンプル
- >可逆変換
- >パターンに自動適応
>> よくある質問
Move-to-Front エンコーディングとは何ですか？
MTF は、動的に更新されるリスト内でのインデックスとして各シンボルを符号化するデータ変換アルゴリズムです。各シンボルをエンコードした後、そのシンボルはリストの先頭に移動され、頻繁に使われるシンボルほど小さなインデックスを持つようになります。
なぜ BWT と一緒に MTF を使うのですか？
BWT は似たコンテキストをまとめ、局所的な繰り返しを作り出します。MTF はそれらの繰り返しを小さな数（0 や 1 が多い列）に変換し、その後のランレングス符号化やハフマン符号化による圧縮効率を高めます。
MTF のリストはどのように動作しますか？
リストは 256 個の可能なバイト値を順番に並べた状態から始まります。シンボルがエンコードされるたびに、その値はリストの先頭へ移動します。最近使用されたシンボルは先頭付近に留まり小さなインデックスを持ち、使用されないシンボルは徐々に大きなインデックス側へ移動します。
他の変換と比べた MTF の位置づけは？
MTF は BWT の後段で用いることを前提に設計されています。単体ではあまり効果的ではありませんが、BWT の出力を圧縮しやすい形に変換する用途には非常に適しています。算術符号化より単純ですが、最適性はやや劣ります。