3.2. Формат сжатого блока
3.2.1. Synopsis of prefix and Huffman coding
Прекфиксное кодирование представляет символы из априорно известного алфавита битовыми последовательностями (кодами), один код на каждый символ, в такой манере, что различные символы могут быть представлены битовыми последовательностями различной длины, но программа разбора может всегда разобрать кодированные строки однгозначно символ за символом.
Мы определям префиксный код в терминах бинарного дерева в котором два ребра исходящие из не листового узла помечаются как 0 и как 1, а листовые узлы однозначно соответствуют символам алфавита; при этом код для символа представляет собой последовательность 0-ей и 1-ек, которыми помечены ребра, ведущие от корня к листу дерева, помеченному символом алфавита. Например:
/\ Symbol Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
Программа разбора может декодировать следующий символ из кодированного входного потока, спускаясь вниз по дереву от корня, на каждом шаге выбирая ребро соответсвующее следующему входному биту.
При заданном алфавите с известной частотой символов, алгоритм Huffman-а позволяет конструировать оптимальные префикстные коды. (представляя строки как частоты символов и используя наименьшее количество бит из всех префиксных кодов для данного алфавита). Такой код называется кодом Huffman-а. (см. ссылку [1] в главе 5, для дополнительной информации относительно кодов Huffman-а.)
Отметим что для формата "deflate", коды Huffman-а для различных алгоритмов не должны превышать определенную максимальную длину. Данное ограниченние затрудняет алгоритм вычисления длины кодов из частоты появления. Детальное описание приведено в разделе 5.