2

ファイル圧縮プログラムを開発しています。現在、圧縮された.ZIPアーカイバーを生成するときに、他の評判の良いコンプレッサー（7zipなど）がそれを完全に理解/解凍できるように、.ZIPアーカイバー標準を実装しています。

現在、 RFC 1951に基づいて DEFLATE アルゴリズムを開発しています。LZ77
のバリアントと、RFC と完全に互換性のある固定コードを使用したハフマン コーディングがあり、Literal-Length + Distance 値で動作します。

Dynamic Huffman Coding では、現在、一部の圧縮データ (別の信頼できるコンプレッサーで圧縮) からハフマン ツリーを抽出できますが、実際のデータの解凍を開始すると、正しくない値が得られます。
おそらく私はツリーを間違った方法で読んでいます。

これらのツリーの値が圧縮データに格納される方法を誰かが正確に説明している場所を特に見つけたことがありません。

RFCで説明されているように、固定ハフマンエンコーディングと同じ方法で、エンコードされたデータは同じリテラル長値（0〜285）+距離（0〜30）に対応するリテラル/距離あたりの余分なビットに従うと仮定します。

これが固定ハフマン エンコーディングで格納される方法は、ハフマン コードがメモリの最下位ビットにコードの最上位ビットと共に格納されることです。このようにして、エンコーディング ツリーを少しずつ読み進めることができます。ハフマン コードの余分なビットは、別の方法で格納されます。

動的ハフマン符号化はそれらを同じ方法で保存しますか?

私が見逃していること、または知っておくべきことはありますか?

4

2 に答える 2

9

まず、商用利用を許可する無料の圧縮ライブラリであるzlibですでに実行されているため、実行していることを実行する必要はありません。zlibは、RFC 1951に従って、deflate圧縮とinflate decompressionの実装を提供します。また、zlibソースコードパッケージまたはlibzipにサードパーティのコントリビューションとして含まれているminizipを使用して、zlibを使用してzipファイルを処理できます。

自分でそれを行うことに熱心な場合は、zlibディストリビューションでもpuff.cを見ることができます。これは、RFC 1951に、コメントの多い作業であるという理由でdeflate形式の明確な定義を補足する目的で作成されました。デコーダーを収縮させます。

RFC 1951は、実際、フォーマットを正確に説明しています。あなたはそれを注意深く読む必要があります。puff.cは、学習プロセスを加速するのに役立つ場合があります。

非固定ハフマン符号化の正しい用語は「動的」です。「適応型」ではありません。その理由は、「適応型ハフマン」という用語は、データ内を移動するときにハフマンツリーが実際に変形する他の何か（デフレート形式では使用されない特別な手法）を指すためです。deflateが使用する動的ハフマンコーディングは、代わりにデータをブロックに分割し、そのブロック全体で一定である各ブロックの完全なハフマンコードを送信します。

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

于 2012-05-06T17:50:23.477 に答える
1

ハフマン コードの余分なビットが格納される方法について誤解されている可能性があると思います。RFC1951 は、余分なビットの表現について次のように述べています。

余分なビットは、最上位ビットが最初に格納されたマシン整数として解釈する必要があります。たとえば、ビット 1110 は値 14 を表します。

余分なビットはハフマン コードの一部であるため、同じ順序で読み取られます。とりわけ、これは、連続したハフマン コードを持つエンコードする長さと距離の値の範囲が多数あることを意味します (つまり、長さ/リテラル​​ アルファベットのコード 269 がビット文字列「1010」で終わる場合、長さ 19-22コードはそれぞれ 101000、101001、101010、101011 になります。)

于 2013-06-20T14:49:13.227 に答える