スライディングウィンドウで文字列の一致を見つけるアルゴリズム

Question

ZIPのようなファイル圧縮の主なステップの1つは、以前のデコードされたテキストを参照ソースとして使用することです。例えば、符号化されたストリームは、「次の219個の出力文字は、5161バイト前の復号ストリームからの文字と同じである」と言うかもしれない。これにより、ちょうど3バイト程度の219文字を表現できます。 （ハフマン圧縮のように、ZIPにはもっと多くのことがありますが、参照整合についてはちょっと話しています）。文字列一致アルゴリズムの戦略は私の質問です。 zlibなどのソースコードを見ても、圧縮マッチングアルゴリズムの説明はよく分かりません。

問題のように記述することがあります：テキストのブロックを考えると、それの30Kを言うと、入力文字列、正確に入力文字列の先頭にマッチしたテキストの30Kで最長参照を見つけます「。アルゴリズムは効率的でなければなりません。つまり、30Kブロックのテキストは、先頭からいくつかのバイトを削除し、後ろに新しいバイトを追加して更新し、新しいマッチを実行します。

私は議論にもっと関心がありますソースコードまたはライブラリ（zlibには非常に良いソースがあります）異なるトレードオフを持ついくつかのアプローチがあると思われます。

Answer 1

7-zipで使用されているLZMA Algorithmの詳細を見ることができます。 7-zipの著者は、zlibなどが使用しているアルゴリズムを改良したと主張しています。

Answer 2

あなたはLongest Common Substring Problemの修正版についてお答えしていると思います。

Answer 3

まあ、私はあなたがこの問題についていくつかの詳細を述べているが、セクション4のRFC 1951（DEFLATE圧縮データフォーマットの仕様、つまりZIPで使用されているフォーマット）の情報は言及していないことに気付きましたあなたがこのリソースを逃した可能性があると信じてください。

基本的なアプローチは、3バイトシーケンスをキーとして使用する連鎖ハッシュテーブルです。チェーンが空でない限り、それに沿ったすべてのエントリがスキャンされ、a）誤った衝突を排除し、b）古いものを排除し、c）残っているものの中から最長一致を選ぶ。

（彼らの推奨は、特許の要因によって形作られています;彼らはより効果的な手法を知っていたかもしれませんが、それが誰かの特許の対象ではないことを確かめることはできませんでした。入ってくるデータの2番目のバイト、3番目のバイトなどで始まる3バイトシーケンスの一致を調べ、マッチしないマッチを除外することで最も長いマッチを見つけることができませんでした。受信データは "ABCDEFG ..."であり、オフセット100,302、および416で "ABC"のハッシュ一致が得られますが、 "BCD"のハッシュ一致はオフセット301になります。重複したハッシュの一致 - おそらく - 次に最も長い一致が302です。）

また、オプションで "レイジーマッチング"（これは皮肉なことにより効果があります）：入力データの最初のバイトから開始する最長マッチを自動的に取る代わりに、次のバイトから始まるさらに長いマッチをチェックします。あなたの着信データが "ABCDE ..."で、スライディングウインドウの "ABC"と "BCDE"のみが一致する場合は、 "A"をリテラルバイトとして、 "BCDE"を試合。