最前面への移動変換
 |
先頭移動（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
| 反復 | 順序 | リスト |
|---|---|---|
| bアナナア | 1 | (abcdefghijklmnopqrstuvwxyz) |
| b a nanaaa | 1,1 | （bacdefghijklmnopqrstuvwxyz） |
| バン・アナア | 1,1,13 | (abcdefghijklmnopqrstuvwxyz) |
| ナアを 禁止する | 1,1,13,1 | （nabcdefghijklmopqrstuvwxyz） |
| バナ・アンド・アー | 1,1,13,1,1 | （anbcdefghijklmopqrstuvwxyz） |
| バナン・ア・ア | 1、1、13、1、1、1 | （nabcdefghijklmopqrstuvwxyz） |
| バナナa a | 1,1,13,1,1,1,0 | （anbcdefghijklmopqrstuvwxyz） |
| バナナa | 1,1,13,1,1,1,0,0 | （anbcdefghijklmopqrstuvwxyz） |
| ファイナル | 1,1,13,1,1,1,0,0 | （anbcdefghijklmopqrstuvwxyz） |
この変換が可逆であることは容易に分かります。同じリストを維持し、エンコードされたストリーム内の各インデックスをリスト内のそのインデックスの文字に置き換えるだけでデコードできます。この方法とエンコード方法の違いに注意してください。各値のインデックスを参照するのではなく、リスト内のインデックスを直接使用します。
つまり、(abcdefghijklmnopqrstuvwxyz) から始めます。エンコードされたブロックの「1」を取り、リスト内を検索すると「b」になります。次に「b」を先頭に移動すると、(bacdef...) になります。次に次の「1」を取り、リスト内を検索すると「a」になります。「a」を先頭に移動して、… というように繰り返します。
実装
実装の詳細は、特にデコードにおいてパフォーマンスに重要です。エンコードにおいては、リンクリストの使用による明確な利点はないため、リストの格納に配列を使用することは許容されます。この場合、最悪の場合でもパフォーマンスはO ( n k ) となります。ここで、nはエンコードするデータの長さ、kは値の数（通常は実装によって定数）です。
頻繁に使用されるシンボルは先頭に位置する可能性が高く、ヒットが早く生成されるため、典型的なパフォーマンスは向上します。これは、Move-to-front 自己組織化リストの背後にある考え方でもあります。
ただし、デコードの場合は、特殊なデータ構造を使用することでパフォーマンスを大幅に向上させることができます。
パイソン
これはPythonでの前方移動アルゴリズムの可能な実装です。
collections.abcから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つの繰り返し「'」を利用していることがわかります。しかし、ここでの共通辞書は理想的とは言えません。よく使われるASCII印刷可能文字をあまり使用されない制御コードの後に配置して初期化しているため、よく使われる文字を先頭に配置するというMTFコードの設計意図に反しています。辞書を回転させて、よく使われる文字を先頭に配置すると、より良いエンコードが得られます。
itertoolsのインポートチェーンからdef block32 ( x ):範囲( 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 文字) )__name__ == "__main__"の場合: doctestをインポートします。doctest.testmod ( )実用的なデータ圧縮アルゴリズムでの使用
MTF変換は、周波数の局所的な相関を利用してメッセージのエントロピーを低減します。実際、最近使用された文字はリストの先頭に配置されます。文字の使用に局所的な相関が見られる場合、出力には「0」や「1」などの小さな数字が多数含まれることになります。
ただし、すべてのデータがこのタイプのローカル相関を示すわけではなく、一部のメッセージでは、MTF 変換によってエントロピーが実際に増加する可能性があります。
MTF変換の重要な用途の一つは、バロウズ・ホイーラー変換に基づく圧縮です。バロウズ・ホイーラー変換は、テキストやその他の特殊なデータクラスから、局所的な周波数相関を示すシーケンスを生成するのに非常に優れています。圧縮においては、最終的なエントロピー符号化ステップの前に、バロウズ・ホイーラー変換に続いてMTF変換を行うことで、大きな効果が得られます。
例
 |
例として、ハムレットの独白(生きるべきか死ぬべきか… ) を圧縮するとします。このメッセージのサイズは 7033 ビットと計算できます。単純に、MTF 変換を直接適用しようとすると、結果は 7807 ビット (元のサイズより大きくなります) のメッセージになります。これは、英語のテキストは一般に局所的な頻度の相関が高くないためです。ただし、最初に Burrows–Wheeler 変換を適用し、次に MTF 変換を適用すると、6187 ビットのメッセージが得られます。Burrows–Wheeler 変換ではメッセージのエントロピーは減少しないことに注意してください。MTF 変換がより効果的になるようにバイト順序が並べ替えられるだけです。
基本的なMTF変換の問題点は、頻度に関わらずどの文字に対しても同じ変更を加えることです。そのため、出現頻度の低い文字が出現頻度の高い文字を高い値に押し上げ、圧縮効果が低下する可能性があります。このため、様々な変更や代替手段が開発されてきました。よくある変更の1つは、ある一定の値を超える文字は特定のしきい値までしか移動できないようにすることです。もう1つの変更は、各文字の局所的な頻度をカウントし、その値を使用して任意の時点での文字の順序を選択するアルゴリズムを作成することです。これらの変換の多くは、バロウズ・ウィーラー変換後のデータで最も頻繁に出現する繰り返し文字に対して0を割り当てています。
先頭へ移動するリンクリスト
- 最前列への移動（MTF）という用語は、少し異なる文脈でも、動的リンクリストの一種として使用されます。MTFリストでは、各要素はアクセスされると最前列に移動されます。[ 4 ]これにより、時間の経過とともに、より頻繁にアクセスされる要素へのアクセスが容易になります。
参考文献
- ^リャブコ、ボリス・ヤコヴレヴィチ[ロシア語] (1980). 「ブックスタックによるデータ圧縮」（PDF） .情報伝達の問題. 16（4）：265–269 . Zbl 0466.94007 .
- ^ Bentley, Jon Louis ; Sleator, Daniel Dominic Kaplan ; Tarjan, Robert Endre ; Wei, VK (1986). 「局所適応型データ圧縮方式」 . Communications of the ACM . 29 (4): 320– 330. CiteSeerX 10.1.1.69.807 . doi : 10.1145/5684.5688 . S2CID 5854590 .
- ^ Ryabko, Boris Yakovlevich [ロシア語] ; Horspool, R. Nigel ; Cormack, Gordon Villy (1987). 「JL Bentley, DD Sleator, RE Tarjan, VK Wei による「局所適応型データ圧縮方式」へのコメント」 . Comm. ACM . 30 (9): 792– 794. doi : 10.1145/30401.315747 . S2CID 16138142 .
- ^ Rivest, Ronald Linn (1976). 「自己組織化逐次探索ヒューリスティックスについて」 Communications of the ACM . 19 (2): 63– 67. doi : 10.1145/359997.360000 . S2CID 498886 .
外部リンク
