Канонический код Хаффмана - Canonical Huffman code

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

Как дробное двоичное число

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

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

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

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

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

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

А = 11В = 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, то А длины 2 и остается 3. Поскольку символы отсортированы по длине битов, мы можем эффективно восстановить кодовую книгу. А псевдокод описание реконструкции вводится в следующем разделе.

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

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

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

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

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

Псевдокод

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

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

Алгоритм

Алгоритм, описанный в: «Метод построения кодов с минимальной избыточностью» Дэвид А. Хаффман, Proceedings of the I.R.E. is:

алгоритм вычислить код Хаффмана является    Вход:  ансамбль сообщений (набор (сообщение, вероятность)). основан. выход: кодовый ансамбль (набор (сообщение, код)). 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. Управление гигабайтами: книга с реализацией канонических кодов Хаффмана для словарей.