gzipのさまざまな圧縮レベルはどのように違いますか？

Question

私は、gzipの圧縮レベル（1〜9）の違いによって、エンコーディングがどのように実装されるかを理解しようとしています。

私はzlib Cのソースコードを見てきました。これは、最も長い一致文字列の検索がどれほど徹底しているかというだけではなく、より具体的な情報を探しているようです。

たとえば、レベルによってハフマンコードの割り当ての相違が生じますか？

Answer 1

あなたが観察したように、収縮した文字列がどのように収縮しているかだけでレベルが異なります。ハフマン符号化は、選択された固定数の記号（リテラルおよび長さ/距離の組）に対して行われ、「ブロック」を生成する。この数は、圧縮レベルではなくメモリレベルによって定義される。コード化されている記号が異なるため、生成されるハフマンコードは必然的に異なります。

シンボルの数が多いほど、ブロックのコード記述のコストがより多くのシンボルに広がりますが、記号が多すぎると、ハフマンコードのローカル変更への適応が妨げられる可能性があります。シンボルの統計で。テストでは、レベル9（ブロックあたり32,767シンボル）よりも優れた圧縮が行われていることが示されているため、デフォルトのメモリレベルは8です（ブロックあたり16,383シンボルになります）。ただし、あなたの走行距離は異なる場合があります。

Answer 2

私が思い出したことから、それは主に割り当てようとしているバッファのサイズに基づいています。バッファが大きければ大きいほど、圧縮することができます。サイズが約input file size × 1.2のバッファを割り当てることができれば、ほとんどの場合、ハフマンで最高の圧縮率が得られます。

その理由は、ハフマンテーブルが、このような大きなバッファを持っているときに可能な限り最良の結果を持つすべてのバイトを包含するからです。アルゴリズムがバッファ領域を使い果たすと、そのテーブルをリセットする必要があります（それにはストリームにコードが追加されています）。これは、新しいエンコーディングテーブルを最初から開始することを意味します。つまり、新しいテーブルを再設計するためにバイトを失います。 ...

リセットが有益な場合があります（つまり、ファイルの前半で値Xに設定されたバイト数が多く、後半で値Yが多いバイト数が多い場合があります）。起こります。