For faster navigation, this Iframe is preloading the Wikiwand page for
Move To Front.
Move to Front(先頭移動法、MTF)とは、再帰時間符号化法の一種で、再帰順位符号化(receny rank)法や book stack とも呼ばれる符号。実装に配列やリストを使用して、要素を先頭に移動する操作をメインとすることからこの呼称で呼ばれることが多い。
ブロックソートを行ったデータをMTF処理すると圧縮しやすいデータになることから、主にブロックソートを用いる圧縮プロセスの一部として利用されている。
動作原理は単純ながら、非定常であるため、その理論的性能の解析は困難であった。2005年に、1次マルコフ情報源の特定の状況においてのみ、エントロピーレートを達成することが明らかになっている。
- まず初期化として、符号化の対象とするデータ列をリスト状に並べる。
- 対象: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を施すとデータが偏るようになる。これを圧縮すると高い圧縮率が期待できる。
{{bottomLinkPreText}}
{{bottomLinkText}}
This page is based on a Wikipedia article written by
contributors (read/edit).
Text is available under the
CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
{{current.index+1}} of {{items.length}}
Thanks for reporting this video!
This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:
An extension you use may be preventing Wikiwand articles from loading properly.
If you're using HTTPS Everywhere or you're unable to access any article on Wikiwand, please consider switching to HTTPS (https://www.wikiwand.com).
An extension you use may be preventing Wikiwand articles from loading properly.
If you are using an Ad-Blocker, it might have mistakenly blocked our content.
You will need to temporarily disable your Ad-blocker to view this page.
✕
This article was just edited, click to reload
Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}
Follow Us
Don't forget to rate us
Oh no, there's been an error
Please help us solve this error by emailing us at
support@wikiwand.com
Let us know what you've done that caused this error, what browser you're using, and whether you have any special extensions/add-ons installed.
Thank you!