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

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.

  1. Подсчитываем колво кодов для каждой битовой длины кода. bl_count [N] - число кодов длины N, N >= 1.
  2. Ищется числовое значения наименьшего кода для каждой кодовой длины:
    code = 0;
    bl_count[0] = 0;
    for (bits = 1; bits <= MAX_BITS; bits++) {
        code = (code + bl_count[bits-1]) << 1;
        next_code[bits] = code;
    }
  3. Назначаются числовые значения для всех кодов, используя последовательные значения для всех кодов одной и тойже длины, с базовыми значениями, определенными на шаге 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
2007 - 2017 © Русские переводы RFC, IETF, ISOC.