0

固定ハフマン コードを使用して圧縮データを圧縮するための解凍プログラムを作成したいと考えています。仕様を形成します。

     BTYPE specifies how the data are compressed, as follows:

        00 - no compression
        01 - compressed with fixed Huffman codes
        10 - compressed with dynamic Huffman codes
        11 - reserved (error)

     The only difference between the two compressed cases is how the
     Huffman codes for the literal/length and distance alphabets are
     defined.

BTYPE=01 の場合、デコンプレッサでデータを解凍します。ハフマン コードをデコードしてから lz77 を解凍する必要があることはわかっていますが、BTYPE=01 の場合、ハフマン ツリーは圧縮データとともに保存されません。

では、ツリーを持たずにハフマンコードをデコードするにはどうすればよいですか??

編集：

したがって、ハフマン コードは次のようになります。

0 110000
1 110001
2 110010
144 110010000
145 110010001
255 111111111
256 0
257 1
258 10
259 11
260 100
279 10111
280 11000000
287 11000111

私が得られないのは、コード10に遭遇した場合、値0〜23と256〜297は同じコード であるため、距離コードの値2と値258をどのように区別できるかです

4

1 に答える 1

1

固定ハフマン コードは事前に定義されています。RFC 1951から:

3.2.6. Compression with fixed Huffman codes (BTYPE=01)

     The Huffman codes for the two alphabets are fixed, and are not
     represented explicitly in the data.  The Huffman code lengths
     for the literal/length alphabet are:

               Lit Value    Bits        Codes
               ---------    ----        -----
                 0 - 143     8          00110000 through
                                        10111111
               144 - 255     9          110010000 through
                                        111111111
               256 - 279     7          0000000 through
                                        0010111
               280 - 287     8          11000000 through
                                        11000111

     The code lengths are sufficient to generate the actual codes,
     as described above; we show the codes in the table for added
     clarity.  Literal/length values 286-287 will never actually
     occur in the compressed data, but participate in the code
     construction.

     Distance codes 0-31 are represented by (fixed-length) 5-bit
     codes, with possible additional bits as shown in the table
     shown in Paragraph 3.2.5, above.  Note that distance codes 30-
     31 will never actually occur in the compressed data.
于 2013-09-05T15:09:38.507 に答える