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

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.

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