最前面への移動変換

先頭への移動 (MTF) 変換は、圧縮のエントロピー符号化技術のパフォーマンスを向上させるために設計されたデータ(通常はバイトストリーム)の符号化です。効率的に実装されると、十分に高速であるため、その利点は通常、データ圧縮アルゴリズムに追加のステップとして含めることを正当化します。

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

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

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

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

バナナー

慣例により、リストの初期値は (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 ( n k ) です。ここで、nはエンコードされるデータの長さ、kは値の数 (通常は特定の実装の定数) です。

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

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

これはPythonでの move-to-front アルゴリズムの可能な実装です。

「""mtfwiki.py""」

 collections.abc からGeneratorをインポートし 、itertoolsからIterable をインポートし、 chain をインポートします。 
   


クラス MoveToFront : 
"""     >>> mtfwiki = MoveToFront()     >>> list(mtfwiki.encode("Wikipedia"))     [87, 105, 107, 1, 112, 104, 104, 3, 102]     >>> mtfwiki.decode([87, 105, 107, 1, 112, 104, 104, 3, 102])     'Wikipedia'     >>> list(mtfwiki.encode("wikipedia"))     [119, 106, 108     , 1, 113, 105, 105, 3, 103] >>> mtfwiki.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])     'ウィキペディア'     """    











    def  __init__ ( self ,  common_dictionary :  Iterable [ int ]  =  range ( 256 )): 
"""        常に「元の」辞書を送信するのではなく、        初期セットに同意する方が簡単です。        ここでは、バイトの 256 の可能な値を使用します。        """ self . common_dictionary = 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 )   # エンコードされた文字は
            順位を返す 

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

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


          
          

        # エンコードされたテキストの各ランクを読み取ります
        for  rank  in  compressed_data : #
            辞書plain_textからそのランクの文字を読み取ります
            append ( dictionary [ rank ])

            
            #辞書を更新するe  =  dictionary.pop ( rank ) dictionary.insert ( 0 , e )
             

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

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

def  block32 ( x ): 
    return  ( x  +  i  for  i  in  range ( 32 ))


クラス MoveToFrontMoreCommon ( MoveToFront ): 
"""     >>> mtfwiki = MoveToFrontMoreCommon()     >>> list(mtfwiki.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 文字
            ) 
        )


 __name__  ==  "__main__"の場合: 
    doctestをインポートします 

    doctest.testmod ( )の

MTF 変換は、周波数のローカル相関を利用してメッセージのエントロピーを減らします。 ^{[説明が必要]}実際、最近使用された文字はリストの先頭に残ります。文字の使用がローカル相関を示している場合、出力には「0」や「1」などの小さな数字が多数表示されます。

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

MTF 変換の重要な用途は、Burrows-Wheeler 変換に基づく圧縮です。Burrows-Wheeler 変換は、テキストやその他の特定の特殊なデータ クラスからローカル周波数相関を示すシーケンスを生成するのに非常に優れています。圧縮では、最終的なエントロピー エンコーディング ステップの前に Burrows-Wheeler 変換の後に MTF 変換を実行すると、大きな効果が得られます。

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

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

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

• 「前に移動」アルトゥーロ・サン・エメテリオ・カンポス