次の文字列があるとします。
ABCADCADCADABC
繰り返し部分文字列を見つけて圧縮したい。最適な圧縮を行うアルゴリズムは何ですか?
上記の例では、返されるはずです
AB*1 CAD*3 ABC*1
比較のために、貪欲なアルゴリズムが返される可能性があります
ABC*1 ADC*2 AD*1 ABC*1
次の文字列があるとします。
ABCADCADCADABC
繰り返し部分文字列を見つけて圧縮したい。最適な圧縮を行うアルゴリズムは何ですか?
上記の例では、返されるはずです
AB*1 CAD*3 ABC*1
比較のために、貪欲なアルゴリズムが返される可能性があります
ABC*1 ADC*2 AD*1 ABC*1
これは接尾辞配列/ツリーの仕事のように聞こえます!
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などの一般的な圧縮アルゴリズムで使用されています。
高速で単純な圧縮率と高い圧縮率のどちらを好むかに応じて、Lempel-Ziv-Welch (LZW)またはLempel-Ziv-Markov chain (LZMA)アルゴリズムを調べることができます。どちらも繰り返し文字列の辞書を保持しています。
実際には関係ないかもしれませんが、あなたが尋ねる特定の質問には、動的プログラミングの解決策があります。最初の文字から始まる長さ 1、2、3...n-1 の文字列を圧縮する最適な方法を計算した場合、最初の文字から始まる長さ n の文字列を圧縮する最適な方法を計算できます。各可能性 k の最後の k 文字を見て、それらが単純な文字列の倍数を形成しているかどうかを確認します。その場合、最初の nk 文字を圧縮し、文字列の倍数を使用して最後の k 文字を表現するコストを計算します。
したがって、あなたの例では、ABC はそれ自体の倍数であり、これを ABC*1 と表現した場合、AB CAD*3 の最初の 11 文字について既に計算した答えを使用して生成できることに気付くことで終了します。 AB*1 CAD*3 ABC*1
さらに良いのは次のとおりです。
ABCAD(6,3)(3,11)
ここで、(n,d) はマッチの後方の長さと距離です。したがって、(6,3) は 3 バイトから始まる 6 バイトをコピーします。少し奇妙に聞こえるかもしれませんが、3 バイトを取得するまでに、必要な次の 3 バイトがコピーされています。というわけCADCAD
で追記です。(3,11)ABC
が追加されます。
これは LZ77 圧縮と呼ばれます。deflate 圧縮データ形式を使用して、zip、gzip、zlib で実装されているものです。ABCAD
この形式は、以前の文字列の一致を参照するだけでなく、リテラル (例: ) および長さと距離にハフマン圧縮を使用します。