Адаптивный алгоритм хаффмана

Answers to Questions

How to encrypt using Huffman Coding cipher?

The Huffman code uses the frequency of appearance of letters in the text, calculate and sort the characters from the most frequent to the least frequent.

Example: The message DCODEMESSAGE contains 3 times the letter E, 2 times the letters D and S, and 1 times the letters A, C, G, M and O.

The Huffman algorithm will create a tree with leaves as the found letters and for value (or weight) their number of occurrences in the message. To create this tree, look for the 2 weakest nodes (smaller weight) and hook them to a new node whose weight is the sum of the 2 nodes. Repeat the process until having only one node, which will become the root (and that will have as weight the total number of letters of the message).

The binary code of each character is then obtained by browsing the tree from the root to the leaves and noting the path (0 or 1) to each node.

Example: DCODEMOI generates a tree where D and the O, present most often, will have a short code. ‘D = 00’, ‘O = 01’, ‘I = 111’, ‘M = 110’, ‘E = 101’, ‘C = 100’, so 0010001101110111 (16 bits)

How to decrypt Huffman Code cipher?

Decryption of the Huffman code requires knowledge of the matching tree or dictionary (characters binary codes)

To decrypt, browse the tree from root to leaves (usually top to bottom) until you get an existing leaf (or a known value in the dictionary).

Example: Deocde the message 0010001101110111, search for gives no correspondence, then continue with 00 which is code of the letter D, then 1 (does not exist), then 10 (does not exist), then 100 (code for C), etc. The plain message is’ DCODEMOI’

Why Huffman is used for compression?

By applying the algorithm of the Huffman coding, the most frequent characters (with greater occurrence) are coded with the smaller binary words, thus, the size used to code them is minimal, which increases the compression.

How to recognize Huffman coded text?

The encoded message is in binary format (or in a hexadecimal representation) and must be accompanied by a tree or correspondence table for decryption.

How to decipher Huffman coding without the tree?

By making assumptions about the length of the message and the size of the binary words, it is possible to search for the probable list of words used by Huffman.

It should then be associated with the right letters, which represents a second difficulty for decryption and certainly requires automatic methods.

What are the variants of the Huffman cipher?

There are variants of Huffman when creating the tree / dictionary.

The dictionary can be static: each character / byte has a predefined code and is known or published in advance (so it does not need to be transmitted)

The dictionary can be semi-adaptive: the content is analyzed to calculate the frequency of each character and an optimized tree is used for encoding (it must then be transmitted for decoding). This is the version implemented on dCode

The dictionary can be adaptive: from a known tree (published before and therefore not transmitted) it is modified during compression and optimized as and when. The calculation time is much longer but often offers a better compression ratio.

Спортивная карьера

После окончания школы Нэйт поступил в Публичный колледж Лансинга, где провёл два года, после чего перевёлся в Центральный мичиганский университет. За два года в университете он проявил себя как один из лучших игроков команды. Помимо успехов под кольцом, где он превосходил ростом своих соперников, Хаффман также демонстрировал редкую для центрового способность к дальним броскам. В свой первый сезон в команде он забросил 8 из 15 трёхочковых бросков, а во второй 20 из 47. Хаффман побил командный рекорд по проценту попаданий с игры за карьеру, державшийся десять лет, и оставался лидером по этому показателю в течение следующих шести лет с 58,1% попаданий.

В 1997 году Хаффман, хотя и не был выбран в драфте НБА, заключил договор с командой «Los Angeles Clippers» как свободный агент. Однако в НБА в этом сезоне он так и не попал и провёл год в клубе «Idaho Stampede» в Континентальной баскетбольной лиге, где в среднем набирал 11,2 очка и 7,6 подбора за 25 минут игры.

После года в КБА Хаффман подписал контракт с командой «Фуэнлабрада», выступающей в высшем дивизионе чемпионата Испании. В этом сезоне он в среднем проводил на площадке 28 минут и набирал по 12,7 очка и 8,6 подбора за игру и пробился с командой в плей-офф.

В 1999 году Хаффман подписал контракт с «Маккаби» (Тель-Авив), лидером израильского баскетбола. Он провёл в клубе три года, завоевав за это время три чемпионских звания и два Кубка Израиля. На международной арене в первый год с «Маккаби» он дошёл до финала Кубка европейских чемпионов, а во второй выиграл Супролигу, один из двух параллельных главных клубных турниров Европы того сезона. В сезоне 2000/2001 года Хаффман был признан Супролиги и самым ценным игроком чемпионата Израиля. Летом 2001 года клуб НБА «San Antonio Spurs» предложил Хаффману контракт на минимальную сумму в 332 тысячи долларов, но он отказался в пользу продолжения контракта с «Маккаби», где получал два миллиона.

По окончании третьего сезона с «Маккаби» Хаффман подписал трёхлетний контракт с командой НБА «Toronto Raptors» на общую сумму в 5,1 миллиона долларов, но провёл в ней только семь игр. В январе клуб объявил о расторжении контракта, обвинив Хаффмана в том, что тот скрыл при подписании травму колена. Хаффман подал судебный иск, который был решён в его пользу: команда была вынуждена выплатить травмированному центровому всю сумму, оговоренную в контракте. После этого Хаффман уже не выступал, хотя сообщалось о его предстоящем возвращении в Европу.

В 2015 году было объявлено, что у Хаффмана диагностирована терминальная стадия рака мочевого пузыря и что метастазы распространились уже по всему телу, включая лимфатические узлы, печень и лёгкие. Нейт Хаффман умер 15 октября 2015 года в возрасте 40 лет, оставив после себя вдову Мишель и шестилетнего сына Кристиана.

Метод Хаффмана

Идея метода

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

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

Алгоритм

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в ожидаемое сообщение.
2. Выбираются 2 свободных узла дерева с наименьшими весами.
3. Создается родитель с весом равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а двое его потомков удаляются из этого списка.
5. Одной дуге выходящей их родителя ставится в соответствие бит 1, другой – бит 0.
6. 6. Далее пункты повторяются, начиная со второго, до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Кодирование Хаффмана

Допустим у нас есть таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами – D и E. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6=11. Затем узлы D и E удаляются из списка свободных. Узел D соответствует ветви 0 родителя, узел E – ветви 1. На следующем шаге то же происходит с узлами B и C, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы B и C удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рисунке.

На следующем шаге «наилегчайшей» парой оказываются узлы B/C и D/E. Для них еще раз создается родитель, теперь уже с весом 24. Узел B/C соответствует ветви 0 родителя, D/E – ветви 1. На последнем шаге в списке свободных остается только 2 узла – это A и узел (B/C)/(D/E). В очередной раз создается родитель с весом 39, и бывшие свободные узлы присоединяются к разным его ветвям. Поскольку свободным остается только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Дерево представлено на рисунке.

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

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения A закодирован наименьшим количеством битов, а наиболее редкий символ E – наибольшим.

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

Алгоритмы

Существует несколько реализаций этого метода, наиболее примечательными являются «FGK» (ФГК: Фоллер, Галлагер и Кнут) и алгоритм Виттера.

ФГК алгоритм

Он позволяет динамически регулировать дерево Хаффмана, не имея начальных частот. В ФГК дереве Хаффмана есть особый внешний узел, называемый 0-узел, используемый для идентификации входящих символов. То есть, всякий раз, когда встречается новый символ — его путь в дереве начинается с нулевого узла

Самое важное — то, что нужно усекать и балансировать ФГК дерево Хаффмана при необходимости, и обновлять частоту связанных узлов. Как только частота символа увеличивается, частота всех его родителей должна быть тоже увеличена

Это достигается путём последовательной перестановки узлов, поддеревьев или и тех и других.

Важной особенностью ФГК дерева является принцип братства (или соперничества): каждый узел имеет два потомка (узлы без потомков называются листами) и веса идут в порядке убывания. Благодаря этому свойству дерево можно хранить в обычном массиве, что увеличивает производительность

Алгоритм Виттера

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

Цифры идут вниз, и справа налево.

Веса должны удовлетворять принципу братства. Таким образом, если А является родительским узлом B и C является потомком B, то W(A)>W(B)>W(C){\displaystyle W(A)>W(B)>W(C)}.

Вес — это всего лишь количество символов, встреченных ранее.

Набор узлов с одинаковыми весами представляют собой блок.

Чтобы получить код для каждого узла, в случае двоичного дерева мы могли бы просто пройти все пути от корня к узлу, записывая, например, «1» если мы идем направо, и «0» если мы пойдем налево.

Также в этом алгоритме используется специальный лист (узел без потомков), NYT (от англ. not yet transmitted — ещё не переданный символ), из которого «растут» новые, ранее не встречавшиеся, символы.

Кодер и декодер начинают только с корневого узла, который имеет максимальный вес. В начале это и есть наш NYT узел.

Когда мы передаем NYT символ, мы должны передать вначале код самого узла, а затем данные.

Для каждого символа, который уже находится в дереве, мы должны только передавать код конечных узлов (листов).

Для каждого передающегося символа передатчик и приёмник выполняют процедуру обновления:

1. Если текущий символ является не встречавшимся — добавить к NYT два дочерних узла: один для следующего NYT, другой для символа. Увеличить вес нового листа и старого NYT и переходить к шагу 4. Если текущий символ является не NYT, перейти к листу символа.
2. Если этот узел не имеет наибольший вес в блоке, поменять его с узлом, имеющим наибольшее число, за исключением, если этот узел является родительским элементом
3. Увеличение веса для текущего узла
4. Если это не корневой узел зайти в родительский узел затем перейдите к шагу 2. Если это корень, окончание.

Примечание: замена узлов означает замену весов и соответствующих символов, но не чисел.

Пример

Начинаем с пустого дерева.

Для «a» передаём его двоичный код.

NYT порождает два дочерних узла: 254 и 255.
Увеличиваем вес корня.
Код «a», связанный с узлом 255, становится 1.

Для «b» передавать 0 (код NYT узла), затем его двоичный код.

NYT порождает два дочерних узла: 252 для NYT и 253 для b.
Увеличиваем веса 253, 254 и корня.
Код для «b» равен 01.

Для следующего «b» передаётся 01.

Идём в лист 253. У нас есть блок весов в 1 и наибольшее число в блоке 255, так что меняем веса и символы узлов 253 и 255, увеличиваем вес, идём в корень и увеличиваем вес корня.

В будущем код «b» — это 1, а для «a» — это теперь 01, который отражает их частоту.

Биграммная модель

Существует разновидность алгоритма Хаффмана, использующая контекст. В данном случае размер контекста равен единице (биграммный — два символа, триграммный — три и так далее). Это метод построения префиксного кода для моделей высших порядков, уже не источника без памяти. Он использует результат (предыдущей операции) операции над предыдущей буквой совместно с текущей буквой. Строится на основе цепи Маркова с глубиной зависимости r=1{\displaystyle r=1}.

Алгоритм

1. Строится таблица в виде квадрата — распределение вероятностей на биграммах. Сразу вычисляется стартовая схема, с помощью которой будет кодироваться только первая буква. Строками в таблице, например, являются предыдущие буквы, а столбцами текущие.
2. Вычисляются вероятности для кодовых деревьев для контекстов.
3. По контекстам длины r=1{\displaystyle r=1} строятся остальные кодовые деревья, с помощью которых будут кодироваться все остальные символы (кроме первого).
4. Выполняется кодирование, первый символ кодируется согласно стартовой схеме, все последующие — исходя из кодовых деревьев для контекстов (предыдущего символа).

Декодирование выполняется аналогично: из стартовой кодовой схемы получаем первый контекст, а затем переходим к соответствующему кодовому дереву. Более того, декодеру необходима таблица распределения вероятностей.

Пример

Допустим, сообщение, которое надо закодировать «abcabcabc». Нам заранее известна таблица частот символов (на основе других данных, например, статистических данных по словарю).

Имеем стартовую схему: (a=516,b=516,c=616){\displaystyle (a={\tfrac {5}{16}},b={\tfrac {5}{16}},c={\tfrac {6}{16}})}. Сортируем по убыванию: (c=616,a=516,b=516){\displaystyle (c={\tfrac {6}{16}},a={\tfrac {5}{16}},b={\tfrac {5}{16}})} и строим кодовое дерево Хаффмана.

Для контекста «a» имеем:

• p(aa)=p(a,a)p(a)=316÷516=35{\displaystyle p(a/a)=p(a,a)/p(a)={\tfrac {3}{16}}\div {\tfrac {5}{16}}={\tfrac {3}{5}}},
• p(ba)=p(b,a)p(a)=116÷516=15{\displaystyle p(b/a)=p(b,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1}{5}}},
• p(ca)=p(c,a)p(a)=116÷516=15{\displaystyle p(c/a)=p(c,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1}{5}}}.

Для контекста «b» имеем:

• p(ab)=p(a,b)p(b)=18÷516=25{\displaystyle p(a/b)=p(a,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2}{5}}},
• p(bb)=p(b,b)p(b)=116÷516=15{\displaystyle p(b/b)=p(b,b)/p(b)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1}{5}}},
• p(cb)=p(c,b)p(b)=18÷516=25{\displaystyle p(c/b)=p(c,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2}{5}}}.

Для контекста «c» имеем:

• p(ac)=p(a,c)p(c)=18÷616=13{\displaystyle p(a/c)=p(a,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1}{3}}},
• p(bc)=p(b,c)p(c)=18÷616=13{\displaystyle p(b/c)=p(b,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1}{3}}},
• p(cc)=p(c,c)p(c)=18÷616=13{\displaystyle p(c/c)=p(c,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1}{3}}}.

Примечание: здесь p(x, y) не равно p(y, x).

Строим кодовые деревья для каждого контекста. Выполняем кодирование и имеем закодированное сообщение: (00, 10, 01, 11, 10, 01, 11, 10, 01).

• 00 — из кода буквы «a» для стартовой схемы,
• 10 — из кода буквы «b» для контекста «a»,
• 01 — из кода буквы «c» для контекста «b»,
• 11 — из кода буквы «a» для контекста «c».

Кодирование Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности появления символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (то есть ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. Битовые значения ветвей, исходящих от корня, не зависят от весов потомков.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

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

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

Построение дерева для данного примера

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

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

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что энтропия источника, независимым образом порождающего символы с указанными частотами, составляет ~2,1858 бита на символ, то есть избыточность построенного для такого источника кода Хаффмана, понимаемая как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

Классический алгоритм Хаффмана имеет ряд существенных недостатков. Во-первых, для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования. Во-вторых, избыточность кодирования обращается в ноль лишь в тех случаях, когда вероятности кодируемых символов являются обратными степенями числа 2. В-третьих, для источника с энтропией, не превышающей 1 (например, для двоичного источника), непосредственное применение кода Хаффмана бессмысленно.

Масштабирование весов узлов дерева Хаффмана

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

Объясняется это тем, что при делении целых чисел отбрасывается дробная часть.

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

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

Выигрыш от масштабирования

Масштабирование веса узлов дерева через определенные интервалы дает неожиданный результат. Несмотря на то, что при масштабировании происходит потеря точности статистики, тесты показывают, что оно приводит к лучшим показателям сжатия, чем если бы масштабирование откладывалось. Это можно объяснить тем, что текущие символы сжимаемого потока больше «похожи» на своих близких предшественников, чем на тех, которые встречались намного раньше. Масштабирование приводит к уменьшению влияния «давних» символов на статистику и к увеличению влияния на неё «недавних» символов. Это очень сложно измерить количественно, но, в принципе, масштабирование оказывает положительное влияние на степень сжатия информации. Эксперименты с масштабированием в различных точках процесса сжатия показывают, что степень сжатия сильно зависит от момента масштабирования веса, но не существует правила выбора оптимального момента масштабирования для программы, ориентированной на сжатие любых типов информации.