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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Март 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июнь 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом . Пожалуйста, помогите улучшить статью , предоставив читателю больше контекста . ( Июнь 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

Алгоритм [ править ]

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

А = 11B = 0С = 101D = 100

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

B = 0А = 11С = 101D = 100

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

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

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

B = 0А = 10С = 110D = 111

В виде дробного двоичного числа [ править ]

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

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

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

Кодирование кодовой книги [ править ]

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

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

А = 11B = 0С = 101D = 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 (значение кода: 2 десятичных, биты: 2 )B = 0 (значение кода: десятичное 0, биты: 1 )C = 110 (значение кода: 6 десятичных, биты: 3 )D = 111 (значение кода: 7 десятичных, биты: 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, будет в кодовой книге.

Псевдокод [ править ]

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

код  : = 0 , а больше символов сделать символ печати, код  код  : = ( код + 1) << ((длина бита следующего символа) - (текущая длина бита))

Алгоритм [ править ]

Алгоритм, описанный в: «Метод построения кодов с минимальной избыточностью» Дэвид А. Хаффман, Труды IRE:

Алгоритм код Хаффмана вычислений является  ввод: ансамбль сообщения (набор (сообщение, вероятность)). исходя из. вывод: кодовый ансамбль (набор (сообщение, код)).  1- сортировать ансамбль сообщений по убыванию вероятности. 2- N - кардинал ансамбля сообщений (количество различных Сообщения). 3- вычислить целое число n_0, такое как 2≤n_0≤D и (N − n_0) / (D − 1) является целым числом. 4- выберите n_0 наименее вероятных сообщений и назначьте им каждое цифровой код. 5- заменить выбранные сообщения суммированием составных сообщений их вероятность и переупорядочить. 6- пока остается более одного сообщения, выполните шаги 8. 7- выберите D наименее вероятных сообщений и назначьте им каждое цифровой код. 8- заменить выбранные сообщения составным сообщением суммируя их вероятность, и переупорядочьте ее. 9- код каждого сообщения дается путем объединения цифры кода агрегата, в который они были введены.

Литература: 1. Managing Gigabytes : книга с реализацией канонических кодов Хаффмана для словарей.