Move To Front

Move to Front（先頭移動法、MTF）とは、再帰時間符号化法の一種で、再帰順位符号化（receny rank）法や book stack とも呼ばれる符号。実装に配列やリストを使用して、要素を先頭に移動する操作をメインとすることからこの呼称で呼ばれることが多い。

ブロックソートを行ったデータをMTF処理すると圧縮しやすいデータになることから、主にブロックソートを用いる圧縮プロセスの一部として利用されている。

動作原理は単純ながら、非定常であるため、その理論的性能の解析は困難であった。2005年に、1次マルコフ情報源の特定の状況においてのみ、エントロピーレートを達成することが明らかになっている。M. Arimura and H. Yamamoto, "Asymptotic redundancy of the MTF scheme for stationary ergodic sources," in IEEE Transactions on Information Theory, vol. 51, no. 11, pp. 3742-3752, Nov. 2005, doi: 10.1109/TIT.2005.856941.

符号化の原理

まず初期化として、符号化の対象とするデータ列をリスト状に並べる。 対象：a b a b a c a c a 次に、符号化対象とするデータ列から記号を1つ読み込む。この読み込んだ記号が以前に出現していなければそのまま出力する。同時に、出現した記号をテーブルに登録する。 出力：a テーブル：a 一度出力したことのある記号まで1と2を繰り返す。出現した記号は常にテーブルの先頭に登録する。 出力：a b テーブル：b a aは一度出力したことがあるので、以前のaがテーブルの何番目に位置するかを、整数で出力する。そして、この記号をテーブルの先頭位置に移動する。 出力：a b 2 テーブル：a b データ列のすべての記号を符号化するまでこの操作を繰り返す。 出力：a b 2 2 テーブル：b a 出力：a b 2 2 2 テーブル：a b 出力：a b 2 2 2 c テーブル：c a b 出力：a b 2 2 2 c 2 テーブル：a c b 出力：a b 2 2 2 c 2 2 テーブル：c a b 出力：a b 2 2 2 c 2 2 2 テーブル：a c b このように、MTFを施すとデータが偏るようになる。これを圧縮すると高い圧縮率が期待できる。

参考文献

関連項目 ブロックソート