3

ZIP などのファイル圧縮の主要な手順の 1 つは、以前にデコードされたテキストを参照ソースとして使用することです。たとえば、エンコードされたストリームは、「次の 219 の出力文字は、5161 バイト前のデコードされたストリームの文字と同じです」と言う場合があります。これにより、わずか 3 バイト程度で 219 文字を表すことができます。(ハフマン圧縮のように、ZIP にはそれ以上の機能がありますが、参照の一致について話しているだけです。)

私の質問は、文字列一致アルゴリズムの戦略が何であるかです。zlib などのソース コードを見ても、圧縮マッチング アルゴリズムの適切な説明が得られないようです。

この問題は次のように表現できます: 30K のテキスト ブロックと入力文字列が与えられた場合、入力文字列の先頭に正確に一致する 30K のテキストの中で最も長い参照を見つけます。"アルゴリズムは反復時に効率的でなければなりません。つまり、30K のテキスト ブロックは、前部からいくつかのバイトを削除し、後部に新しいバイトを追加することによって更新され、新しい一致が実行されます。

ソースコードやライブラリではなく、これを行うためのアルゴリズムの議論にもっと興味があります。(zlib には非常に優れたソースがあります!) さまざまなトレードオフを伴ういくつかのアプローチがあるのではないかと思います。

4

3 に答える 3

3

さて、あなたが問題について詳細に説明しているのに気付きましたが、RFC 1951のセクション 4 (DEFLATE 圧縮データ形式の仕様、つまり ZIP で使用される形式) で提供されている情報については触れていません。このリソースを見逃している可能性があります。

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

(彼らの推奨は特許の要因によって形成されていることに注意してください。彼らはより効果的な技術を知っていたかもしれませんが、それが誰かの特許でカバーされていないことを確信できなかったのかもしれません.着信データの 2 番目のバイト、3 番目のバイトなどで始まる 3 バイト シーケンスの一致を調べて、一致しない一致を除外することにより、最長の一致を見つけます。つまり、受信データが " ABCDEFG...」で、オフセット 100、302、および 416 で「ABC」のハッシュ一致がありますが、「BCD」の唯一のハッシュ一致はオフセット 301 です。2 つの完全に一致する重複するハッシュ一致がない限り、- - 可能性は低いです -- その場合、302 が最長一致です。)

また、オプションの「遅延マッチング」の推奨事項にも注意してください (皮肉なことに、これはより多くの作業を行います)。受信データの最初のバイトから始まる最長の一致を自動的に取得する代わりに、コンプレッサーは次のバイトから始まるさらに長い一致をチェックします。受信データが「ABCDE...」で、スライディング ウィンドウでの一致が「ABC」と「BCDE」のみの場合、「A」をリテラル バイトとしてエンコードし、「BCDE」を次のようにエンコードすることをお勧めします。試合。

于 2009-03-22T01:24:21.973 に答える
1

7-zipで使用されるLZMAアルゴリズムの詳細を見ることができます。7-zipの作成者は、zlibetalによって使用されているアルゴリズムが改善されたと主張しています。

于 2009-03-13T14:05:18.510 に答える