Канонический код Хаффмана

В информатике и теории информации канонический код Хаффмана — это особый тип кода Хаффмана с уникальными свойствами, которые позволяют его очень компактно описывать. Вместо того, чтобы явно хранить структуру кодового дерева, канонические коды Хаффмана упорядочиваются таким образом, что достаточно хранить только длины кодовых слов, что снижает накладные расходы на кодовую книгу.

Мотивация

Компрессоры данных обычно работают одним из двух способов. Либо декомпрессор может определить, какую кодовую книгу использовал компрессор, из предыдущего контекста, либо компрессор должен сообщить декомпрессору, что это за кодовая книга. Поскольку каноническую кодовую книгу Хаффмана можно хранить особенно эффективно, большинство компрессоров начинают с создания «обычной» кодовой книги Хаффмана, а затем преобразуют ее в каноническую кодовую книгу Хаффмана перед ее использованием.

Чтобы схема кодирования символов , такая как код Хаффмана, могла быть распакована, та же модель, которую алгоритм кодирования использовал для сжатия исходных данных, должна быть предоставлена ​​алгоритму декодирования, чтобы он мог использовать ее для распаковки закодированных данных. В стандартном кодировании Хаффмана эта модель принимает форму дерева кодов переменной длины, где наиболее часто встречающиеся символы расположены в верхней части структуры и представлены наименьшим количеством битов.

Однако это дерево кода приводит к двум критическим недостаткам в реализации схемы кодирования. Во-первых, каждый узел дерева должен хранить либо ссылки на свои дочерние узлы, либо символ, который он представляет. Это требует дорогого использования памяти, и если в исходных данных имеется высокая доля уникальных символов, то размер кодового дерева может составлять значительный объем общих закодированных данных. Во-вторых, обход дерева требует больших вычислительных затрат, поскольку требует, чтобы алгоритм случайным образом перескакивал через структуру в памяти по мере считывания каждого бита закодированных данных.

Канонические коды Хаффмана решают эти две проблемы, генерируя коды в четком стандартизированном формате; всем кодам заданной длины присваиваются значения последовательно. Это означает, что вместо сохранения структуры дерева кодов для декомпрессии требуются только длины кодов, что уменьшает размер закодированных данных. Кроме того, поскольку коды являются последовательными, алгоритм декодирования можно значительно упростить и сделать его более эффективным в вычислительном отношении.

Алгоритм

Обычный алгоритм кодирования Хаффмана присваивает код переменной длины каждому символу алфавита. Более часто используемым символам будет присвоен более короткий код. Например, предположим, что у нас есть следующая неканоническая кодовая книга:

A = 11
B = 0
C = 101
D = 100

Здесь букве A присвоено 2 бита , букве B — 1 бит, а букве C и D — по 3 бита. Чтобы сделать код каноническим кодом Хаффмана, коды перенумерованы. Длины битов остаются прежними, кодовая книга сортируется сначала по длине кодового слова, а затем по алфавитному значению буквы:

B = 0
A = 11
C = 101
D = 100

Каждый из существующих кодов заменяется новым такой же длины по следующему алгоритму:

• Первому . символу в списке присваивается кодовое слово той же длины, что и исходное кодовое слово символа, но все нули Часто это будет один ноль («0»).
• Каждому последующему символу присваивается следующее по порядку двоичное число, гарантируя, что следующие коды всегда будут иметь более высокое значение.
• Когда вы достигнете более длинного кодового слова, после увеличения добавьте нули до тех пор, пока длина нового кодового слова не станет равна длине старого кодового слова. Это можно рассматривать как сдвиг влево .

Следуя этим трем правилам, каноническая версия кодовой книги будет иметь следующий вид:

B = 0
A = 10
C = 110
D = 111

В виде дробного двоичного числа

Другая точка зрения на канонические кодовые слова заключается в том, что они представляют собой цифры после точки счисления (двоично-десятичной точки) в двоичном представлении определенной серии. В частности, предположим, что длины кодовых слов равны l ₁ ... l _n . Тогда каноническое кодовое слово для символа i — это первые l _i двоичных цифр после точки счисления в двоичном представлении

$\sum _{j=1}^{i-1}2^{-l_{j}}.$

Эта точка зрения особенно полезна в свете неравенства Крафта , которое гласит, что приведенная выше сумма всегда будет меньше или равна 1 (поскольку длины берутся из кода без префиксов). Это показывает, что добавление одного в приведенный выше алгоритм никогда не приводит к переполнению и создает кодовое слово, которое длиннее, чем предполагалось.

Кодирование кодовой книги

Преимущество канонического дерева Хаффмана состоит в том, что его можно закодировать меньшим количеством битов, чем произвольное дерево.

Давайте возьмем нашу оригинальную кодовую книгу Хаффмана:

A = 11
B = 0
C = 101
D = 100

Есть несколько способов закодировать это дерево Хаффмана. Например, мы могли бы записать каждый символ , а затем количество битов и код :

('A',2,11), ('B',1,0), ('C',3,101), ('D',3,100)

Поскольку мы перечисляем символы в последовательном алфавитном порядке, мы можем опустить сами символы, указав только количество битов и код :

(2,11), (1,0), (3,101), (3,100)

В нашей канонической версии мы знаем, что символы расположены в последовательном алфавитном порядке и что более поздний код всегда будет иметь более высокую ценность, чем более ранний. Единственные части, которые осталось передать, — это длина битов ( количество битов ) для каждого символа. Обратите внимание, что наше каноническое дерево Хаффмана всегда имеет более высокие значения для более длинных битовых длин и что любые символы одинаковой битовой длины ( C и D ) имеют более высокие кодовые значения для более высоких символов:

A = 10    (code value: 2 decimal, bits: 2)
B = 0     (code value: 0 decimal, bits: 1)
C = 110   (code value: 6 decimal, bits: 3)
D = 111   (code value: 7 decimal, bits: 3)

Поскольку две трети ограничений известны, только количество бит необходимо передать для каждого символа:

2, 1, 3, 3

Зная канонический алгоритм Хаффмана, можно воссоздать всю таблицу (значения символов и кодов) только на основе битовых длин. Неиспользуемые символы обычно передаются как имеющие нулевую длину в битах.

Другой эффективный способ представления кодовой книги — перечислить все символы в порядке возрастания их битовой длины и записать количество символов для каждой битовой длины. Для примера, упомянутого выше, кодировка будет такой:

(1,1,2), ('B','A','C','D')

Это означает, что первый символ B имеет длину 1, затем A имеет длину 2 и остается 3. Поскольку символы сортируются по длине в битах, мы можем эффективно восстановить кодовую книгу. Псевдокод , описывающий реконструкцию, представлен в следующем разделе.

Этот тип кодирования предпочтителен, когда сжимается лишь несколько символов алфавита. Например, предположим, что кодовая книга содержит только 4 буквы C , O , D и E , каждая длиной 2. Чтобы представить букву O с помощью предыдущего метода, нам нужно либо добавить много нулей:

0, 0, 2, 2, 2, 0, ... , 2, ...

или запишите, какие 4 буквы мы использовали. Каждый из способов делает описание длиннее, чем:

(0,4), ('C','O','D','E')

Формат обмена файлами JPEG использует этот метод кодирования, поскольку в кодовой книге будет не более 162 символов из 8-битного алфавита, имеющего размер 256.

Псевдокод

Учитывая список символов, отсортированный по битовой длине, следующий псевдокод напечатает каноническую кодовую книгу Хаффмана:

code := 0
while more symbols do
    print symbol, code
    code := (code + 1) << ((bit length of the next symbol) − (current bit length))

algorithm compute huffman code is
    input:  message ensemble (set of (message, probability)).
                  base D.
    output: code ensemble (set of (message, code)).
 
    1- sort the message ensemble by decreasing probability.
    2- N is the cardinal of the message ensemble (number of different
       messages).
    3- compute the integer $n_{0}$ such as $2\leq n_{0}\leq D$ and $(N-n_{0})/(D-1)$ is integer.
    4- select the $n_{0}$ least probable messages, and assign them each a
       digit code.
    5- substitute the selected messages by a composite message summing
       their probability, and re-order it.
    6- while there remains more than one message, do steps thru 8.
    7-    select D least probable messages, and assign them each a
          digit code.
    8-    substitute the selected messages by a composite message
          summing their probability, and re-order it.
    9- the code of each message is given by the concatenation of the
       code digits of the aggregate they've been put in.