繰り返しベース、パターンベースのデータ圧縮アルゴリズム

Question

は、私は次の文字列があるとします。

ABCADCADCADABC 

私は繰り返しのサブストリングを見つけることによって、それを圧縮します。 最適な圧縮を行うアルゴリズムとは何ですか？上記の例では、それは比較のために

AB*1 CAD*3 ABC*1 

を返す必要があります

、貪欲アルゴリズムは、あなたが見てみることができ、高速かつ簡単、高圧縮率を好むかどうかに応じて

ABC*1 ADC*2 AD*1 ABC*1 

Answer 1

を返すことがありますLempel-Ziv-Welch (LZW)またはLempel-Ziv-Markov chain (LZMA)アルゴリズムに変換します。彼らは両方とも繰り返し文字列の辞書を保持します。

Answer 2

ベターはまだだろう：

（N、D）マッチの長さと距離戻った

ABCAD(6,3)(3,11) 

。したがって、（6,3）は、3バイトから始まる6バイトをコピーします。それは少し奇妙に聞こえるかもしれませんが、3バイトが入るまでに、必要とする次の3バイトがコピーされています。したがってCADCADが追加されます。 （3,11）により、ABCが追加されます。

これはLZ77圧縮と呼ばれます。これは、圧縮された圧縮データ形式を使用して、zip、gzip、およびzlibによって実装されます。そのフォーマットは、以前の文字列一致を参照するだけでなく、長さと距離だけでなく、リテラル（例：ABCAD）のハフマン圧縮も使用します。

Answer 3

実際には関係ないかもしれませんが、特定の質問については動的プログラミングソリューションが必要です。最初の文字から始まる長さ1,2,3 ... n-1の文字列を圧縮する最適な方法を計算した場合、長さnの文字列を最初の文字から圧縮する最適な方法を計算することができます。各可能性kの最後のk個の文字を見て、それらが単純な文字列の倍数を形成するかどうかを調べる。そうであれば、最初のn-k文字を圧縮し、最後のk文字を複数の文字列で表現するコストを計算します。

あなたの例では、ABCがそれ自身の倍数であることに気づくことで終わります。これをABC * 1として表現すると、AB CADの最初の11文字* 3を生成するAB * 1 CAD * 3 ABC * 1

Answer 4

これは接尾辞配列/木の仕事のように聞こえる！あなたが繰り返しパターンを把握するために、あなたの文字列の上に構築された接尾辞配列を使用することができます

http://en.wikipedia.org/wiki/Suffix_array

。たとえば、以下のようにあなたの例に接尾辞配列を作ることができます（$は常に各文字の後に来るので、$を各文字の前に来るように並べ替えることができます）。

 
ABCADCADCADABC$ 
ABC$ 
ADABC$ 
ADCADABC$ 
ADCADCADABC$ 
BCADCADCADABC$ 
BC$ 
CADABC$ 
CADCADABC$ 
CADCADCADABC$ 
C$ 
DABC$ 
DCADABC$ 
DCADCADABC$ 
$ 

これより、文字列の一般的なパターンをより簡単に確認できます。このサフィックス配列表現の情報を使用すると、CADがローカルエリアで3倍繰り返されていることがわかります。これを圧縮の選択肢として使用する可能性があります。 ADCやDCAなどは、文字列の圧縮が少ないため、魅力的ではありません。

http://en.wikipedia.org/wiki/Suffix_tree

接尾辞木は、同じタスクを行うためのより効率的な方法です。サフィックス配列を使用して何かをする方法を頭で囲むと、それはサフィックスツリーに行くのにあまりにも遠くはありません。実際、これはLZW 1とBWT（Bzip）2を含む一般的な圧縮アルゴリズムで使用されています。