DEFLATEメソッド推論

Question

LZWではなく2番目のパスでLZ77 DEFLATEがハフマンエンコーディングを使用するのはなぜですか？それらの組み合わせについて最適なものがありますか？もしそうなら、LZWの出力の性質はLZWや他の方法よりもハフマン圧縮に適していますか？

Answer 1

LZWは、LZ77と同じように、最初の「ステージ」と同じように、繰り返しのある文字列を利用しようとします。それは、その情報をエントロピーコーディングするという貧弱な仕事をします。 LZWは、より現代的なアプローチに完全に取って代わられています。 LZ77がリテラルとマッチのリストを生成すると、LZWが利用するために残されることは何もなく、その情報のためにほぼ完全に無効なエントロピーコーダを作成します。

Answer 2

Mark Adler could best answer this question.

LZ77とハフマンがどのように連携するかについての詳細は、いくつかの精査を必要としています。生データを文字列と特別な長さ、距離の組に変換したら、これらの要素をハフマンコードで表現する必要があります。

これはNOTですが、標準的な用語ではありませんが、私たちがビットを "ダイヤルトーン"で読み始めるポイントを呼び出してください。結局のところ、我々のアナロジーでは、ダイヤルトーンは、特定の電話機にマッピングされる一連の番号を指定することができる場所です。だから最初の "ダイヤルトーン"と呼んでください。そのダイヤルトーンでは、文字、長さ - 距離のペア、またはブロックの終わりの3つのうちの1つが続きます。可能性のある文字（「リテラル」）、可能な長さの範囲を示す要素（「長さ」）、および特殊なブロック終了標識はすべて、単一のアルファベットにマージされます。そのアルファベットはハフマンツリーの基礎となります。距離は、長さの直後にしか現れないので、このアルファベットに含める必要はありません。リテラルがデコードされるか、またはデコードされた長さ - 距離のペアは、別の「ダイヤルトーン」ポイントにあり、再び読み込みを開始します。もちろん、ブロックの終わりのシンボルを取得した場合は、別のブロックの先頭または圧縮データの最後に位置しています。

実際には、長さコードまたは距離コードは、基本値を表すコードであり、その後に基本値に追加する整数を形成する余分なビットが続きます。

...

Read the whole deal here.

かいつまん。 LZ77は重複排除を提供します。ハフマン符号化はビット削減をもたらす。 It's also on the wiki.