Deflateでのダイナミックハフマンエンコーディング - RFC 1951

Question

私はファイル圧縮プログラムを開発中です。私たちは現在、.ZIPアーカイバスタンドアールを実装しています。そのため、圧縮された.ZIPアーカイバを生成する際に、他の評判の良いコンプレッサ（7zipなど）は完全に理解/解読できます。

我々は今、私たちは、LZ77ので、リテラル長+距離値での作業、完全およびRFCと互換性が働いて固定コードとハフマン符号化のバリアントを持ってRFC 1951
に基づいてdeflateアルゴリズムを開発しています。

ダイナミックハフマンコーディングでは、現在、いくつかの圧縮データ（別の信頼性の高いコンプレッサを使用して圧縮されたもの）からハフマンツリーを抽出することができますが、実際のデータを解凍するときは、
おそらく私は間違った方法で木を読んでいます。

私は、これらのツリーの値が圧縮されたデータに格納される方法を厳密に説明している場所は特定していません。

固定されたハフマン符号化の場合と同じ方法でRFCで説明されているように、エンコードされたデータは同じリテラル長の値（0〜285）+距離（0〜30）これは固定されたハフマン符号化に格納され

方法はハフマン符号がメモリ内少なくとも上位ビットにコードの最も上位ビットで格納されていることです。この方法で、ビットごとに読み取っているエンコードツリーをナビゲートすることができます。
ハフマンコードの余分なビットは、代わりに格納されます。

ダイナミックハフマンコーディングは同じ方法でそれらを保存しますか？

私には何かがありますか？

Answer 1

まず、商用利用が可能な無料の圧縮ライブラリであるzlibで既に完了しているため、行う必要はありません。 zlibは、RFC 1951に準拠して、deflate圧縮とinflate decompressionの実装を提供します。zlibを使用してzipファイルを処理するには、zlibソースコードパッケージのサードパーティからの貢献として含まれるminizipまたはlibzipを使用できます。

自分でやってみるつもりならば、zlibディストリビューションのpuff.cを見ることができます.puff.cはRFC 1951にdeflate形式の明確な定義を追加する目的で書かれています非常にコメントされた作業用のデフレートデコーダです。

実際、RFC 1951では正確な形式で説明しています。あなたはそれを慎重に読む必要があります。 puff.cは、学習プロセスを加速するのに役立ちます。

固定されていないハフマン符号化の正しい用語は「動的」です。 「適応的」ではない。その理由は、「適応型ハフマン」という用語は、何か他のもの、つまり収縮形式では使用されない特別な技術を指しています。データを移動するときにハフマンツリーが実際に変形するからです。動的なハフマン符号化は、何を使用するかによって、データをブロックに分割し、そのブロック全体にわたって一定である各ブロックに対して完全なハフマン符号を送信する。

はい、ダイナミックハフマンコードと余分なビットは、固定されたハフマンコードと同じ順序で格納されます。トリッキーな部分は、各ブロックのデフレートストリームヘッダーでハフマンコードがどのように送信されるかを理解することです。

Answer 2

ハフマンコードの余分なビットが格納される方法について間違えていると思います。 RFC1951は、余分なビットの表現について以下言う：

余分なビットは、最初の最上位ビットで格納された機械整数として解釈されるべきで、例えば、ビット1110は値14

を表します

余分なビットは、部分ののハフマンコードであるため、同じ順序で読み込まれます。とりわけこれは、連続するハフマンコードを有する符号化する長さと距離値の範囲が多数あることを意味する（すなわち、長さ/文字アルファベットのコード269がビットストリング "1010"で巻かれた場合、長さ19〜22 101000,10101,101010,101011のコードがあります）