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.