Как хранить дерево хаффмана

Добавил пользователь Алексей Ф.
Обновлено: 19.09.2024

Delphi site: daily Delphi-news, documentation, articles, review, interview, computer humor.

Алгоритм кодирования Хаффмана очень похож на алгоритм сжатия Шеннона-Фано. Этот алгоритм был изобретен Девидом Хаффманом (David Huffman) в 1952 году ("A method for the Construction of Minimum-Redundancy Codes" ("Метод создания кодов с минимальной избыточностью")), и оказался еще более удачным, чем алгоритм Шеннона-Фано. Это обусловлено тем, что алгоритм Хаффмана математически гарантированно создает наименьший по размеру код для каждого из символов исходных данных.

Аналогично применению алгоритма Шеннона-Фано, нужно построить бинарное дерево, которое также будет префиксным деревом, где все данные хранятся в листьях. Но в отличие от алгоритма Шеннона-Фано, который является нисходящим, на этот раз построение будет выполняться снизу вверх. Вначале мы выполняем просмотр входных данных, подсчитывая количество появлений значений каждого байта, как это делалось и при использовании алгоритма Шеннона-Фано. Как только эта таблица частоты появления символов будет создана, можно приступить к построению дерева.

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

Описанный процесс не очень нагляден, поэтому создадим дерево Хаффмана для предложения "How much wood could a woodchuck chuck?" Мы уже вычислили количество появлений символов этого предложения и представили их в виде таблицы 11.1, поэтому теперь к ней потребуется применить описанный алгоритм с целью построения полного дерева Хаффмана. Выберем два узла с наименьшими значениями. Существует несколько узлов, из которых можно выбрать, но мы выберем узлы "m" и Для обоих этих узлов число появлений символов равно 1. Создадим родительский узел, значение счетчика которого равно 2, и присоединим к нему два выбранных узла в качестве дочерних. Поместим родительский узел обратно в пул. Повторим цикл с самого начала. На этот раз мы выбираем узлы "а" и "Д.", объединяем их в мини-дерево и помещаем родительский узел (значение счетчика которого снова равно 2) обратно в пул. Снова повторим цикл. На этот раз в нашем распоряжении имеется единственный узел, значение счетчика которого равно 1 (узел ПН") и три узла со значениями счетчиков, равными 2 (узел "к" и два родительских узла, которые были добавлены перед этим). Выберем узел "к", присоединим его к узлу wHn и снова добавим в пул родительский узел, значение счетчика которого равно 3. Затем выберем два родительских узла со значениями счетчиков, равными 2, присоединим их к новому родительскому узлу со значением счетчика, равным 4, и добавим этот родительский узел в пул. Несколько первых шагов построения дерева Хаффмана и результирующее дерево показаны на рис. 11.2.

Используя это дерево точно так же, как и дерево, созданное для кодирования Шенона-Фано, можно вычислить код для каждого из символов в исходном предложении и построить таблицу 11.5.

Таблица 11.5. Коды Хаффмана для символов примера предложения

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

Теперь можно вычислить код для всего предложения. Он начинается с битов:

и содержит всего 131 бит. Если бы исходное предложение было закодировано кодами ASCII, по одному байту на символ, оно содержало бы 286 битов. Таким образом, в данном случае коэффициент сжатия составляет приблизительно 54%.

Повторим снова, что, как и при применении алгоритма Шеннона-Фано, необходимо каким-то образом сжать дерево и включить его в состав сжатых данных.

Восстановление выполняется совершенно так же, как при использовании кодирования Шеннона-Фано: необходимо восстановить дерево из данных, хранящихся в сжатом потоке, и затем воспользоваться им для считывания сжатого потока битов.

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

Эта высокоуровневая подпрограмма TDHuffroanCompress, выполняющая кодирование Хаффмана, приведена в листинге 11.5.

Листинг 11.5. Высокоуровневая подпрограмма кодирования Хаффмана

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

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

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

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

И, наконец, когда все эти структуры данных определены, мы вызываем подпрограмму DoHuffmanCompression, выполняющую реальное сжатие данных. Код этой подпрограммы приведен в листинге 11.6.

Листинг 11.6. Цикл сжатия Хаффмана

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

После того, как мы ознакомились с выполнением сжатия Хаффмана на высоком уровне, следует рассмотреть класс, выполняющий большую часть вычислений. Это внутренний класс THuffmanTree. Объявление связных с ним типов показано в листинге 11.7.

Вначале мы объявляем узел дерева Хаффмана THaffxnanNode и массив этих узлов THaffmanNodeArray фиксированного размера. Этот массив будет использоваться для создания реальной структуры дерева и будет содержать ровно 511 элементов. Почему именно это количество?

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

Листинг 11.7. Класс дерева Хаффмана

Предположим, что дерево содержит только два типа узлов: внутренние, имеющие ровно по два дочерних узла, и листья, не имеющие узлов (иначе говоря, не существует узлов, имеющих только один дочерний узел, - именно такой вид имеет префиксное дерево). Сколько внутренних узлов имеет это дерево, если оно содержит п листьев? Лемма утверждает, что такое дерево содержит ровно п - 1 внутренних узлов. Это утверждение можно доказать методом индукции. Когда п = 1, лемма явно выполняется, поскольку дерево содержит только корневой узел.

Теперь предположим, что лемма справедлива для всех /

Поскольку конструктор не распределяет никакой памяти, и никакое распределение памяти не выполняется ни в каком другом объекте класса, явному деструктору нечего делать. Поэтому по умолчанию класс использует метод TObject.Destroy.

Первым методом, вызываемым для дерева Хаффмана в подпрограмме сжатия, был метод CalcCharDistribution. Это метод считывает входной поток, вычисляет количество появлений каждого символа, а затем строит дерево.

Листинг 11.9. Вычисление количеств появлений символов

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

Прежде чем изучить реализацию этого важного внутреннего метода, рассмотрим возможную реализацию алгоритма построения дерева. Вспомним, что мы начинаем с создания "пула" узлов, по одному для каждого символа. Мы выбираем два наименьших узла (т.е. два узла с наименьшими значениями счетчиков) и присоединяем их к новому родительскому узлу (устанавливая значение его счетчика равным сумме значений счетчиков его дочерних узлов), а затем помещаем родительский узел обратно в пул. Мы продолжаем этот процесс до тех пор, пока в пуле не останется только один узел. Если вспомнить описанное в главе 9, станет очевидным, какую структуру можно использовать для реализации этого аморфного "пула": очередь по приоритету. Строго говоря, мы должны использовать сортирующее дерево с выбором наименьшего элемента (обычно очередь по приоритету реализуется так, чтобы возвращать наибольший элемент).

Листинг 11.10. Построение дерева Хаффмана

procedure THuffmanTree.htBuild; var i : integer; PQ : TtdPriorityQueue; Nodel : PHuffmanNode; Node2 : PHuffmanNode; RootNode : PHuffmanNode; begin

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

Как только очередь по приоритету создана, мы помещаем в нее все узлы с ненулевыми значениями счетчиков. В случае существования только одного такого узла, значение поля корневого узла дерева Хаффмана устанавливается равным индексу этого единственного узла. В противном случае мы применяем алгоритм Хаффмана, причем обращение к первому родительскому узлу осуществляется по индексу, равному 256. Удаляя из очереди два узла и помещая в нее новый родительский узел, мы поддерживаем значение переменной РКоо^ чтобы она указывала на последний родительский узел. В результате по окончании процесса нам известен индекс элемента, представляющего корневой узел дерева.

И, наконец, мы освобождаем объект очереди по приоритету. Теперь дерево Хаффмана полностью построено.

Следующий метод, вызываемый в высокоуровневой подпрограмме сжатия - метод, который выполняет запись дерева Хаффмана в выходной поток битов. По существу, нам необходимо применить какой-либо алгоритм, выполняющий запись достаточного объема информации, чтобы можно было восстановить дерево. Одна из возможностей предусматривает запись символов и их значений счетчика появлений. При наличии этой информации программа восстановления может без труда восстановить дерево Хаффмана, просто вызывая метод 1гёВи11с1 Это кажется здравой идеей, если не учитывать объем, занимаемый таблицей символов и количеств их появлений в сжатом выходном потоке. В этом случае каждый символ занимал бы в выходном потоке полный байт, а его значение счетчика занимало бы определенное фиксированное количество байтов (например, два байта на символ, чтобы можно было подсчитывать вплоть до 65535 появлений). При наличии во входном потоке 100 отдельных символов вся таблица занимала бы 300 байт. Если бы во входном потоке присутствовали все возможные символы, таблица занимала бы 768 байт.

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

Конечно, если бы входной поток был достаточно большим, некоторые из значений счетчиков могли бы превысить размер 2-байтового слова, и для каждого символа пришлось бы использовать по три или даже четыре байта.

Более рациональный подход - игнорировать значения счетчиков символов и сохранять реальную структуру дерева. Префиксное дерево содержит два различных вида узлов: внутренние с двумя дочерними узлами и внешние, не имеющие дочерних узлов. Внешние узлы - это узлы, содержащие символы. Выполним обход дерева, применив один из обычных методов обхода (фактически, мы будем использовать метод обхода в ширину). Для каждого достигнутого узла будем записывать нулевой бит, если узел является внутренним, или единичный бит, если узел является внешним, за которым будет следовать представляемый узлом символ. Код реализации метода SaveToBitStream и вызываемого им рекурсивного метода htSaveNode, который выполняет реальный обход дерева и запись информации в поток битов, представлен в листинге 11.11.

Листинг 11.11. Запись дерева Хаффмана в поток битов

Если бы во входном потоке присутствовало 100 отдельных символов, он содержал бы 99 внутренних узлов, и требовалось бы всего 199 битов для хранения информации об узлах плюс 100 байтов для хранения самих символов - всего около 125 байтов. Если бы во входном потоке были представлены все символы, требовалось бы 511 битов для хранения информации об узлах плюс место для хранения 256 символов. Таким образом, всего для хранения дерева требовалось бы 320 байтов.

Полный код подпрограммы сжатия дерева Хаффмана можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHuffmn.pas.

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

Листинг 11.12. Подпрограмма TDHuffmanDecoropress

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

Затем выполняется считывание длины несжатых данных, и если она равна нулю, задача выполнена. В противном случае необходимо проделать определенную работу. В этом случае мы создаем входной поток битов, содержащий входной поток. Затем мы создаем объект дерева Хаффмана, который будет выполнять большую часть работы, и вынуждаем его выполнить собственное считывание из входного потока битов (вызывая для этого метод LoadFromBitStream). Если дерево Хаффмана представляет единственный символ, исходный поток восстанавливается в виде повторений этого символа. В противном случае мы вызываем подпрограмму DoHuffmanDecoonpression для выполнения восстановления данных. Код этой подпрограммы приведен в листинге 11.13.

Листинг 11.13. Подпрограмма DoHuffmanDecompression

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

Листинг 11.14. Метод DecodeNextByte

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

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

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

Он был изобретен Дэвидом Альбертом Хаффманом и опубликован в 1952 году.

Резюме

Принцип

Принцип кодирования Хаффмана основан на создании древовидной структуры, состоящей из узлов.

Дерево создается следующим образом: мы каждый раз связываем два узла наименьшего веса, чтобы получить новый узел, вес которого эквивалентен сумме весов его дочерних элементов. Мы повторяем этот процесс, пока у нас не останется только один узел: корень. Тогда, например, код 0 связан с каждой ветвью, идущей влево, а код 1 - вправо.

Различные методы построения дерева

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

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

Характеристики

Где - длина кодового слова, кода, связанного с исходным символом , и - это набор исходных символов. л ( Икс ) ПРОТИВ ( Икс ) Икс Ω

По методу Хаффмана код префикса кода с переменной длиной . Он оптимален в смысле наименьшей длины для символьного кодирования . То есть для кода Хаффмана и для любого однозначно декодируемого кода тогда: ПРОТИВ * > ПРОТИВ

Ограничения кодирования Хаффмана

Мы можем показать, что для источника энтропия Шеннона средняя длина кодового слова, полученного с помощью кодирования Хаффмана, удовлетворяет: Икс ЧАС ( Икс ) L

ЧАС ( Икс ) ≤ L ЧАС ( Икс ) + 1

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

Одно из решений этой проблемы - работать с блоками символов. Затем мы показываем, что можем приблизиться к энтропии: нет

ЧАС ( Икс ) ≤ L ЧАС ( Икс ) + 1 нет

но процесс оценки вероятностей становится более сложным и дорогостоящим.

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

На практике, когда мы хотим приблизиться к энтропии, мы предпочитаем арифметическое кодирование, оптимальное на битовом уровне.

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

Канонический код

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

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

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

Использует

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

Другие так называемые консервативные (без потерь) алгоритмы сжатия, такие как те, которые используются для сжатия файлов, также используют Хаффмана для сжатия результирующего словаря. Например, LZH ( Lha ) и deflate ( ZIP , gzip , PNG ) объединяют алгоритм сжатия словаря ( LZ77 ) и энтропийное кодирование Хаффмана.

История

Первый Macintosh компания Apple использовала код Хаффмана для представления текстов: 15 наиболее часто встречающихся символов языка были закодированы на 4 бита, а 16- я конфигурация служила префиксом для кодирования других однобайтовых символов (что, таким образом, сделал иногда 4 бита, иногда 12 бит на символ (см. UTF-8 ). Было обнаружено, что этот простой метод позволяет сэкономить 30% места в среднем тексте в то время, когда оперативная память все еще была дорогим компонентом.

Кодирование Хаффмана ( англ. Huffman coding ) - один из самых простых и легко реализуемых методов сжатия без потерь [1] . Он был разработан в 1952 году американцем Дэвидом Хаффманом [2] .

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

Исходный алфавит (набор символов) задан С. знак равно < Икс 1 , … , Икс п > , \ dots, x_ \>> и набор связанных вероятностей П. знак равно < п 1 , … , п п >. , \ dots, p_ \>.> Символы обычно являются байтами , хотя нет никаких препятствий для того, чтобы ими могло быть что-то еще (например, пары символов). Вероятности могут быть заранее определены для данного набора данных, например, путем определения частоты появления символов в текстах на данном языке. Однако чаще они устанавливаются индивидуально для каждого набора данных.

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

Свойства кода Хаффмана следующие:

это код префикса ; то есть никакое кодовое слово не является началом другого слова;
средняя длина кодового слова является наименьшей среди префиксных кодов;
если вероятности разные, т.е. п j > п а также , > p_ ,> длина кода для символа Икс j > не больше кода символа Икс а также ; <\ displaystyle x_ ;>
кодовые слова двух наименее вероятных символов имеют одинаковую длину.

Сжатие заключается в замене символов полученными кодами.

Определите вероятность (или частоту) для каждого символа в наборе S.
Создайте список двоичных деревьев, которые содержат пары символов и вероятностей в узлах. Сначала деревья состоят только из корня.
Пока в списке более одного дерева, повторите:
1. Удалите два наименее вероятных дерева из списка корней.
2. Вставьте новое дерево, корень которого является суммой вероятностей удаленных деревьев, а сами они станут его левым и правым поддеревьями. В корне дерева символ не хранится.
Дерево, которое остается в списке, называется деревом Хаффмана - вероятность, записанная в корне, равна 1, а символы записываются в листьях дерева.

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

Кодовые слова создаются из дерева Хаффмана; алгоритм следующий:
1. Присвойте 0 каждому левому краю дерева и 1 - правому (вы, конечно, можете сделать наоборот).
2. Двигайтесь глубже в дерево от корня к каждому листу (символу):
  1. Если повернуть направо, добавьте к коду 1 бит.
  2. Если повернуть налево, добавьте к коду бит 0.
  Длина кодового слова равна глубине символа в дереве, двоичное значение зависит от его положения в дереве.
  
  Пример
  
  Кодирование исходного алфавита по алгоритму (обозначения как на картинке справа):
  1. Комбинируя символы (A) и (B), получаем (A + B) = 0,3; (C) = 0,3; (D) = 0,4.
  2. Объединяя дерево (A + B) с символом (C), получаем элементы ((A + B) + C) = 0,6 и (D) = 0,4.
  3. Соединение дерева ((A + B) + C) с помощью символа (D). Остается только один свободный узел (корень) - получаем дерево (((A + B) + C) + D) = 1.0.
  4. Осталось вычислить коды отдельных символов:
    - A = слева, слева, слева = 000
    - B = слева, слева, справа = 001
    - C = влево, вправо = 01
    - D = вправо = 1
  Как вы можете легко проверить, средняя длина кода будет: Л. k знак равно п ( А ТАКЖЕ ) ⋅ 3 + п ( B ) ⋅ 3 + п ( С. ) ⋅ 2 + п ( D ) ⋅ 1 знак равно 0 , 3 + 0 , 6 + 0 , 6 + 0 , 4 знак равно 1 , 9. = п (А) \ cdot 3 + p (B) \ cdot 3 + p (C) \ cdot 2 + p (D) \ cdot 1 = 0 3 + 0 6 + 0 6 + 0 4 = 1 9.>
  - 000 [left, left, left] достигается на листе A
  - 001 [влево, влево, вправо], затем достигает листа B
  - 01 [левый, правый] лист C достигнут
  - 1 [справа], лист D достигнут
  Практическое применение
  
  Одна из основных проблем при использовании статического алгоритма Хаффмана - это передача всего дерева или всей таблицы вероятностей. В случае передачи дерева узлы посещаются в порядке предварительного заказа , внутренний узел может быть записан в один бит (у него всегда есть два сына), в то время как списки требуют один бит плюс количество битов, необходимых для хранения символа (например, 8 биты). Например, дерево из приведенного выше примера можно записать как: (1, 0, 'D', 1, 0, 'C', 1, 0, 'B', 0, 'A'), то есть 7 + 4 · 8 = 39 бит.
  
  Лучшее сжатие, но за счет очень быстрого увеличения требований к памяти, достигается за счет кодирования нескольких последовательных символов одновременно, даже если они не коррелированы.
  
  Пример кодирования сразу 2 символов
  - Парные символы - AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD с вероятностями - .
  - Дерево растет следующим образом:
    1. (AA + AB) = 0,03;
    2. (BA + AC) = 0,05;
    3. (CA + (AA + AB)) = 0,06;
    4. (BB + AD) = 0,08;
    5. (DA + (BA + AC)) = 0,09;
    6. (BC + CB) = 0,12;
    7. ((CA + (AA + AB)) + BD) = 0,14;
    8. (DB + (BB + AD)) = 0,16;
    9. ((DA + (BA + AC)) + CC) = 0,18;
    10. (CD + DC) = 0,24;
    11. ((BC + CB) + ((CA + (AA + AB)) + BD)) = 0,26;
    12. (DD + (DB + (BB + AD))) = 0,32;
    13. (((DA + (BA + AC)) + CC) + (CD + DC)) = 0,42;
    14. (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD))))) = 0,58;
    15. ((((DA + (BA + AC)) + CC) + (CD + DC)) + (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + ( DB + (BB + AD))))) = 1.0.
  Таким образом, соответствующие пары символов соответствуют:
  - AA - 101010
  - AB - 101011
  - AC - 00011
  - Нашей эры - 11111
  - BA - 00010
  - BB - 11110
  - До н.э. - 1000
  - БД - 1011
  - CA - 10100
  - CB - 1001
  - CC - 001
  - CD - 010
  - DA - 0000
  - ДБ - 1110
  - DC - 011
  - ДД - 110
  Среднее количество битов на пару символов составляет 3,73, поэтому среднее количество битов на символ составляет 1,865. Это намного лучшее сжатие (6,75% вместо 5% при максимально возможных 7,68%), чем в предыдущем примере. Используя большее количество символов, вы можете приблизиться к максимальному сжатию, но у вас закончится нехватка памяти гораздо раньше, поскольку требования к памяти увеличиваются экспоненциально до количества символов, которые вы можете сжать одновременно.
  
  Динамическое кодирование Хаффмана - это кодирование данных с неизвестной статистикой. Статистика строится по мере поступления данных, и дерево Хаффмана улучшает каждый символ или количество символов .
  
  Преимущество динамического кодирования в том, что вам не нужно загружать дерево кода. Вместо этого одна и та же процедура исправления деревьев должна выполняться как кодером, так и декодером.
  
  Существует два алгоритма исправления дерева Хаффмана:
  1. Алгоритм Фаллера-Галлагера-Кнута (создатели - Ньютон Фаллер и Роберт Галлагер, метод был усовершенствован Дональдом Кнутом ),
  2. Алгоритм Виттера (дальнейшие улучшения метода FGK Джеффри Виттера).
  Алгоритм FGK основан на следующих предположениях о виде дерева:
  - у каждого узла дерева всегда есть два потомка, кроме листьев ;
  - с каждым узлом связан числитель: в листьях он хранит количество появлений данного символа (или пропорциональное значение ), в других узлах - сумму дочерних счетчиков;
  - при перемещении дерева справа налево и считывании счетчиков, связанных с каждым узлом, получается последовательность невозрастающих чисел.
  Последнее предположение было ужесточено в алгоритме Виттера :
  - также получается последовательность невозрастающих чисел, но внутри подстрок с одинаковыми значениями есть числа из внутренних узлов в начале и числа из листьев в конце.
  Когда числитель в листе увеличивается, алгоритмы изменяют (перемещают некоторые узлы) только небольшую часть дерева, сохраняя вышеупомянутые свойства. Алгоритм Виттера немного сложнее, но дает лучшие результаты, т.е. более короткие коды, чем алгоритм FKG .
  
  Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана [Huffman 52] производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое дерево снизу вверх, затем скользит вниз по дереву, чтобы построить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему). Начиная с работ Д.Хаффмана 1952 года, этот алгоритм являлся предметом многих исследований. (Последнее утверждение из § 3.8.1 показывает, что наилучший код переменной длины можно иногда получить без этого алгоритма.)
  
  Алгоритм начинается составлением списка символов алфавита в порядке убывания их вероятностей. Затем от корня строится дерево, листьями которого служат эти символы. Это делается по шагам, причем на каждом шаге выбираются два символа с наименьшими вероятностями, добавляются наверх частичного дерева, удаляются из списка и заменяются вспомогательным символом, представляющим эти два символа. Вспомогательному символу приписывается вероятность, равная сумме вероятностей, выбранных на этом шаге символов. Когда список сокращается до одного вспомогательного символа, представляющего весь алфавит, дерево объявляется построенным. Завершается алгоритм спуском по дереву и построением кодов всех символов.
  
  Лучше всего проиллюстрировать этот алгоритм на простом примере. Имеется пять символов с вероятностями, заданными на рис. 1.3а.
  
  Рис. 1.3. Коды Хаффмана.
  
  Символы объединяются в пары в следующем порядке:
  
  1. объединяется с , и оба заменяются комбинированным символом с вероятностью 0.2;
  
  2. Осталось четыре символа, с вероятностью 0.4, а также и с вероятностями по 0.2. Произвольно выбираем и , объединяем их и заменяем вспомогательным символом с вероятностью 0.4;
  
  3. Теперь имеется три символа и с вероятностями 0.4, 0.2 и 0.4, соответственно. Выбираем и объединяем символы и во вспомогательный символ с вероятностью 0.6;
  
  4. Наконец, объединяем два оставшихся символа и и заменяем на с вероятностью 1.
  
  Средняя длина этого кода равна бит/символ. Очень важно то, что кодов Хаффмана бывает много. Некоторые шаги алгоритма выбирались произвольным образом, поскольку было больше символов с минимальной вероятностью. На рис. 1.3b показано, как можно объединить символы по-другому и получить иной код Хаффмана (11, 01, 00, 101 и 100). Средняя длина равна бит/символ как и у предыдущего кода.
  
  Пример: Дано 8 символов А, В, С, D, Е, F, G и H с вероятностями 1/30, 1/30, 1/30, 2/30, 3/30, 5/30, 5/30 и 12/30. На рис. 1.4а,b,с изображены три дерева кодов Хаффмана высоты 5 и 6 для этого алфавита.
  
  Рис. 1.4. Три дерева Хаффмана для восьми символов.
  
  Средняя длина этих кодов (в битах на символ) равна
  
  Пример: На рис. 1.4d показано другое дерево высоты 4 для восьми символов из предыдущего примера. Следующий анализ показывает, что соответствующий ему код переменной длины плохой, хотя его длина меньше 4.
  
  (Анализ.) После объединения символов А, В, С, D, Е, F и G остаются символы ABEF (с вероятностью 10/30), CDG (с вероятностью 8/30) и H (с вероятностью 12/30). Символы ABEF и CDG имеют наименьшую вероятность, поэтому их необходимо было слить в один, но вместо этого были объединены символы CDG и H. Полученное дерево не является деревом Хаффмана.
  
  Дисперсия показывает насколько сильно отклоняются длины индивидуальных кодов от их средней величины (это понятие разъясняется в любом учебнике по статистике). Дисперсия кода 1.3а равна , а для кода 1.3b .
  
  Код 1.3b является более предпочтительным (это будет объяснено ниже). Внимательный взгляд на деревья показывает, как выбрать одно, нужное нам. На дереве рис. 1.3а символ сливается с символом , в то время как на рис. 1.3b он сливается с . Правило будет такое: когда на дереве имеется более двух узлов с наименьшей вероятностью, следует объединять символы с наибольшей и наименьшей вероятностью; это сокращает общую дисперсию кода.
  
  Если кодер просто записывает сжатый файл на диск, то дисперсия кода не имеет значения. Коды Хаффмана с малой дисперсией более предпочтительны только в случае, если кодер будет передавать этот сжатый файл по линиям связи. В этом случае, код с большой дисперсией заставляет кодер генерировать биты с переменной скоростью. Обычно данные передаются по каналам связи с постоянной скоростью, поэтому кодер будет использовать буфер. Биты сжатого файла помещаются в буфер по мере их генерации и подаются в канал с постоянной скоростью для передачи. Легко видеть, что код с нулевой дисперсией будет подаваться в буфер с постоянной скоростью, поэтому понадобится короткий буфер, а большая дисперсия кода потребует использование длинного буфера.
  
  Табл. 1.5. Пример кода Хаффмана.
  
  Длина кода символа , конечно, зависит от его вероятности . Однако она также неявно зависит от размера алфавита. В большом алфавите вероятности символов малы, поэтому коды Хаффмана имеют большую длину. В маленьком алфавите наблюдается обратная картина. Интуитивно это понятно, поскольку для малого алфавита требуется всего несколько кодов, поэтому все они коротки, а большому алфавиту необходимо много кодов и некоторые из них должны быть длинными.
  
  Рис. 1.6. Код Хаффмана для английского алфавита.
  
  На рис. 1.6 показан код Хаффмана для всех 26 букв английского алфавита.
  
  Случай алфавита, в котором символы равновероятны, особенно интересен. На рис. 1.7 приведены коды Хаффмана для алфавита с 5, 6, 7 и 8 равновероятными символами. Если размер алфавита является степенью 2, то получаются просто коды фиксированной длины. В других случаях коды весьма близки к кодам с фиксированной длиной. Это означает, что использование кодов переменной длины не дает никаких преимуществ. В табл. 1.8 приведены коды, их средние длины и дисперсии.
  
  Рис. 1.7. Коды Хаффмана с равными вероятностями.
  
  Заметим, что метод Хаффмана не работает в случае двухсимвольного алфавита. В таком алфавите одному символу придется присвоить код 0, а другому 1. Метод Хаффмана не может присвоить одному символу код короче одного бита. Если исходные данные (источник) состоят из индивидуальных битов, как в случае двухуровневого (монохромного) изображения, то возможно представление нескольких бит (4 или 8) в виде одного символа нового недвоичного алфавита (из 16 или 256 символов). Проблема при таком подходе заключается в том, что исходные битовые данные могли иметь определенные статистические корреляционные свойства, которые могли быть утеряны при объединении битов в символы. При сканировании монохромного рисунка или диаграммы по строкам пикселы будут чаще встречаться длинными последовательностями одного цвета, а не быстрым чередованием черных и белых. В итоге получится файл, начинающийся с 1 или 0 (с вероятностью 1/2). За нулем с большой вероятностью следует нуль, а за единицей единица. На рис. 1.9 изображен конечный автомат, иллюстрирующий эту ситуацию. Если биты объединять в группы, скажем, по 8 разрядов, то биты внутри группы будут коррелированы, но сами группы не будут иметь корреляцию с исходными пикселами. Если входной файл содержит, например, две соседние группы 00011100 и 00001110, то они будут кодироваться независимо, игнорируя корреляцию последних нулей первой группы и начальных нулей второй. Выбор длинных групп улучшает положение, но увеличивает число возможных групп, что влечет за собой увеличение памяти для хранения таблицы кодов и удлиняет время создания этой таблицы. (Напомним, что если группа длины увеличивается до длины , то число групп растет экспоненциально с до ).
  
  Рис. 1.9. Конечный автомат.
  
  Более сложный подход к сжатию изображений с помощью кодов Хаффмана основан на создании нескольких полных множеств кодов Хаффмана. Например, если длина группы равна 8 бит, то порождается несколько семейств кодов размера 256. Когда необходимо закодировать символ , выбирается одно семейство кодов, и кодируется из этого семейства.
  
  Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.
  
  Он поступил на факультет MIT в 1953 году. В 1967 году Хаффман перешел в университет Санта Круз на факультет компьютерных наук. Он играл заметную роль в развитии академической программы факультета и в подборе преподавателей, возглавляя его с 1970 по 1973 года. Выйдя на пенсию в 1994 году, Давид Хаффман продолжил свою научную деятельность в качестве заслуженного профессора в отставке, читая курсы по теории информации и по анализу сигналов. Он умер в 1999 году в возрасте 74 лет.
  
  (Анализ.) Двоичная запись 127 равна 01111111, а 128 - 10000000. Половина пикселов поверхности будет нулем, а вторая половина единицей. В самом плохом случае область будет походить на шахматную доску, то есть, иметь много серий длины 1. В этом случае каждая серия требует кода в 1 бит, что ведет к одному кодовому биту на пиксел на область, или 8 кодовых битов на пиксел для всего изображения. Это приводит к полному отсутствию сжатия. А коду Хаффмана для такого изображения понадобится всего два кода (поскольку имеется всего два разных пиксела), и они могут быть длины 1. Это приводит к одному кодовому биту на пиксел, то есть к восьмикратному сжатию.
  
  Один из первых алгоритмов эффективного кодирования информации был предложен Хаффманом в 1952 г. Этот алгоритм стал базой для большого количества программ сжатия информации. Например, кодирование по Хаффману используется в программах сжатия ARJ, ZIP, RAR, в алгоритме сжатия графических изображений с потерями JPEG, а также встроено в современные факс-аппараты.
  
  Построение кодового дерева Хаффмана
  
  Для иллюстрации алгоритма Хаффмана рассмотрим графический способ построения дерева кодирования. Перед этим введем некоторые определения, принятые для описания алгоритма Хаффмана с использованием этого способа.
  
  Граф - совокупность множества узлов и множества дуг, направленных от одного узла к другому.
  
  Дерево - граф, обладающий следующими свойствами:
  - • ни в один из узлов не входит более одной дуги;
  - • только в один узел нс входит ни одной дуги (этот узел называется корнем дерева);
  - • перемещаясь по дугам от корня, можно попасть в любой узел.
  Лист дерева - узел, из которого нс выходит ни одной дуги. В парс
  
  узлов дерева, соединенных между собой дугой, тог, из которого она выходит, называется родителем, другой - ребенком.
  
  Два узла называются братьями, если имеют одного и того же родителя.
  
  Двоичное дерево - дерево, у которого из всех узлов, кроме листьев, выходит ровно по две дуги.
  
  Дерево кодирования Хаффмана - двоичное дерево, у которого каждый узел имеет вес, и при этом вес родителя равен суммарному весу его детей. Алгоритм построения дерева кодирования Хаффмана таков:
  
  Теперь, двигаясь по кодовому дереву сверху вниз и последовательно выписывая двоичные цифры, соответствующие дугам, можно получить коды букв входного алфавита.
  
  Для примера рассмотрим построение дерева кодирования Хаффмана для приведенного в табл. 10.1 алфавита из восьми букв.
  
  Построение дерева начинаем со списка листьев (рис. 10.2) и выполняем по шагам.
  
  Рис. 10.2. Список свободных узлов-листьев
  
  На первом шаге из листьев дерева выбираются два с наименьшим весом - z₇ и zg. Они присоединяются к узлу-родителю, вес которого устанавливается в 0,04 + 0,02 = 0,06. Затем узлы z₇ и z₈ удаляются из списка свободных. Узел z₇ соответствует ветви 0 родителя, узел z₈ - ветви 1. Дерево кодирования после первого шага приведено на рис. 10.3.
  
  Рис. 10.3. Дерево кодирования Хаффмана после первого шага
  
  Рис. 10.4. Дерево кодирования Хаффмана после второго шага
  
  На третьем шаге наименьшие вероятности имеют zs, z*, Zj и свободный узел (zb + Zi+ z.g). Таким образом, на данном шаге можно создать родителя для z$ и (Zb + г₇ + г₈) с весом 0,26, получив при этом дерево кодирования, представленное на рис. 10.5. Обратите внимание, что в данной ситуации возможны несколько вариантов соединения узлов с наименьшими весами. При этом все такие варианты будут правильными, хотя и могут привести к различным наборам кодов, которые, впрочем, будут обладать одинаковой эффективностью для заданного распределения вероятностей.
  
  Рис. 10.5. Дерево кодирования Хаффмана после третьего шага
  
  Рис. 10.6. Дерево кодирования Хаффмана после четвертого шага
  
  Рис. 10.7. Дерево кодирования Хаффмана после пятого шага
  
  Рис. 10.8. Дерево кодирования Хаффмана после шестого шага
  
  На пятом шаге выбираем узлы с наименьшими весами 0,22 и 0,20. Дерево кодирования Хаффмана после пятого шага приведено на рис. 10.7.
  
  На шестом шаге остается три свободных узла с весами 0,42, 0,32 и 0,26. Выбираем наименьшие веса 0,32 и 0,26. Дерево кодирования Хаффмана после шестого шага приведено на рис. 10.8.
  
  На седьмом шаге остается объединить две оставшиеся свободные вершины, после чего получаем окончательное дерево кодирования Хаффмана, приведенное на рис. 10.9.
  
  Рис. 10.9. Окончательное дерево кодирования Хаффмана
  
  На основании построенного дерева буквы представляются кодами, отражающими путь от корневого узла до листа, соответствующего нужной букве. В рассмотренном примере буквы входного алфавита кодируются так, как показано в табл. 10.2.
  
  Рис. 10.10. Альтернативный вариант дерева кодирования Хаффмана
  
  Для заданных в табл. 10.1 вероятностей можно построить и другие правильные варианты кодового дерева Хаффмана. Одно из допустимых деревьев приведено на рис. 10.10. Коды букв входного алфавита для данного кодового дерева приведены в табл. 10.3.
  
  Из табл. 10.3 видно, что коды также получились префиксными, и наиболее вероятным буквам соответствуют наиболее короткие коды.
  
  Читайте также: