RFC: 1951
Оригинал: DEFLATE Compressed Data Format Specification version 1.3
Категория: Информационный
Дата публикации:
Автор:
Перевод: Дмитрий Черкашин

RFC 1951, Страница 11 из 14

3.2.6. Компрессия с фиксированными кодами Huffman (BTYPE=01)

Коды Huffman для этих двух алфавитов предустановлены, и не представлены явно в данных. Длины кода Huffman для алфавита литерала/длины:

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

Как было описано выше, длины кода достаточно для генерации фактических кодов; коды приведены в таблице для дополнительной ясности. Значения 286-287 литерального символа/длины фактически не никогда не появятся в сжатых данных.

Коды расстояния 0-31, представляются (фиксированной-длиной) 5 битами, с возможными дополнительными битами как показано в таблице, в параграфе 3.2.5, выше. Обратите внимание, что расстояния кодированные значениями 30-31, никогда не будут встречаться в сжатых данных.

3.2.7. Сжатие с динамическими кодами Huffman (BTYPE=10)

Коды Huffman-а для этих двух алфавитов появляются в блоке непосредственно после битов заголовка и перед сжатыми данными, причем сначала идет код литерала/длины а затем код расстояния. Каждый код определен последовательностью длин кода, как описано выше в параграфе 3.2.2. Для большей компактности, коды длины сжаты, используя код Huffman. Алфавит для длин следующий:

0  - 15: Представляют длины 0 - 15
     16: Копировать предыдущую длину кода 3 - 6 раз.
             Следующие 2 бита указывают длину повторения
             (От 0 до 3..., от 3 до 6)

              Пример:   8, 16 (+2 бита 11), 16 (+2 бита 10)
			    кодируют 12 8-ми битовых длин (1+6+5)

    	17: Повторить длину кода 0 для 3 - 10 раз. (3 бита длины)
     18: Повторить длину кода 0 для 11 - 138 раз. (7 битов длины)

Длина кода 0 указывает, что соответствующий символ в алфавите литерала/длина или в алфавите расстояния не встречается в блоке, и не должен участвовать в алгоритме построения кода Huffman-а, приведенном выше. Если используется только один код расстояния, это кодируется используя один бит, (не нулевыми битами); в данном случае единственная длина единица, c одним неиспользованным кодом.

Теперь мы можем определить формат блока:

5 битов: HLIT, # кодов литерала/длины - 257 (257 - 286)
5 битов: HDIST,# кодов расстояния - 1 (1 - 32)
4 бита : HCLEN,# кодов длины - 4 (4 - 19)
(HCLEN + 4) x 3 бита: длины кода для алфавита длины, данного
   только что выше, в порядке: 16, 17, 18, 0, 8, 7, 9,
   6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

   Данные длины кодов интерпретируются как 3 битовые (0-7)
   целые числа; длина 0 обозначает что соответствующий символ
   (литеральный символ/длина или расстояния) не используется.
HLIT + 257 кодовых длин для алфавита литерала/длины,
закодированных используя код Huffman для длин

HDIST + 1 кодовых длин для алфавита расстояния,
закодированного с использованием кода Huffman-а для длины

Фактические сжатые данные блока, кодированные с использованием
кодов Huffman для литеральных символов/длины и расстояния

Символ 256 из алфавита литеральных символов/длины (конец данных),
закодированный с использованием кода Huffman-а для литерального
символа/длины

The code length repeat codes can cross from HLIT + 257 to the HDIST + 1 code lengths. In other words, all code lengths form a single sequence of HLIT + HDIST + 258 values.

2007 - 2017 © Русские переводы RFC, IETF, ISOC.