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

В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.

Этот метод кодирования состоит из двух основных этапов: Построение оптимального кодового дерева. Построение отображения код-символ на основе построенного дерева.

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

Классический алгоритм Хаффмана на входе получает таблицу частотностей символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево)Д. Мастрюков. Монитор 7-8.93 . Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение. Выбираются два свободных узла дерева с наименьшими весами. Создаётся их родитель с весом, равным их суммарному весу. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. Битовые значения ветвей, исходящих от корня, не зависят от весов потомков. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица абсолютных частотностей: СимволАБВГДАбсолютная частотность 15 7 6 6 5

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

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

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

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом. Символ А Б В Г ДКод 0 100 101 110 111

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

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

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

Адаптивное сжатие

Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.

В создании алгоритма адаптивного кодирования Хаффмана наибольшие сложности возникают при разработке процедуры обновления модели очередным символом. Теоретически можно было бы просто вставить внутрь этой процедуры полное построение дерева кодирования Хаффмана, однако, такой алгоритм сжатия имел бы неприемлемо низкое быстродействие, так как построение Н-дерева — это слишком большая работа, и производить её при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее Н-дерево так, чтобы отобразить обработку нового символа. Наиболее известными алгоритмами перестроения являются алгоритм Фоллера-Галлагера-Кнута (FGK) и алгоритм Виттера.

Все алгоритмы перестроения дерева при считывании очередного символа включают в себя две операции:

Первая — увеличение веса узлов дерева. Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса потомков. Этот процесс продолжается до тех пор, пока мы не доберёмся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ.

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

Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдём последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве (при этом родители каждого из узлов тоже изменятся). На этом операция перестановки заканчивается.

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

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

В этом алгоритме не строится дерево ХаффманаПодробнее с примерами алгоритм расписан в Managing Gigabytes авторов Witten, Мoffat, Bell на 68-й странице..

Состоит из двух этапов: Подсчёт длины кода для какого-то символа Составление кода.

Подсчёт длины Посчитаем частотность для каждого символа Отсортируем их в лексикографическом порядке. В массив запишем частотность каждой буквы. Слева приписываем массив той же длины, но с порядковыми номерами из правого массива. Левый массив получается списком указателей на элементы правой части. В левой части делаем не возрастающую пирамиду. Но куча будет не по значению элементов массива, а по значению на ссылаемый элемент массива. Самый левый элемент указывает на символ из правого массива с наименьшей частотностью. Его можно удалить следующим образом: Правую половину не трогаем Первый элемент массива заменяем на самый правый элемент левого массива, якобы сдвигая границу разделения. Проверяем условия правильности пирамиды, если что-то не так, то надо повторить «хипизацию». Убирается первый элемент левой части массива и объединяется ранее убранным. Сумма их частотностей записывается в границу между левым и правым массивом. На место удалённого элемента в левой части записывается индекс массива куда добавили сумму частотностей на прошлом шаге. Из-за того объединили два элемента нужно изменить значения этих элементов массива ссылкой на родителя, куда их положили. Повторяем, пока в куче слева не останется 1 элемент. В правой части массива получились ссылки на элементы, объединяющие 2 символа. Поэтому идём по массиву по ссылкам, инкрементируя уровень погружения. Количество переходов по ссылкам будет длиной кода Хаффмана.

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

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

Алгоритм Строится таблица в виде квадрата — распределение вероятностей на биграммах. Сразу вычисляется стартовая схема, с помощью которой будет кодироваться только первая буква. Строками в таблице, например, являются предыдущие буквы, а столбцами текущие. Вычисляются вероятности для кодовых деревьев для контекстов. По контекстам длины строятся остальные кодовые деревья, с помощью которых будут кодироваться все остальные символы (кроме первого). Выполняется кодирование, первый символ кодируется согласно стартовой схеме, все последующие — исходя из кодовых деревьев для контекстов (предыдущего символа). Декодирование выполняется аналогично: из стартовой кодовой схемы получаем первый контекст, а затем переходим к соответствующему кодовому дереву. Более того, декодеру необходима таблица распределения вероятностей.

Пример

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

Для контекста «a» имеем: , , . Для контекста «b» имеем: , , . Для контекста «c» имеем: , , . Примечание: здесь p(x, y) не равно p(y, x).

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