В информатике и теории информации канонический код Хаффмана — это особый тип кода Хаффмана с уникальными свойствами, которые позволяют описать его очень компактно. Вместо того, чтобы хранить структуру кодового дерева явно, канонические коды Хаффмана упорядочены таким образом, что достаточно хранить только длины кодовых слов, что снижает накладные расходы на кодовую книгу.
Компрессоры данных обычно работают одним из двух способов. Либо декомпрессор может вывести, какую кодовую книгу использовал компрессор из предыдущего контекста, либо компрессор должен сообщить декомпрессору, что это за кодовая книга. Поскольку каноническая кодовая книга Хаффмана может храниться особенно эффективно, большинство компрессоров начинают с генерации «обычной» кодовой книги Хаффмана, а затем преобразуют ее в каноническую Хаффмана перед использованием.
Для того чтобы схема кодирования символов, такая как код Хаффмана, была распакована, та же модель, которую алгоритм кодирования использовал для сжатия исходных данных, должна быть предоставлена алгоритму декодирования, чтобы он мог использовать ее для распаковки закодированных данных. В стандартном кодировании Хаффмана эта модель принимает форму дерева кодов переменной длины, при этом наиболее частые символы располагаются в верхней части структуры и представлены наименьшим количеством бит.
Однако это кодовое дерево вносит два критических недостатка в реализацию схемы кодирования. Во-первых, каждый узел дерева должен хранить либо ссылки на свои дочерние узлы, либо символ, который он представляет. Это дорого с точки зрения использования памяти, и если в исходных данных высокая доля уникальных символов, то размер кодового дерева может составлять значительную часть всех закодированных данных. Во-вторых, обход дерева требует больших вычислительных затрат, поскольку требует, чтобы алгоритм случайным образом перескакивал через структуру в памяти по мере считывания каждого бита в закодированных данных.
Канонические коды Хаффмана решают эти две проблемы, генерируя коды в четком стандартизированном формате; всем кодам для заданной длины присваиваются их значения последовательно. Это означает, что вместо хранения структуры кодового дерева для декомпрессии требуются только длины кодов, что уменьшает размер закодированных данных. Кроме того, поскольку коды последовательны, алгоритм декодирования может быть значительно упрощен, так что он будет вычислительно эффективным.
Обычный алгоритм кодирования Хаффмана присваивает каждому символу в алфавите код переменной длины. Более часто используемым символам будет присвоен более короткий код. Например, предположим, что у нас есть следующая неканоническая кодовая книга:
А = 11В = 0С = 101Д = 100
Здесь букве A назначено 2 бита , B — 1 бит, а C и D — по 3 бита. Чтобы сделать код каноническим кодом Хаффмана, коды перенумерованы. Длины бит остаются прежними, а кодовая книга сортируется сначала по длине кодового слова, а затем по алфавитному значению буквы:
В = 0А = 11С = 101Д = 100
Каждый из существующих кодов заменяется новым той же длины, используя следующий алгоритм:
При соблюдении этих трех правил каноническая версия кодовой книги будет выглядеть следующим образом:
В = 0А = 10С = 110Д = 111
Другая точка зрения на канонические кодовые слова заключается в том, что они являются цифрами после запятой основания (двоичной точки) в двоичном представлении определенной серии. В частности, предположим, что длины кодовых слов равны l 1 ... l n . Тогда каноническое кодовое слово для символа i — это первые l i двоичных цифр после запятой основания в двоичном представлении
Эта точка зрения особенно полезна в свете неравенства Крафта , которое гласит, что сумма выше всегда будет меньше или равна 1 (поскольку длины берутся из кода без префиксов). Это показывает, что добавление единицы в алгоритме выше никогда не приводит к переполнению и создает кодовое слово, которое длиннее, чем предполагалось.
Преимущество канонического дерева Хаффмана заключается в том, что его можно закодировать меньшим количеством бит, чем произвольное дерево.
Давайте возьмем нашу оригинальную кодовую книгу Хаффмана:
А = 11В = 0С = 101Д = 100
Есть несколько способов, которыми мы могли бы закодировать это дерево Хаффмана. Например, мы могли бы написать каждый символ , а затем указать количество битов и код :
('А',2,11), ('Б',1,0), ('С',3,101), ('Г',3,100)Поскольку мы перечисляем символы в последовательном алфавитном порядке, мы можем опустить сами символы, перечислив только количество бит и код :
(2,11), (1,0), (3101), (3100)
С нашей канонической версией мы знаем, что символы расположены в последовательном алфавитном порядке и что более поздний код всегда будет иметь большее значение, чем более ранний. Единственные части, которые осталось передать, — это длина бит ( число бит ) для каждого символа. Обратите внимание, что наше каноническое дерево Хаффмана всегда имеет более высокие значения для более длинных бит и что любые символы той же длины бит ( 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 имеет длину 1, затем A имеет длину 2, а оставшиеся 2 символа (C и D) имеют длину 3. Поскольку символы отсортированы по длине бит, мы можем эффективно реконструировать кодовую книгу. Псевдокод, описывающий реконструкцию, представлен в следующем разделе.
Этот тип кодирования выгоден, когда сжимается только несколько символов в алфавите. Например, предположим, что кодовая книга содержит только 4 буквы C , O , D и E , каждая длиной 2. Чтобы представить букву O с помощью предыдущего метода, нам нужно либо добавить много нулей (Метод 1):
0, 0, 2, 2, 2, 0, ... , 2, ...
или запишите, какие 4 буквы мы использовали. Каждый способ делает описание длиннее, чем следующее (Метод2):
(0,4), ('С','О','Д','Э')Формат обмена файлами JPEG использует метод кодирования Method2, поскольку в кодовой книге будет максимум 162 символа из 8-битного алфавита, имеющего размер 256.
Учитывая список символов, отсортированный по длине в битах, следующий псевдокод выведет каноническую кодовую книгу Хаффмана:
code := 0 , в то время как больше символов печатают символ, code code := ( code + 1) << ((длина бит следующего символа) − (текущая длина бит))
Алгоритм вычисления кода Хаффмана имеет входные данные: ансамбль сообщений (набор (сообщение, вероятность)). база D. выход: кодовый ансамбль (набор (сообщение, код)) . 1- отсортировать ансамбль сообщений по убыванию вероятности. 2- N - кардинал ансамбля сообщений (число различных сообщения). 3- вычислить целое число такое как и является целым числом. 4- выберите наименее вероятные сообщения и присвойте каждому из них цифровой код. 5- заменить выбранные сообщения составным сообщением, суммирующим их вероятность и переупорядочить ее. 6- пока остается более одного сообщения, выполните шаги по 8. 7- выберите D наименее вероятных сообщений и присвойте каждому из них цифровой код. 8- заменить выбранные сообщения составным сообщением суммируем их вероятности и переупорядочиваем. 9- код каждого сообщения получается путем конкатенации цифры кода агрегата, в который они были помещены.
[1] [2]
