修理

Re-Pair (再帰ペアリングの略) は、入力テキストが与えられると、直線プログラム、つまり単一の文字列 (入力テキスト) を生成する文脈自由文法を構築する文法ベースの圧縮アルゴリズムです。線形時間で圧縮を実行するために、入力のサイズの約 5 倍のメモリ量を消費します。

文法は、テキスト内で最も頻繁に出現する文字のペアを再帰的に置き換えることによって構築されます。2 回出現する文字のペアがなくなると、結果の文字列が文法の公理として使用されます。したがって、出力文法は、公理以外のすべてのルールの右側に 2 つの記号が含まれるようになります。

Re-Pairは1999年にNJ. LarssonとA. Moffat ^[1]によって初めて導入されました。

論文では、アルゴリズムとともに、線形時間と空間の複雑さで実装するために必要なデータ構造の詳細な説明が提示されています。実験では、Re-Pair は高い圧縮率を達成し、解凍のパフォーマンスも優れていることが示されました。ただし、このアルゴリズムの主な欠点はメモリ消費量で、入力サイズの約 5 倍になります。このようなメモリ使用量は線形時間で圧縮を実行するために必要ですが、このアルゴリズムは大きなファイルの圧縮には実用的ではありません。

右側の画像は、アルゴリズムが文字列を圧縮する仕組みを示しています。 ${\displaystyle w=xabcabcy123123zabc}$

最初の反復では、に 3 回出現するペアが新しいシンボル に置き換えられます。2 回目の反復では、文字列 で最も頻繁に出現するペア が新しいシンボル に置き換えられます。したがって、2 回目の反復の最後に残っている文字列は です。次の 2 回の反復では、ペアと がそれぞれシンボルとに置き換えられます。最後に、文字列 には重複するペアが含まれないため、出力文法の公理として使用されます。 ${\displaystyle ab}$${\displaystyle w}$${\displaystyle R_{1}}$${\displaystyle w=xR_{1}cR_{1}cy123123zR_{1}c}$${\displaystyle R_{1}c}$${\displaystyle R_{2}}$${\displaystyle w=xR_{2}R_{2}y123123zR_{2}}$${\displaystyle 12}$${\displaystyle R_{3}3}$${\displaystyle R_{3}}$${\displaystyle R_{4}}$${\displaystyle w=xR_{2}R_{2}yR_{4}R_{4}zR_{2}}$

線形時間計算量を達成するために、Re-Pairは次のデータ構造を必要とする。

• 入力文字列を表すシーケンス。シーケンスの位置には、入力文字列のi番目のシンボルと、シーケンス内の他の位置への 2 つの参照が含まれます。これらの参照は、次/前の位置、たとえばと を指し、同じ部分文字列が で始まり、となり、3 つの出現すべてが同じ参照によってキャプチャされます (つまり、文字列を生成する文法に変数があります)。${\displaystyle i}$${\displaystyle k}$${\displaystyle m}$${\displaystyle w[i]}$${\displaystyle w[k]}$${\displaystyle w[m]}$
• 優先キュー。キューの各要素は、シーケンス内で連続して出現するシンボルのペア (端末または以前に定義されたペア) です。ペアの優先度は、残りのシーケンス内でのペアの出現回数によって決まります。新しいペアが作成されるたびに、優先キューが更新されます。
• すでに定義されているペアを追跡するためのハッシュ テーブル。このテーブルは、新しいペアが作成または削除されるたびに更新されます。

ハッシュ テーブルと優先キューは同じ要素 (ペア) を参照するため、ハッシュ テーブル (h_next) と優先キュー (p_next と p_prev) へのポインターを持つ PAIR と呼ばれる共通データ構造によって実装できます。さらに、各 PAIR は、シーケンス内の PAIR によって表される文字列の最初の (f_pos) 出現と最後の (b_pos) 出現の先頭を指します。次の図は、このデータ構造の概要を示しています。

次の 2 つの図は、初期化後およびペアリング プロセスの 1 つのステップを適用した後のこれらのデータ構造の例を示しています (NULL へのポインターは表示されません)。

与えられた入力文字列の文法が構築されたら、効果的な圧縮を実現するために、この文法を効率的にエンコードする必要があります。文法をエンコードする最も簡単な方法の 1 つは、暗黙のエンコードです。これは、以下で説明する関数 をencodeCFG(X)、すべての公理のシンボルに対して順番に呼び出すことで構成されます。直感的には、ルールは、文法の深さ優先トラバーサルで訪問されるときにエンコードされます。ルールが初めて訪問されると、その右側が再帰的にエンコードされ、新しいコードがルールに割り当てられます。その時点から、ルールに到達するたびに、割り当てられた値が書き込まれます。

num_rules_encoded = 256 // デフォルトでは、拡張 ASCII 文字セットが文法の終端になります。   

writeSymbol (シンボルs ) { bitslen = log ( num_rules_encoded ); // 最初は 8 で、任意の拡張 ASCII 文字を記述するには、bitslenビットを使用してs をバイナリで書き込みます}  
     
        


void encodeCFG_rec (シンボルs ) { if ( sが非終端であり、シンボルsが初めて出現する場合) { take rule s → X Y ; write bit 1 ; encodeCFG_rec ( X ) ; encodeCFG_rec ( Y ) ;シンボルsに値++ num_rules_encodedを割り当てる; } else { write bit 0 ; writeSymbol (終端/割り当てられた値) } }   
               
  	     
      
    
    
         
    
      
     
  


void encodeCFG (シンボルs ) { encodeCFG_rec ( s );ビット1を書き込みます; }   
  
    

もう 1 つの可能性は、文法の規則を世代に分割することです。つまり、規則が世代 に属するのは、または の少なくとも 1 つが世代 に属し、その他がで世代 に属する場合のみです。その後、これらの世代は、世代 から順にエンコードされます。これは、 Re-Pairが最初に導入されたときに最初に提案された方法です。ただし、Re-Pair のほとんどの実装では、単純でパフォーマンスが優れているため、暗黙的なエンコード方法が使用されます。さらに、オンザフライの解凍も可能です。 ${\displaystyle X\to YZ}$${\displaystyle i}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle i-1}$${\displaystyle j}$${\displaystyle j\leq i-1}$${\displaystyle 0}$

Re-Pair にはさまざまな実装が存在します。これらの各バージョンは、実行時間の短縮、スペース消費量の削減、圧縮率の向上など、アルゴリズムの特定の側面を改善することを目的としています。

• バイトペアエンコーディング
• Sequiturアルゴリズム