> 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 の出力を圧縮しやすい形に変換する用途には非常に適しています。算術符号化より単純ですが、最適性はやや劣ります。
// 計算例
| # | Symbol | Index | List |
|---|---|---|---|
| 1 | b | 1 | abcdefg… |
| 2 | a | 1 | bacdefg… |
| 3 | n | 13 | abcdefg… |
| 4 | a | 1 | nabcdef… |
| 5 | n | 1 | anbcdef… |
| 6 | a | 1 | nabcdef… |
// コード例
Input banana initial list: a b c d ... z (index from 0)
Output 1 1 13 1 1 1
Encode output the index of the symbol, then move it to the front
Decode read index, output list[index], move it to the front
Use after BWT: runs of equal symbols become runs of 0s,
which RLE and Huffman/arithmetic coding then compress well (bzip2)
>> その他の質問
Q: Move-to-Frontは何に使いますか？
A: MTF自体は圧縮ではなく変換です。最近使った記号に小さな添字を与えるため、0や1が多くなり、後段のエントロピー符号化（ハフマン、算術符号）で圧縮しやすくなります。
Q: Burrows-Wheeler変換とはどう関係しますか？
A: BWTは同じ文字を連続させます。MTFはそれを小さな数、特に0の連続に変えます。BWT → MTF → RLE → ハフマンという連鎖をbzip2が使っています。
Q: MTFは可逆ですか？
A: はい。復号側も同じ初期リストから同じ移動を行えば元に戻ります。初期リスト（文字集合と順序）は両側で同一である必要があります。