3

DEFLATE エンコーディングがどのように機能するかを理解するのに助けが必要です。これは LZSS アルゴリズムとハフマン コーディングの組み合わせです。

したがって、たとえば「Deflate late」をエンコードしてみましょう。Params: [検索バッファー: 8kb および先読みバッファー 4kb] さて、LZSS アルゴリズムの出力は "Deflate <5, 4>" です。次のステップでは、静的ハフマン コーディングを使用して冗長性を減らします。これが私の問題です。このペア <5, 4> をハフマンでエンコードする方法がわかりません。

【編集済】

D 000
f 001
l 010
a 011
t 100
_ 101
e 11

さて、この表によると、文字列 "Deflate " は 000 11 001 010 011 100 11 101 と書かれています。次のステップとして、ペア (5, 4) をエンコードしましょう。本「Data Compression - The Complete Reference」によると、長さ 4 の固定プレフィックス コードは 258 で、その後に距離 5 の固定プレフィックス コード (コード 4 + 1 エクストラ ビット) が続きます。

それは次のように要約できます。

長さ 4 -> 258 -> 0000010
距離 5 -> 4 + 余分なビット 1 -> 00100|0

したがって、エンコードされた文字列は [header: 1 01] 000 11 001 010 011 100 11 101 0000010 001000 [end-of-block: 0000000] のように記述されますが、ハフマン ツリーを作成すると、静的なハフマンではなくなります。右？

良い一日

4

1 に答える 1

13 
D 000
f 001
l 010
a 011
t 100
_ 101
e 11

Deflate 静的コードではありません。静的リテラル/長さコードはすべて 7、8、または 9 ビットであり、距離コードはすべて 5 ビットです。あなたは静的コードについて尋ねました。

リテラル 'Deflate ' と長さ 4、距離 5 が 16 進数で一致するため、静的な deflate 形式でエンコードされた 'Deflate late' は次のとおりです。

73 49 4d cb 49 2c 49 55 00 11 00

これは次のように分類されます (ビットは各バイトの最下位部分から最初に読み取られます)。

011 - 01 means fixed code, 1 means last block
00101110 - D
10101001 - e
01101001 - f
00111001 - l
10001001 - a
00100101 - t
10101001 - e
00001010 - space
0100000 - length 4
00100 - distance 5 or 6 depending on one extra bit
0 - extra bit -> distance 5
0000000 - end code
0 - fill bit to byte boundary
于 2013-07-01T23:24:39.013 に答える