Loading article…
ムーブ・トゥ・フロント（MTF）変換は、データ（通常はバイトストリーム）のエントロピー符号化による圧縮技術の性能を向上させるために設計された符号化方式です。効率的に実装すれば、その速度は非常に速く、データ圧縮アルゴリズムに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は値の数 (一般的には特定の実装における定数) です。
一般的に、頻繁に使用されるシンボルはリストの先頭に配置されやすく、検索結果がより早く表示されるため、パフォーマンスが向上します。これは、先頭へ移動型の自己組織化リストの背後にある考え方でもあります。
しかし、デコードにおいては、専用のデータ構造を用いることでパフォーマンスを大幅に向上させることができる。
これは、 Pythonにおける move-to-front アルゴリズムの実装例です。
from collections.abc import Generator , Iterableclass 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 )): """ 常に「元の」辞書を送信する代わりに、 初期セットに合意する方が簡単です。 ここでは、バイトの 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 ) #エンコードされた文字yield rank# 辞書を更新します [Θ(k ) for insert ] 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 : # 辞書からそのランクの文字を削除するe = dictionary . pop ( rank ) plain_text . append ( e )# 辞書の先頭に文字を挿入しますdictionary.insert ( 0 , e )return bytes ( plain_text ) .decode ( "latin-1" ) # 元の文字列を返すiこの例では、MTFコードが入力ワード内の3つの繰り返し文字を利用していることがわかります。しかし、ここで使用されている共通辞書は、MTFコードの設計意図である「よく使われる文字を先頭に配置する」という原則に反し、あまり使われない制御コードの後に、よりよく使われるASCII印刷可能文字を配置して初期化されているため、理想的とは言えません。辞書を回転させて、よく使われる文字を先頭に配置すると、より良いエンコードが得られます。
itertoolsから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変換の重要な用途の一つは、バローズ・ウィーラー変換に基づく圧縮です。バローズ・ウィーラー変換は、テキストやその他の特定の種類のデータから局所的な周波数相関を示すシーケンスを生成するのに非常に優れています。圧縮は、最終的なエントロピー符号化ステップの前に、バローズ・ウィーラー変換の後にMTF変換を行うことで大幅に改善されます。
例えば、ハムレットの独白（生きるべきか死ぬべきか…）を圧縮したいとしましょう。このメッセージのサイズは7033ビットと計算できます。単純にMTF変換を直接適用しようとするかもしれません。結果は7807ビットのメッセージ（元のメッセージより大きい）になります。これは、英語のテキストは一般的に局所的な周波数相関が高くないためです。しかし、最初にバロウズ・ウィーラー変換を適用し、次にMTF変換を適用すると、6187ビットのメッセージが得られます。バロウズ・ウィーラー変換はメッセージのエントロピーを減少させるのではなく、MTF変換をより効果的にするためにバイトの順序を並べ替えるだけであることに注意してください。
基本的なMTF変換の問題点の1つは、出現頻度に関係なくどの文字にも同じ変更を加えるため、出現頻度の低い文字が頻繁に出現する文字をより高い値に押し上げてしまい、圧縮率が低下する可能性があることです。このため、さまざまな変更や代替案が開発されてきました。一般的な変更の1つは、ある一定のポイントを超える文字を特定の閾値までしか移動できないようにすることです。もう1つは、各文字のローカル出現頻度をカウントし、これらの値を使用して任意の時点での文字の順序を選択するアルゴリズムを作成することです。これらの変換の多くは、繰り返し文字のためにゼロを予約しています。これは、繰り返し文字がBurrows–Wheeler変換後のデータで最も頻繁に出現することが多いためです。