3.2.2. Use of Huffman coding in the "deflate" format
В формате "deflate" коды Huffman-а, используемые для каждого алфавита имеют два дополнительных правила:
- Все коды заданной битовой длины имеют лексикографически последовательные значения, в том же самом порядке, как и символы которые они представляют;
- Более короткие коды лексиграфичеси предшествуют более длинным кодам.
Cледуя этим правилам мы должны записать выше приведенный пример следующим образом, предполагая что порядок алфавита ABCD:
Symbol Code ------ ---- A 10 B 0 C 110 D 111
Т.е., 0 предшествует 10, которое предшествует 11x, а 110 и 111 лексиграфически следуют друг за другом.
Следуя данному правилу, мы можем определить коды Huffman-а для алфавита задавая только длины кодов для каждого символа алфавита; этого достаточно для определения фактических кодов. В нашем примере, коды полностью определены последовательностью длин кодов (2, 1, 3, 3). Ниже приведен алгоритм, который генерирует коды. Длины кодов первоначально расположены в tree[I].Len; генерируемые коды располагаются в tree[I].Code.
- Подсчитываем колво кодов для каждой битовой длины кода. bl_count [N] - число кодов длины N, N >= 1.
- Ищется числовое значения наименьшего кода для каждой кодовой длины:
code = 0; bl_count[0] = 0; for (bits = 1; bits <= MAX_BITS; bits++) { code = (code + bl_count[bits-1]) << 1; next_code[bits] = code; } - Назначаются числовые значения для всех кодов, используя последовательные значения для всех кодов одной и тойже длины, с базовыми значениями, определенными на шаге 2. Кодам, которые н никогда не используются (которые имеют битовую длину равную ноль) значение не назначается.
for (n = 0; n <= max_code; n++) { len = tree[n].Len; if (len != 0) { tree[n].Code = next_code[len]; next_code[len]++; } }
Пример:
Рассмотрим алфавит ABCDEFGH, с битовыми длинами (3, 3, 3, 3, 3, 2, 4, 4). После шага 1, мы имеем:
N bl_count[N] - ----------- 2 1 3 5 4 2
Шаг номер 2. расчитанные значения для next_code дают:
N next_code[N] - ------------ 1 0 2 0 3 2 4 14
Шаг номер 3. генерирует следующие значения для кодов:
Symbol Length Code ------ ------ ---- A 3 010 B 3 011 C 3 100 D 3 101 E 3 110 F 2 00 G 4 1110 H 4 1111