Move To Front
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/07/05 02:35 UTC 版)
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を施すとデータが偏るようになる。これを圧縮すると高い圧縮率が期待できる。
関連項目
「Move To Front」の例文・使い方・用例・文例
- 昨年までは、Train FirstとTop Shareと契約をしていました。
- 便利なことにNice-n-Fitの本店は隣のBlake Tower内にあり、街中にも4 つの店舗があります。
- Top Trends様のような大切なお客様を失望させてしまったことに、弁解の余地もありません。
- 現状とToBeモデルを比較して下さい。
- ‘She's younger than Tom' という文では Tom の後に動詞の is を補って解すべきだ.
- 臨床的鬱病を治療するのに用いられる三環系抗鬱薬(商品名ImavateとTofranil)
- 経口で投与される非ステロイド性の抗炎症薬(商標名Torodal)
- 危険の少ない薬物が失敗したとき、心室不整脈を治療するために使用される抗不整脈薬(商標名Tonocard)
- しばしばTodea属に含まれる若干のシダを含む
- 同レースは10月16日に始まり,東海大学のソーラーカー「Tokai Challenger」は10月20日に1位でゴールした。
- Tokai Challengerはパナソニックの太陽電池を搭載していた。
- Tokai Challengerは東海大が前回のレースで使用した車より20キロ軽かった。
- Tokai Challengerはまた,空気抵抗を減らすために車幅がより狭められた。
- トヨタ自動車は水素燃料電池で動くコンセプトカー「Toyota FCV Plus」を展示した。
- Move To Frontのページへのリンク