この記事は検証のために追加の引用が必要です。信頼できる情報源からの引用を追加して、この記事の改善にご協力ください。出典のない資料は異議を唱えられ、削除される場合があります。 出典を探す： 「最前列移動変換」  - ニュース ・ 新聞 ・ 書籍 ・ 学者 ・ JSTOR ( 2011年5月)(このメッセージを削除する方法と時期について学ぶ)

先頭移動（MTF）変換は、圧縮におけるエントロピー符号化技術の性能を向上させるために設計されたデータ（通常はバイトストリーム）の符号化です。効率的に実装されていれば、その利点は通常、データ圧縮アルゴリズムの追加ステップとして組み込むことを正当化するほど高速です。

このアルゴリズムは、 1980年にボリス・リャブコによって「ブックスタック」という名前で初めて発表されました。 ^{[ 1 ]}その後、1986年にJKベントレーらによって再発見されました。^{[ 2 ]}説明文にも記載されています。^{[ 3 ]}

主な考え方は、データ内の各シンボルを「最近使用されたシンボル」のスタック内のインデックスに置き換えることです。たとえば、同一シンボルの長いシーケンスは、同じ数のゼロに置き換えられますが、長期間使用されていないシンボルが出現した場合は、大きな数値に置き換えられます。したがって、最終的にデータは整数のシーケンスに変換されます。データが多くの局所的な相関を示す場合、これらの整数は小さくなる傾向があります

正確な説明をしましょう。簡単にするために、データ内のシンボルはバイトであると仮定します。各バイト値は、アルゴリズムの過程で変化するバイトリスト内のインデックスによってエンコードされます。リストは最初はバイト値（0、1、2、3、…、255）の順序になっています。したがって、最初のバイトは常にそのバイトの値によってエンコードされます。ただし、バイトをエンコードした後、その値は次のバイトに進む前にリストの先頭に移動されます。

例を挙げると、変換がどのように機能するかがわかります。バイトではなく、a～zの値をエンコードしていると想像してください。次のシーケンスを変換します。

bananaaa

慣例により、リストは最初は（abcdefghijklmnopqrstuvwxyz）です。シーケンスの最初の文字はbで、インデックス1に現れます（リストのインデックスは0から25です）。出力ストリームに1を設定します。

1

b はリストの先頭に移動し、(bacdefghijklmnopqrstuvwxyz) を生成します。次の文字は a で、インデックス 1 に現れます。そこで出力ストリームに 1 を追加します。つまり、

1,1

文字 a をリストの先頭に戻します。このように続けると、シーケンスは次のようにエンコードされていることがわかります。

1,1,13,1,1,1,0,0

この変換は可逆であることは簡単にわかります。同じリストを維持し、エンコードされたストリーム内の各インデックスをリスト内のそのインデックスの文字に置き換えることでデコードするだけです。これとエンコード方法の違いに注意してください。各値のインデックスを参照するのではなく、リスト内のインデックスを直接使用します。

つまり、(abcdefghijklmnopqrstuvwxyz)から始めます。エンコードされたブロックの「1」を取り、リスト内を検索すると「b」になります。次に「b」を先頭に移動すると、(bacdef...)になります。次に次の「1」を取り、リスト内を検索すると「a」になり、「a」を先頭に移動します…など。

実装の詳細は、特にデコードにおいてパフォーマンスにとって重要です。エンコードの場合、リンクリストを使用することで明確な利点は得られないため、リストを保存するために配列を使用することは許容されます。最悪の場合のパフォーマンスはO ( nk )です。ここで、nはエンコードされるデータの長さ、kは値の数（通常は実装によって定数）です。

頻繁に使用されるシンボルは先頭にある可能性が高く、ヒットが早くなるため、一般的なパフォーマンスは向上します。これは、Move-to-front自己組織化リストの背後 にある考え方でもあります

しかし、デコードには、特殊なデータ構造を使用することでパフォーマンスを大幅に向上させることができます。^{[例が必要]}

これは、 Pythonにおけるmove-to-frontアルゴリズムの実装例です。

from collections.abc import Generator , Iterable    

クラスMoveToFront : """     >>> mtf = MoveToFront()     >>> list(mtf.encode("Wikipedia"))     [87, 105, 107, 1, 112, 104, 104, 3, 102]     >>> mtf.decode([87, 105, 107, 1, 112, 104, 104, 3, 102])     'Wikipedia'     >>> list(mtf.encode("wikipedia"))     [119, 106, 108, 1, 113, 105, 105, 3, 103]     >>> mtf.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])     'wikipedia'     """ def __init__ ( self , common_dictionary : Iterable [ int ] = range ( 256 ) ): """        常に「元の」辞書を送信するのではなく、        初期セットで合意する方が簡単です。        ここでは、1バイトの256通りの値を使用します。        """ # イテラブルを消費して複数回使用できるようにします。self . common_dictionary = list ( common_dictionary ) 
    










         
        




        
          

    def encode ( self , plain_text : str ) -> Generator [ int ]: # 共通辞書を変更するのは賢明ではありません。コピーを作成してください。dictionary = list ( self . common_dictionary )     
        
          

        # 各文字を読み取ります。
        for  c  in  plain_text . encode ( "latin-1" ):   # 256バイトに変更します。
            # 辞書内の文字のランクを見つけます [O(k)] 
            rank  =  dictionary . index ( c )   # エンコードされた文字は
            ランクを生成します 

            # 辞書を更新する [Θ(k 
            ) for insert ] dictionary.pop ( rank ) dictionary.insert ( 0 , c )
             

    def decode ( self , compress_data : Iterable [ int ] ) -> str : """        元のテキストを復元する逆関数        """ dictionary = list ( self . common_dictionary ) plain_text = []     
        


          
          

        # エンコードされたテキストの各ランクを読み込む
        for  rank  in  compress_data : 
            # 辞書からそのランクの文字を削除する
            e  =  dictionary . pop ( rank ) 
            plain_text . append ( e )

            # 辞書の先頭に文字を挿入する
            dictionary . insert ( 0 ,  e )

        return  bytes ( plain_text ) . decode ( "latin-1" )   # 元の文字列を返す

iこの例では、MTFコードが入力単語内の3つの繰り返し「'」を利用していることがわかります。しかし、ここでの共通辞書は、よく使われる文字を先頭に置くというMTFコードの設計意図に反して、あまり使われない制御コードの後に​​、より一般的に使われるASCII印刷可能文字で初期化されているため、理想的とは言えません。辞書を回転させて、よりよく使われる文字を前の場所に配置すると、より良いエンコードが得られます。

from itertools import chain   

def block32 ( x ): return range ( x , x + 32 ) 
      

class MoveToFrontMoreCommon ( MoveToFront ): """     >>> mtf = MoveToFrontMoreCommon()     >>> list(mtf.encode("Wikipedia"))     [55, 10, 12, 1, 17, 9, 9, 3, 7]     """ def __init__ ( self ): super () . __init__ ( chain ( # ASCII ブロックをソート: block32 ( ord ( "a" ) - 1 ), # 最初に小文字、block32 ( ord ( "A" ) - 1 ), # 次に大文字、block32 ( ord ( "!" ) - 1 ), # 句読点/数字、block32 ( 0 ), # 制御コード、range ( 128 , 256 ), # 最後に非 ASCII 文字) ) 
    




     
        
              
                    
                    
                    
                  
                   
            
        

if  __name__  ==  "__main__" : 
    import doctest doctest.testmod ()  
    

MTF変換は、頻度の局所的な相関を利用してメッセージのエントロピーを低減します[説明^が必要]実際、最近使用された文字はリストの先頭に残ります。文字の使用が局所的な相関を示す場合、出力には「0」や「1」などの小さな数字が多数含まれます。

ただし、すべてのデータがこの種の局所的な相関を示すわけではなく、一部のメッセージでは、MTF変換によって実際にエントロピーが増加する可能性があります。

MTF変換の重要な用途は、Burrows-Wheeler変換に基づく圧縮です。Burrows-Wheeler変換は、テキストやその他の特定の特殊なクラスのデータから局所的な頻度の相関を示すシーケンスを生成するのに非常に優れています。最終的なエントロピー符号化ステップの前に、Burrows-Wheeler変換に続いてMTF変換を行うことで、圧縮に大きなメリットがもたらされます。

以下のセクションは、読者にとって混乱を招いたり、不明瞭になったりする可能性があります。特に、これらの数値を導き出す方法は何ですか？以下のセクションを明確にしてください。トークページで議論される可能性があります。 （2011年2月）(このメッセージを削除する方法と時期について学ぶ)

例として、ハムレットの独白(生きるべきか死ぬべきか… ) を圧縮するとします。このメッセージのサイズは 7033 ビットと計算できます。単純に、MTF 変換を直接適用しようとすると、結果は 7807 ビット (元のサイズより大きくなります) のメッセージになります。これは、英語のテキストは一般に局所的な頻度の相関が高くないためです。ただし、最初に Burrows–Wheeler 変換を適用し、次に MTF 変換を適用すると、6187 ビットのメッセージが得られます。Burrows–Wheeler 変換ではメッセージのエントロピーは減少しないことに注意してください。MTF 変換がより効果的になるようにバイト順序が並べ替えられるだけです。

基本的なMTF変換の問題点は、頻度に関係なく、どの文字に対しても同じ変更を加えることです。そのため、まれにしか出現しない文字が頻繁に出現する文字を高い値に押し上げる可能性があり、圧縮率が低下する可能性があります。このため、さまざまな変更や代替手段が開発されてきました。一般的な変更の1つは、特定のポイントを超える文字を特定のしきい値までしか移動できないようにすることです。もう1つは、各文字のローカル頻度をカウントし、これらの値を使用して任意の時点での文字の順序を選択するアルゴリズムを作成することです。これらの変換の多くは、バロウズ・ウィーラー変換後のデータで最も一般的であることが多いため、繰り返し文字にゼロを予約しています。

• 最前面移動（MTF）という用語は、動的リンクリストの一種として、少し異なる文脈でも使用されます。MTFリストでは、各要素はアクセスされると最前面に移動されます。^{[ 4 ]}これにより、時間の経過とともに、より頻繁にアクセスされる要素へのアクセスが容易になります。

• Arturo San Emeterio Camposによる「Move to front」