Код хаффмана


Содержание

Код хаффмана

Huffman — Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

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

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже.

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из «узлов» D и A новый «узел», частота вхождения для которого будет равна сумме частот D и A :

Номер в рамке — сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый «узел» с суммарной частотой вхождения. Самая низкая частота теперь у F и нового «узла». Снова сделаем операцию слияния узлов :

Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все «дерево» не сформировано, т.е. пока все не сведется к одному узлу.

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всенда начнинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C — 00. Для следующего символа ( А ) у нас получается — лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим

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

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

В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11. 4 байта 11 раз — 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику — наша таблица будет приблизительно 50 байтов длинны.

Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт — мы получили 20% сжатие информации.

Не плохо. То что мы действительно выполнили — трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.

Что мы можем получить на этом пути ?

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

Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.

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

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

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

Код хаффмана

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

При кодировании по Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписывают кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11. В результате многократного повторения процедуры разделения вероятностей и образования вершин приходим к ситуации, когда в качестве веса, приписанного ребру бинарного дерева, выступает вероятность одного из данных сообщений. В этом случае вновь образованная вершина оказывается листом дерева, т.к. процесс деления вероятностей для нее завершен. Задача кодирования считается решенной, когда на всех ветвях кодового бинарного дерева образуются листья.

Пример 151. Закодировать по Фано сообщения, имеющие следующие вероятности:

сообщение 1 2 3 4 5 6 7
вероятность 0,4 0,2 0,1 0,1 0,1 0,05 0,05

Решение 1 (с использованием кодового дерева)

Листья кодового дерева представляют собой кодируемые сообщения с присвоенными им кодовыми словами.

Решение 2 (табличный способ)

Цена кодирования (средняя длина кодового слова является критерием степени оптимальности кодирования. Вычислим ее в нашем случае.

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

Пример 152. Закодировать сообщения из предыдущего примера по методу Хаффмана.

Решение 1. Первый шаг

Вторым шагом производим кодирование, «проходя» по таблице справа налево (обычно это проделывается в одной таблице):

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

Листья кодового дерева представляют собой кодируемые сообщения с присвоенными им кодовыми словами. Таблица кодов имеет вид:

сообщение 1 2 3 4 5 6 7
код 1 01 0010 0011 0000 00010 00011

Цена кодирования здесь будет равна

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

Пример 153. Провести кодирование по методу Фано двухбуквенных комбинаций, когда алфавит состоит из двух букв и , имеющих вероятности = 0,8 и = 0,2.

Цена кода , и на одну букву алфавита приходится 0,78 бита информации. При побуквенном кодировании на каждую букву приходится следующее количество информации:

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

Построим кодовое дерево.

Найдем цену кодирования

На каждую букву алфавита приходится в среднем 0,728 бита, в то время как при побуквенном кодировании — 0,72 бита.

Большей оптимизации кодирования можно достичь еще и использованием трех символов — 0, 1, 2 — вместо двух. Тринарное дерево Хаффмана получается, если суммируются не две наименьшие вероятности, а три, и приписываются каждому левому ребру 0, правому — 2, а серединному — 1.

Пример 155. Построить тринарное дерево Хаффмана для кодирования трехбуквенных комбинаций из примера 153 .

Решение. Составим таблицу тройного «сжатия» по методу Хаффмана

Тогда тринарное дерево выглядит следующим образом:

Вопросы для самоконтроля

1. Как определяется среднее число элементарных сигналов, приходящихся на одну букву алфавита?

2. Префиксные коды.

3. Сколько требуется двоичных знаков для записи кодированного сообщения?

4. На чем основано построение кода Фано?

5. Что такое сжатие алфавита?

6. Какой код самый выгодный?

7. Основная теорема о кодировании.

8. Энтропия конкретных типов сообщений.

I 301. Проведите кодирование по методу Фано алфавита из четырех букв, вероятности которых равны 0,4; 0,3; 0,2 и 0,1.

302. Алфавит содержит 7 букв, которые встречаются с вероятностями 0,4; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05. Осуществите кодирование по методу Фано.

303. Алфавит состоит из двух букв, и , встречающихся с вероятностями = 0,8 и = 0,2. Примените метод Фано к кодированию всевозмож-ных двухбуквенных и трехбуквенных комбинаций.

304. Проведите кодирование по методу Хаффмана трехбуквенных слов из предыдущей задачи.

305. Проведите кодирование 7 букв из задачи 302 по методу Хаффмана.

306. Проведите кодирование по методам Фано и Хаффмана пяти букв, равновероятно встречающихся.

II 307. Осуществите кодирование двухбуквенных комбинаций четырех букв из задачи 301.

308. Проведите кодирование всевозможных четырехбуквенных слов из задачи 303.

III 309. Сравните эффективность кодов Фано и Хаффмана при кодировании алфавита из десяти букв, которые встречаются с вероятностями 0,3; 0,2; 0,1; 0,1; 0,1; 0,05; 0,05; 0,04; 0,03; 0,03.

310. Сравните эффективность двоичного кода Фано и кода Хаффмана при кодировании алфавита из 16 букв, которые встречаются с вероятностями 0,25; 0,2; 0,1; 0,1; 0,05; 0,04; 0,04; 0,04; 0,03; 0,03; 0,03; 0,03; 0,02; 0,02; 0,01; 0,01.

КОДЫ ХАФФМАНА

Читайте также:

  1. Код Хаффмана
  2. Метод Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности, что позволяет однозначно их декодировать. В отличие от кодов Шеннона – Фано, которые в настоящее время практически не применяются, коды Хаффмана находят широкое применение при кодирование сообщений [1-3, 5, 7].

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

Рассмотрим алгоритм построения кодов Хаффмана на следующем примере: пусть имеется источник с алфавитом X, включающий шесть сообщений x1x6. У каждого сообщения имеется своя вероятность появления, приведенная в таблице 5.

Вероятность появления сообщений источника информации

Сообщения источника x1 x2 x3 x4 x5 x6
Вероятность появления сообщения 0,3 0,2 0,15 0,15 0,1 0,1


1. Выбираем два сообщения с наименьшими вероятностями и заменяем их одним с вероятностью равной сумме вероятности данных сообщения (выбранные сообщения выделяем темным цветом), таблица 6:

Формирование промежуточных алфавитов

x1 x2 x3 x4 x5 x6
Объединяем сообщения 0,3 0,2 0,15 0,15 0,1 0,1
Упорядочиваем по вероятности появления 0,3 0,2 0,2 0,15 0,15
Объединяем сообщения 0,3 0,2 0,2 0,15 0,15
Упорядочиваем по вероятности появления 0,3 0,3 0,2 0,2
Объединяем сообщения 0,3 0,3 0,2 0,2
Упорядочиваем по вероятности появления 0,4 0,3 0,3
Объединяем сообщения 0,4 0,3 0,3
Упорядочиваем по вероятности появления 0,6 0,4
Объединяем сообщения 0,6 0,4

2. В результате проведенных операций мы получили 4 промежуточных алфавита (X1X4). Результат перепишем в следующем виде, таблица 7:

Вероятности
Исходный алфавит X Промежуточные алфавиты
X1 X2 X3 X4
0,3 0,3 0,3 0,4 0,6
0,2 0,2 0,3 0,3 0,4
0,15 0,2 0,2 0,3
0,15 0,15 0,2
0,1 0,15
0,1

3. Далее проведем процедуру кодирования, таблица 8. Кодирование выполняется в обратном порядке от алфавита X4 к исходному алфавиту X.

Двум знакам последнего алфавита X4 присваиваем коды 0 (сообщение с вероятностью 0,6) и 1 (сообщение с вероятностью 0,4). Условимся в дальнейшем, что верхний знак будет кодироваться символом 0, а нижний – 1.

Сообщение с вероятностью 0,6 алфавита X4 было получено как сумма вероятностей 2-ух сообщений алфавита X3 с вероятностями 0,3 и 0,3. В данном случае эти сообщения кодируются уже двухразрядным кодом. Старшим разрядам обоих сообщений присваивается 0, так как нулем было закодировано сообщение с вероятностью 0,6 алфавита X4. Младшему разряду верхнего сообщения в таблице присваивается 0, а нижнему – 1 (было определено выше). Сообщение с вероятностью 0,4 алфавита X3 будет кодироваться также как и сообщение с этой же вероятностью в алфавите X4.

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

Вероятности
Исходный алфавит X Промежуточные алфавиты
X1 X2 X3 X4
0,3 (00) 0,3 (00) 0,3 (00) 0,4 (1) 0,6 (0)
0,2 (10) 0,2 (10) 0,3 (01) 0,3 (00) 0,4 (1)
0,15 (010) 0,2 (11) 0,2 (10) 0,3 (01)
0,15 (011) 0,15 (010) 0,2 (11)
0,1 (110) 0,15 (011)
0,1 (111)

Пример 7.Закодируем русский алфавит с помощью описанного выше алгоритма Хаффмана, используя таблицу 1.

Решение:Результат кодирования приведен в таблице 9.

Результат кодирования букв русского алфавита кодом Хаффмана

Буква Двоичное число Буква Двоичное число Буква Двоичное число
«−» о е а и т н с р в л к м д п у я ы з ъ, ь б г ч й х ж ю ш ц щ э ф

Пример 8.Пусть по каналу связи получено сообщение (слово на русском языке) закодированное кодом Хаффмана: 10001101001111011010110.

Необходимо декодировать данную последовательность, используя таблицу 9.

Решение:Процесс декодирования основывается также на свойстве префиксности кода и выполняется слева на право, таблица 10.

Процесс декодирования сообщения

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

Можно повысить эффективность кодирования, если строить код не для символа, как в рассмотренных выше примерах, а для блоков из n символов. В этом случае частота блока рассчитывается как произведение частот символов, которые входят в блок.

Дата добавления: 2015-07-02 ; Просмотров: 863 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Коды Хаффмана

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

Рис. 1.5. Дерево кодирования Хаффмана: • — точки ветвления; над ветвями показаны вероятности их появления; а, Ь, с, с1, е, / — символы алфавита источника

Код каждого символа алфавита находится при движении по ветвям дерева, начиная от исходного символа до выхода из дерева. Количество бит в коде символа определяется количеством точек ветвления, встречающихся при этом движении. В соответствующий бит ставится «1» тогда, когда в точку ветвления заходят сверху. В противном случае записывается «О». Пример составления коды Хаффмана приведен на рис. 1.5 и в табл. 1.2.

Таблица 1.2. Пример составления кода Хаффмана

Экономное кодирование информации по алгоритму Хаффмана

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

Илон Маск рекомендует:  Что такое fluke

Алгоритм Хаффмана

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

Например, при экономном кодировании символьной информации часто встречаемые символы кодируются короткими кодами, в то время как редко встречающиеся — длинными.

Префиксные коды и алгоритмы их получения подробно описаны в монографии Семенюка В. В. «Экономное кодирование дискретной информации » [1].

Алгоритм Хаффмана для двоичной системы

  1. Вычисляем вероятность появления каждого символа в информации
  2. Каждому символу присваивается значение равное его частоте вхождения
  3. Полученный список элементов (пара символ — значение) сортируется по убыванию: от часто встречаемых к менее встречаемым
  4. Два последних элемента списка объединяются в новый элемент, значение которого равно сумме значений вошедших в него элементов, т.е. вместо двух последних элементов записывается новый
  5. Новый список сортируется по убыванию
  6. Операции 4, 5 выполняются до тех пор? пока не останется один элемент
  7. Выписывается последний оставшейся элемент
  8. От него откладывают две ветви с элементами, которые его составляют
  9. От каждого элемента, если он не является символом, откладываются такие же две ветви с входящими в него элементами
  10. Процесс выполняется до тех пор, пока все элементы не будут выписаны
  11. Каждому ребру назначается коды 0 и 1
  12. Для каждого символа (не элемента) в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу

Особенности алгоритма Хаффмана для троичной системы

Алгоритмы Хаффмана для двоичной и троичной системы аналогичны.

Однако есть ряд отличий и особенностей.

Так, вместо объедения двух последних элементов, при кодировании в троичной системе объединяются три.

Так как объединяется нечётное количество элементов, в некоторых случаях может оказаться, что при последнем объедении будут объединяться не три, а только два элемента, что повлечёт серьёзные потери в эффективности. Это связано с тем одна из самых верхней ветвей окажется пустой. Существует способ переместить пустую ветвь на самый низкий уровень, что позволит полностью избежать потери в эффективности. Для этого необходимо учитывать количество элементов в первоначальном списке. В случае если количество элементов чётное, то на первом шаге необходимо объединять не три, а два элемента (на следующих шаг объединяются три). Таким образом, пустая ветвь будет на самом низком уровне, где находятся самые редко встречаемые элементы. В случае если количество элементов в первоначальном списке нечётно, то и на первом шаге объединяется три элемента.

Доказательство. Так как при объединении трех элементов одним получаем список меньше предыдущего на два элемента и, учитывая условие, что на последнем этапе необходимо, чтобы объединилось три элемента, получим, что эффективно будет кодироваться список 3+2·k элементами, т.е. с нечётным количеством элементов. Поэтому при четном количестве элементов — 3 + 2k + 1 — первоначально объединяются два элемента, т.е. получаем список с (3 + 2k) элементов — с нечетным количеством элементов.

Алгоритм Хаффмана для троичной системы

  1. Вычисляем вероятность появления каждого символа в информации
  2. Каждому символу присваивается значение равное его частоте вхождения
  3. Полученный список элементов (пара символ — значение) сортируется по убыванию: от часто встречаемых к менее встречаемым
  4. Определяется количество элементов в списке
  5. Если количество элементов чётно, то в новый элемент объединяются два последних элемента списка, если количество нечётно — объединяются три элемента, значение нового элемента равно сумме значений вошедших в него элементов
  6. Новый список сортируется по убыванию
  7. Три последних элемента объединяются в новый
  8. Новый список сортируется по убыванию
  9. Операции 7,8 выполняются до тех пор, пока не останется один элемент
  10. Выписывается последний оставшейся элемент
  11. От него откладывают три ветви с элементами, которые его составляют
  12. От каждого элемента, если он не является символом, откладываются такие же три ветви с входящими в него элементами.
  13. Процесс выполняется до тех пор, пока все элементы не будут выписаны
  14. Каждому ребру назначается коды -, 0 и +
  15. Для каждого символа (не элемента) в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу

Построение двоичного и троичного кодового дерева

Рассмотрим построения двоичного и троичного кодовых деревьев по алгоритму Хаффмана.

Кодируемое сообщение: «ГОЛОГРАММА».

Статистика появления символов в сообщении: Г(2), О(2), Л(1), Р(1), A(2), М(2).

Упорядоченный список: A(2), Г(2), М(2), О(2), Л(1), Р(1).


Двоичное дерево Хаффмана

Троичное дерево Хаффмана

Примечание. Список состоит из 6 элементов — количество четное — на первом шаге объединяем только два последних элемента.

Кодирование в двоичной системе Кодирование в троичной системе
Символ Частота Двоичная система Троичная система
Префиксный код Длина кода Сумма Префиксный код Длина кода Сумма
А 2 10 2 4 1 2
Г 2 11 2 4 2 4
М 2 000 3 6 -0 2 4
О 2 001 3 6 -+ 2 4
Л 1 010 3 3 +- 2 2
Р 1 011 3 3 +0 2 2
Итого: 26 Итого: 18

Сравнение алгоритма для двоичной и троичной систем

Оценим количество шагов для построения деревьев.

Кодирование в двоичной системе Кодирование в троичной системе
Пусть L = 2n (n — натуральное число) — количество элементов в первоначальном списке, K — количество шагов (K — натуральное число). На каждом шаге происходит объединение 2-х элементов в 1, — список с каждым шагом уменьшается на 1 элемент. Таким образом, на предпоследнем шаге останется 2 элемента, т.е. L-(K-1) = 2. Таким образом, K = L – 1 = 2n -1. Первоначально рассмотрим случай, когда количество элементов в первоначальном списке чётно, L = 2n (n — натуральное число) — количество элементов в первоначальном списке, K — количество шагов (K — натуральное число). На каждом шаге происходит объединение 3-х элементов в 1, т.е. список с каждым шагом уменьшается на 1 элемент. Однако в соответствии с оптимальным алгоритмом на первом шаге необходимо объединять в один элемент 2, а не 3. Будем считать, что первый шаг выполнен, было объединено только 2 элемента в 1 (L-1). Таким образом, на предпоследнем шаге останется 3 элемента, т.е. L-2*(K-2) — 1= 3. Таким образом, K = L – 1 = 2n -1.

Оценим эффективность построения деревьев.

Кодирование в двоичной системе Кодирование в троичной системе
Каждый уровень дерева может содержать до 2 n элементов, где n ― номер уровня, т.е. 1-ый уровень содержит 2 элемента, 2-ой ― 4, 3-ий ― 8, 10-ый уровень может содержать уже 2 10 , т.е 1024 элементов. Каждый уровень дерева может содержать до 3 n элементов. Таким образом, 10-ый уровень может содержать 3 10 , т.е 59049 элементов.

Порядок уровня определяет длину префиксного кода. Например, длина префиксных кодов элементов 1-го уровня равна 1, 7-ого ― 7 . Соответственно, чем меньше уровней будет в дереве, тем более экономичным будет кодирование.

Рассмотрим случай, когда все кодируемые элементы располагаются на последнем уровне, случай, когда первоначально все элементы имеют одинаковый вес.

Так на 9-й уровень при кодировании в троичной системе может содержать до 19683 элементов, при кодировании в двоичной системе 9-й уровень может содержать только 512. Лишь 14-й уровень будет содержать примерно такое же количество элементов (15-й уровень будет уже содержать большее, чем 9-й при троичном кодировании). Относительную эффективность можно оценить по соотношению уровней. Из приведённой ниже таблицы видно, что, в среднем, кодирование в троичной системе эффективнее в 1,5 раза чем в двоичной.

Кодирование в троичной системе Кодирование в двоичной системе Соотношение
Уровень Максимальное количество элементов Уровень Максимальное количество элементов
1 3 1 2 1.000
2 9 3 8 1.500
3 27 4 16 1.333
4 81 6 64 1.500
5 243 7 128 1.400
6 729 9 512 1.500
7 2187 11 2048 1.571
8 6561 12 4096 1.500
9 19683 14 16384 1.556
10 59049 15 32768 1.500
11 177147 17 131072 1.545
12 531441 19 524288 1.583
13 1594323 20 1048576 1.538
14 4782969 22 4194304 1.571
15 14348907 23 8388608 1.533
16 43046721 25 33554432 1.562
17 129140163 26 67108864 1.529
18 387420489 28 268435456 1.556
19 1162261467 30 1073741824 1.579
20 3486784401 31 2147483648 1.550
21 10460353203 33 8589934592 1.571
22 31381059609 34 17179869184 1.545
23 94143178827 36 68719476736 1.565
24 282429536481 38 274877906944 1.583
25 847288609443 39 549755813888 1.560
26 2541865828329 41 2199023255552 1.577
27 7625597484987 42 4398046511104 1.556
28 22876792454961 44 17592186044416 1.571
29 68630377364883 45 35184372088832 1.552

Выводы

Построение троичного дерева в два раза быстрее (по количеству шагов) и в полтора раза эффективнее (по длине кодов), чем двоичное дерево.

Код хаффмана

Кодирование Хаффмана. Часть 1.
Вступление
Здравствуй, дорогой читатель! В данной статье будет рассмотрен один из способов сжатия данных. Этот способ является достаточно широко распространённым и заслуживает определённого внимания. Данный материал рассчитан по объёму на три статьи, первая из которых будет посвящена алгоритму сжатия, вторая — программной реализации алгоритма, а третья ― декомпрессии. Алгоритм сжатия будет написан на языке C++, алгоритм декомпрессии ― на языке Assembler.
Однако, перед тем, как приступить к самому алгоритму, следует включить в статью немного теории.
Немного теории
Компрессия (сжатие) ― способ уменьшения объёма данных с целью дальнейшей их передачи и хранения.
Декомпрессия ― это способ восстановления сжатых данных в исходные.
Компрессия и декомпрессия могут быть как без потери качества (когда передаваемая/хранимая информация в сжатом виде после декомпрессии абсолютно идентична исходной), так и с потерей качества (когда данные после декомпрессии отличаются от оригинальных). Например, текстовые документы, базы данных, программы могут быть сжаты только способом без потери качества, в то время как картинки, видеоролики и аудиофайлы сжимаются именно за счёт потери качества исходных данных (характерный пример алгоритмов ― JPEG, MPEG, ADPCM), при порой незаметной потере качества даже при сжатии 1:4 или 1:10.
Выделяются основные виды упаковки:

  • Десятичная упаковка предназначена для упаковки символьных данных, состоящих только из чисел. Вместо используемых 8 бит под символ можно вполне рационально использовать всего лишь 4 бита для десятичных и шестнадцатеричных цифр, 3 бита для восьмеричных и так далее. При подобном подходе уже ощущается сжатие минимум 1:2.
  • Относительное кодирование является кодированием с потерей качества. Оно основано на том, что последующий элемент данных отличается от предыдущего на величину, занимающую в памяти меньше места, чем сам элемент. Характерным примером является аудиосжатие ADPCM (Adaptive Differencial Pulse Code Modulation), широко применяемое в цифровой телефонии и позволяющее сжимать звуковые данные в соотношении 1:2 с практически незаметной потерей качества.
  • Символьное подавление — способ сжатия информации, при котором длинные последовательности из идентичных данных заменяются более короткими.
  • Статистическое кодирование основано на том, что не все элементы данных встречаются с одинаковой частотой (или вероятностью). При таком подходе коды выбираются так, чтобы наиболее часто встречающемуся элементу соответствовал код с наименьшей длиной, а наименее частому ― с наибольшей.

Кроме этого, коды подбираются таким образом, чтобы при декодировании можно было однозначно определить элемент исходных данных. При таком подходе возможно только бит-ориентированное кодирование, при котором выделяются разрешённые и запрещённые коды. Если при декодировании битовой последовательности код оказался запрещённым, то к нему необходимо добавить ещё один бит исходной последовательности и повторить операцию декодирования. Примерами такого кодирования являются алгоритмы Шеннона и Хаффмана, последний из которых мы и будем рассматривать.
Конкретнее об алгоритме
Как уже известно из предыдущего подраздела, алгоритм Хафмана основан на статистическом кодировании. Разберёмся поподробнее в его реализации.
Пусть имеется источник данных, который передаёт символы [math](a_1, a_2, . a_n)[/math] с разной степенью вероятности, то есть каждому [math]a_i[/math] соответствует своя вероятность (или частота) [math]P_i(a_i)[/math] , при чём существует хотя бы одна пара [math]a_i[/math] и [math]a_j[/math] , [math]i\ne j[/math] , такие, что [math]P_i(a_i)[/math] и [math]P_j(a_j)[/math] не равны. Таким образом образуется набор частот [math][/math] , при чём [math]\displaystyle \sum_^ P_i(a_i)=1[/math] , так как передатчик не передаёт больше никаких символов кроме как [math][/math] .
Наша задача ― подобрать такие кодовые символы [math][/math] с длинами [math][/math] , чтобы средняя длина кодового символа не превышала средней длины исходного символа. При этом нужно учитывать условие, что если [math]P_i(a_i)>P_j(a_j)[/math] и [math]i\ne j[/math] , то [math]L_i(b_i)\le L_j(b_j)[/math] .
Хафман предложил строить дерево, в котором узлы с наибольшей вероятностью наименее удалены от корня. Отсюда и вытекает сам способ построения дерева:
1. Выбрать два символа [math]a_i[/math] и [math]a_j[/math] , [math]i\ne j[/math] , такие, что [math]P_i(a_i)[/math] и [math]P_j(a_j)[/math] из всего списка [math][/math] являются минимальными.
2. Свести ветки дерева от этих двух элементов в одну точку с вероятностью [math]P=P_i(a_i)+P_j(a_j)[/math] , пометив одну ветку нулём, а другую ― единицей (по собственному усмотрению).
3. Повторить пункт 1 с учётом новой точки вместо [math]a_i[/math] и [math]a_j[/math] , если количество получившихся точек больше единицы. В противном случае мы достигли корня дерева.
Теперь попробуем воспользоваться полученной теорией и закодировать информацию, передаваемую источником, на примере семи символов.
Разберём подробно первый цикл. На рисунке изображена таблица, в которой каждому символу [math]a_i[/math] соответствует своя вероятность (частота) [math]P_i(a_i)[/math] . Согласно пункту 1 мы выбираем два символа из таблицы с наименьшей вероятностью. В нашем случае это [math]a_1[/math] и [math]a_4[/math] . Согласно пункту 2 сводим ветки дерева от [math]a_1[/math] и [math]a_4[/math] в одну точку и помечаем ветку, ведущую к [math]a_1[/math] , единицей, а ветку, ведущую к [math]a_4[/math] ,― нулём. Над новой точкой приписываем её вероятность (в данном случае ― 0.03) В дальнейшем действия повторяются уже с учётом новой точки и без учёта [math]a_1[/math] и [math]a_4[/math] .

Код Хаффмана. Как распаковать таблицы, сжатые Huffman Encoding, в Intel ME 11.x

Содержание статьи

Предыдущие версии ME

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

Также примечательны следующие свойства:

  • Для разных наборов таблиц диапазоны длин кодовых слов различаются (7–19 и 7–15 бит включительно).
  • Каждая кодовая последовательность кодирует целое количество байтов (от 1 до 15 включительно).
  • В обоих наборах используется Canonical Huffman Coding (это позволяет быстро определять длину очередного кодового слова при распаковке).
  • В пределах одного набора длины закодированных значений для любого кодового слова совпадают во всех таблицах (Code и Data).

Постановка задачи

Можно предположить, что в таблицах Хаффмана для ME 11.x три последних свойства также соблюдаются. Тогда для полного восстановления таблиц требуется найти следующее:

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

Разбиение сжатых данных на отдельные страницы

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

Разобрав Lookup Table, часть Code Partition Directory, легко определить, для каких модулей применяется кодирование Хаффмана, где начинаются их упакованные данные и какой размер модуль будет иметь после распаковки.

Размер сжатых и распакованных данных и SHA-256 от распакованных данных несложно найти, разобрав Module Attributes Extension для конкретного модуля.

Беглый анализ нескольких прошивок для ME 11.x позволяет заметить, что размер данных после распаковки Хаффманом всегда кратен размеру страницы (4096 == 0x1000 байт). В начале упакованных данных располагается массив четырехбайтовых целочисленных значений. Количество элементов массива соответствует количеству страниц в распакованных данных.

Например, для модуля размером 81920 == 0x14000 байт массив будет занимать 80 == 0x50 байт и состоять из 20 == 0x14 элементов.

В двух старших битах каждого из Little-Endian-значений хранится номер таблицы (0b01 для кода и 0b11 для данных). В оставшихся 30 битах хранится смещение начала сжатой страницы относительно конца массива смещений. Приведенный выше фрагмент описывает 20 страниц:

Примечательно, что смещения упакованных данных для каждой страницы отсортированы по возрастанию, а размер упакованных данных для каждой страницы в явном виде нигде не фигурирует. В приведенном выше примере упакованные данные для каждой конкретной страницы начинаются на границе, кратной 64 = 0x40 байтам, а неиспользуемые области заполнены нулями. Но по другим модулям можно установить, что выравнивание не обязательно. Это наталкивает на мысль, что распаковщик останавливается, когда объем данных распакованной страницы достигает 4096 байт.

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

На скриншоте видно, что последняя сжатая страница (начинающаяся по смещению 0xFA40) состоит из байта 0xB2 == 0b10110010, за которым идет 273 байта со значением 0xEC == 0b11101100, и дальше — только нули. Так как битовая последовательность 11101100 (или 01110110) повторяется 273 раза, можно предположить, что она кодирует 4096/273 == 15 одинаковых байт (скорее всего, со значениями 0x00 или 0xFF). Тогда битовая последовательность 10110010 (или 1011001) кодирует 4096-273*15 == 1 байт.

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

Нахождение пар «сжатый текст — открытый текст»

Как было показано ранее, в разных версиях прошивок для ME 11 модули с одинаковыми названиями могут упаковываться разными алгоритмами. Если разобрать Module Attributes Extension для одноименных модулей, упакованных как LZMA, так и Хаффманом, и извлечь значения SHA-256 для каждого модуля, то не обнаружится ни одной пары модулей, упакованных разными алгоритмами и имеющих одинаковые значения хешей.

Но если вспомнить, что для модулей, упакованных LZMA, SHA-256 обычно считается от сжатых данных, и посчитать SHA-256 для модулей после распаковки LZMA, то обнаружится достаточно много подходящих пар. И для каждого такого «парного» модуля мы сразу получим несколько пар страниц — в упакованном Хаффманом и распакованном виде.

Продолжение доступно только участникам

Вариант 1. Присоединись к сообществу «Xakep.ru», чтобы читать все материалы на сайте

Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», увеличит личную накопительную скидку и позволит накапливать профессиональный рейтинг Xakep Score! Подробнее

Алфавитное неравномерное двоичное кодирование. Код Хаффмана

На этом шаге мы рассмотрим алфавитное неравномерное двоичное кодирование; префиксный код; код Хаффмана.

Равномерное кодирование удобно для декодирования. Однако часто применяют и неравномерные коды, т.е. коды с различной длиной кодовых слов. Это полезно, когда в исходном тексте разные буквы встречаются с разной частотой. Тогда часто встречающиеся символы стоит кодировать более короткими словами, а редкие – более длинными. Из примера 1 видно, что (в отличие от равномерных кодов!) не все неравномерные коды допускают однозначное декодирование.

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

Код называется префиксным, если в нем нет ни одного кодового слова, которое было бы началом (по-научному, — префиксом) другого кодового слова.

Код из примера 1 – НЕ префиксный, так как, например, код буквы А (т.е. кодовое слово 1) – префикс кода буквы К (т.е. кодового слова 12, префикс выделен жирным шрифтом).

Код из примера 2 (и любой другой равномерный код) – префиксный: никакое слово не может быть началом слова той же длины.

Пример . Пусть исходный алфавит включает 9 символов: А, Л, М, О, П, Р, У, Ы, -. Кодовый алфавит – двоичный. Кодовые слова:

А: 00 М: 01 -: 100 Л: 101 У: 1100 Ы: 1101 Р: 1110 О: 11110 П: 11111

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

На рисунке изображено бинарное дерево. Его корень расположен слева. Из каждого внутреннего узла выходит два ребра. Верхнее ребро имеет пометку 0, нижнее – пометку 1. Таким образом, каждому узлу соответствует слово в двоичном алфавите. Если слово X является началом (префиксом) слова Y, то узел, соответствующий слову X, находится на пути из корня в узел, соответствующий слову Y. Наши кодовые слова находятся в листьях дерева. Поэтому ни одно из них не является началом другого.

Символы некоторого первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита (т.е. 0 и 1), причем, длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковы ( = 1 = ). За счет чего можно оптимизировать кодирование в этом случае? Очевидно, суммарная длительность сообщения будет меньше, если применить следующий подход: тем буквам первичного алфавита, которые встречаются чаще, присвоить более короткие по длительности коды, а тем, относительная частота которых меньше – коды более длинные. Но длительность кода – величина дискретная, она кратна длительности сигнала передающего один символ двоичного алфавита. Следовательно, коды букв, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов. Построим кодовую таблицу для букв русского алфавита, основываясь на приведенных ранее вероятностях появления отдельных букв.

Очевидно, возможны различные варианты двоичного кодирования, однако, не все они будут пригодны для практического использования – важно, чтобы закодированное сообщение могло быть однозначно декодировано, т.е. чтобы в последовательности 0 и 1, которая представляет собой многобуквенное кодированное сообщение, всегда можно было бы различить обозначения отдельных букв. Проще всего этого достичь, если коды будут разграничены разделителем – некоторой постоянной комбинацией двоичных знаков. Условимся, что разделителем отдельных кодов букв будет последовательность 00 (признак конца знака), а разделителем слов – 000 (признак конца слова – пробел). Довольно очевидными оказываются следующие правила построения кодов:

  • код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);
  • коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);
  • код буквы (кроме пробела) всегда должен начинаться с 1;
  • разделителю слов (000) всегда предшествует признак конца знака; при этом реализуется последовательность 00000 (т.е. если в конце кода встречается комбинация …000 или …0000, они не воспринимаются как разделитель слов); следовательно, коды букв могут оканчиваться на 0 или 00 (до признака конца знака).

Длительность передачи каждого отдельного кода ti, очевидно, может быть найдена следующим образом: ti = ki , где ki – количество элементарных сигналов (бит) в коде символа i. В соответствии с приведенными выше правилами получаем следующую таблицу кодов:

Таблица 1. Таблица кодов
Буква Код pi·10 3 ki Буква Код pi·10 3 ki
пробел я
о ы
е з
а ь,ъ
и б
т г
н ч
с й
р х
в ж
л ю
к ш
м ц
д щ
п э
у ф

Теперь по формуле можно найти среднюю длину кода K (2) для данного способа кодирования:

Поскольку для русского языка, I1 (r) =4,356 бит, избыточность данного кода, согласно (2), составляет:

Q (r) = 1 — 4,356/4,964 0,122;

это означает, что при данном способе кодирования будет передаваться приблизительно на 12% больше информации, чем содержит исходное сообщение. Аналогичные вычисления для английского языка дают значение K (2) = 4,716, что приI1 (e) = 4,036 бит приводят к избыточности кода Q (e) = 0,144.

Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.


Пример. Пусть имеется следующая таблица префиксных кодов:

Таблица 2. Таблица кодов
а л м р у ы

Требуется декодировать сообщение: 00100010000111010101110000110.

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

1. Отрезать от текущего сообщения крайний левый символ, присоединить к рабочему кодовому слову.

2. Сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (1).

3. Декодировать рабочее кодовое слово, очистить его.

4. Проверить, имеются ли еще знаки в сообщении; если «да», перейти к (1).

Применение данного алгоритма дает:

Доведя процедуру до конца, получим сообщение: «мама мыла раму».

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

Способ оптимального префиксного двоичного кодирования был предложен Д.Хаффманом. Построение кодов Хаффмана мы рассмотрим на следующем примере: пусть имеется первичный алфавит A, состоящий из шести знаков a1, . a6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит A1, объединив два знака с наименьшими вероятностями (a5 и a6) и заменив их одним знаком (например, a (1) ); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т.е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что число таких шагов будет равно N – 2, где N – число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:

Теперь в обратном направлении поведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой – роли не играет; условимся, что верхний знак будет иметь код 0, а нижний – 1). В нашем примере знак a1 (4) алфавита A (4) , имеющий вероятность 0,6 , получит код 0, а a2 (4) с вероятностью 0,4 – код 1. В алфавите A (3) знак a1 (3) с вероятностью 0,4 сохранит свой код (1); коды знаков a2 (3) и a3 (3) , объединенных знаком a1 (4) с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра – как условились – у верхнего 0, у нижнего – 1; таким образом, a2 (3) будет иметь код 00, а a3 (3) – код 01. Полностью процедура кодирования представлена в следующей таблице:

Из самой процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода при этом оказывается:

Для сравнения можно найти I1 (A) – она оказывается равной 2,409, что соответствует избыточности кода Q = 0,0169, т.е. менее 2%.

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

Применение описанного метода для букв русского алфавита дает следующие коды:

Таблица 3. Таблица кодов русских букв
Буква Код pi·10 3 ki Буква Код pi·10 3 ki
пробел я
о ы
е з
а ь,ъ
и б
т г
н ч
с й
р х
в ж
л ю
к ш
м ц
д щ
п э
у ф

Средняя длина кода оказывается равной K (2) = 4,395; избыточность кода Q (r) = 0,00887, т.е. менее 1%.

Таким образом, можно заключить, что существует метод построения оптимального неравномерного алфавитного кода. Не следует думать, что он представляет число теоретический интерес. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.

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

голец Freq Код
пространство 7 111
a 4 010
е 4 000
е 3 1101
час 2 1010
я 2 1000
м 2 0111
N 2 0010
s 2 1011
T 2 0110
L 1 11001
о 1 00110
п 1 10011
р 1 11 000
U 1 00111
Икс 1 10010

В информатике и теории информации , код Хаффмана является конкретным типом оптимального кода префикса , который обычно используется для сжатия данных без потерь . Процесс поиска и / или с использованием такого кода доходов с помощью кодирования Хаффмана , алгоритм , разработанный David A. Huffman , когда он был д.т.н. студент MIT , и опубликовано в 1952 г. статьи «Метод строительство с минимальной избыточностью кодов».

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

содержание

история

В 1951 году Дэвид Хаффман и его MIT теория информации одноклассники получили выбор курсовой работы или окончательного экзамена . Профессор, Роберт М. Фано , присваивается курсовую по проблеме поиска наиболее эффективного двоичного кода. Хаффман, не в состоянии доказать , какие коды были наиболее эффективными, собирался сдаваться и начать обучение в финале , когда он ударил по идее использования частотно-отсортирован бинарное дерево и быстро доказал этот метод является наиболее эффективным.

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

терминология

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

Определение проблемы

Неформальное описание

Формализованное описание

Ввод .
Алфавит , который является символом алфавита размера . Кортеж , который является кортежем весов (положительные) символов ( как правило , пропорциональной вероятность), то есть . Выход . Код , который является кортежем (бинарных) кодовых слов, где это кодовое слово для . Цель . Пусть взвешенная длина пути кода . Условие: для любого кода . A = ( a 1 , a 2 , ⋯ , a n ) <\displaystyle A=(a_<1>,a_<2>,\cdots ,a_)> n <\displaystyle n>
W = ( w 1 , w 2 , ⋯ , w n ) <\displaystyle W=(w_<1>,w_<2>,\cdots ,w_)> w i = w e i g h t ( a i ) , 1 ≤ i ≤ n <\displaystyle w_=\mathrm \left(a_\right),1\leq i\leq n>

пример

Приведем пример результата кодирования Хаффмана для кода с пятью символами и заданными весами. Мы не будем проверять , что сводит к минимуму L по всем кодам, но мы будем вычислять L и сравнить его с Шэннона энтропии H из заданного набора весов; результат почти оптимальный.

Входные данные ( , Вт ) Символ ( я ) б с d е сумма
Вес ( ш я ) 0,10 0,15 0,30 0,16 0,29 = 1
Выход C Кодовые слова ( с я ) 010 011 11 00 10
Длина кодового слова (в битах)
( л я )
3 3 2 2 2
Вклад в взвешенную длину пути
( л я ш I )
0,30 0,45 0,60 0,32 0,58 L ( C ) = 2,25
Оптимальность Вероятность бюджета
(2 — л я )
1/8 1/8 1/4 1/4 1/4 = 1,00
Содержание данных (в битах)
(- войти 2 ш I ) ≈
3,32 2,74 1,74 2,64 1,79
Вклад энтропии
(- ш я войти 2 ш I )
0,332 0,411 0,521 0,423 0,518 Н ( ) = 2,205

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

В соответствии с определением Шенноном (1948) , содержание информации ч (в битах) каждый символ я с ненулевой вероятностью является

Энтропия Н (в битах) является взвешенной суммой, по всем символам я с ненулевой вероятностью ш I , информационного содержания каждого символа:

(Примечание: символ с нулевой вероятностью имеет нулевой вклад в энтропию, так как Таким образом , для простоты, символы с нулевой вероятностью может быть исключены из приведенной выше формулы.) lim w → 0 + w log 2 ⁡ w = 0 <\displaystyle \lim _>w\log _<2>w=0>

Как следствие теоремы Шеннона кодирования источника , энтропия является мерой наименьшей длины кодового слова, которое теоретически возможно для данного алфавита с соответствующими весами. В этом примере, средневзвешенная длина кодового слова составляет 2,25 бита на символ, что лишь немного больше , чем вычисленные энтропии 2.205 битых на символ. Так что не только этот код оптимальный в том смысле , что никакой другой выполнимый код не работает лучше, но это очень близко к теоретическому пределу , установленному Шеннон.

В общем, код Хаффмана не должно быть уникальным. Таким образом, множество кодов Хаффмана для заданного распределения вероятностей является непустым подмножеством кодов , минимизирующими для этого распределения вероятностей. (Тем не менее, для каждого минимизируя присвоения длины кодового слова, существует по крайней мере один код Хаффмана с теми длинами.) L ( C )

Базовая техника

компрессия

Источник генерирует 4 различных символов с вероятностью . Бинарное дерево генерируется слева направо с двумя не менее вероятными символами и положить их вместе , чтобы сформировать другой эквивалентный символ , имеющий вероятность, равную сумму два символов. Процесс повторяется до тех пор , пока только один символ. Дерева , то можно прочитать в обратном направлении, справа налево, назначая различные биты в различных отраслях. Окончательный код Хаффмана является: < a 1 , a 2 , a 3 , a 4 ><\displaystyle \,a_<2>,a_<3>,a_<4>\>> < 0.4 ; 0.35 ; 0.2 ; 0.05 ><\displaystyle \<0.4;0.35;0.2;0.05\>>

Условное обозначение Код
a1
a2 10
a3 110
a4 111

Стандартный способ для представления сигнала , выполненный из 4 -х символов с помощью 2 бит / символ, но энтропия источника является 1,74 бит / символ. Если этот код Хаффмана используется для представления сигнала, то средняя длина понижается до 1,85 бит / символа; она все еще далека от теоретического предела , поскольку вероятности символов отличаются от отрицательных степеней двойки.

Техника работает путем создания бинарного дерева узлов. Они могут храниться в обычном массиве , размер которого зависит от количества символов, . Узел может быть либо узлом листа или внутренний узел . Изначально все узлы являются листовыми узлами, которые содержат символ самого, то вес (частоту появления) символа и , возможно, ссылку на родительский узел , который позволяет легко читать код (в обратном направлении) , начиная от узла листа , Внутренние узлы содержат вес , ссылки на два дочерних узлы и необязательную ссылку на родительский узел. В качестве общей конвенции, бит «0» представляет следующий левый ребенок и немного «1» представляет после правого ребенка. Готовое дерево имеет до листовых узлов и внутренних узлов. Хаффмана дерево , которое пропускает неиспользуемые символы производит наиболее оптимальные длины кода. n <\displaystyle n>n <\displaystyle n>n − 1

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

Простейший алгоритм построения использует очереди приоритета , где узел с наименьшей вероятностью дается наивысший приоритет:

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

Так как эффективные структуры данных очереди приоритетов требуют O (журнал п ) раз в вставки, и дерево с п листьев имеют 2 п -1 узлов, этот алгоритм работает в O ( п войти п ) время, где п есть число символов.

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

  1. Начните с так много листьев, как есть символы.
  2. Enqueue всех листовых узлов в первую очередь (с вероятностью в порядке возрастания так, что наименее вероятно элемент находится в голове очереди).
  3. Хотя есть более чем один узел в очередях:
    1. DEQUEUE два узла с наименьшим весом путем изучения фронтов обеих очередей.
    2. Создать новый внутренний узел с двумя только что снятыми узлами, как дети (или узел может быть либо ребенок), а сумма их весов в качестве нового веса.
    3. Enqueue новый узел в задней части второй очереди.
  4. Оставшийся узел является корневым узлом; дерево теперь генерируется.

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

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

декомпрессия

Вообще говоря, процесс декомпрессии это просто вопрос о переводе потока префиксных кодов для отдельных байтовых значений, как правило , путем обхода дерева узла Хаффмана узла , как каждый бит считываются из входного потока (достигающего листовой узел обязательно прекращает поиск для этого конкретного значения байта). Перед тем как это может иметь место, однако, дерево Хаффмана должно быть каким — то образом реконструировано. В простейшем случае, когда частоты символов довольно предсказуем, дерево может быть preconstructed (и даже статистически настроены на каждом цикле сжатия) и , таким образом , повторно каждый раз, за счет , по крайней мере , до некоторой степени эффективности сжатия. В противном случае информация для восстановления дерева должна быть направлена априори. Наивный подход может предварять счетчик частоты каждого символа в поток сжатия. К сожалению, накладные расходы в таком случае может составлять несколько килобайт, поэтому этот метод имеет мало практического использования. Если данные сжаты с использованием канонического кодирования , модель сжатия можно точно реконструировать только с битами информации (где является количество бит на символ). Другой способ заключается в просто приписать дерево Хаффмана, бит за битом, чтобы выходной поток. Например, если предположить , что значение 0 представляет собой родительский узел и 1 лист узел, всякий раз , когда последнее встречается процедура построения дерева просто считывает следующие 8 бит , чтобы определить значение символа этого конкретного листа. Процесс продолжается рекурсивно до последнего узла листа не будет достигнута; в этой точке, дерево Хаффмана таким образом , будет точно реконструировать. Накладные расходы с использованием такого метода находятся в диапазоне от примерно 2 до 320 байт (при условии , 8-битный алфавита). Многие другие методы также возможны. В любом случае, так как сжатые данные могут включать в себя неиспользуемые биты «хвостовые» декомпрессор должен быть в состоянии определить , когда следует прекратить производить выход. Это может быть достигнуто либо путем передачи длины распакованных данных вместе с моделью сжатия или определяя специальный кодовый символ, обозначающий конец ввода (последний способ может отрицательно повлиять на длину кода оптимальность, однако). B 2 B <\displaystyle B2^> B

Основные свойства

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

Оптимальность

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

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

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

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

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

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

вариации

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

п — позиционное кодирование Хаффмана

П Хаффман -ичного алгоритм использует <0, 1, . п — 1> алфавит для кодирования сообщения и построить н -ичное дерево. Такой подход был рассмотрен Хаффман в своей оригинальной статье. Же алгоритм применим и для бинарных ( п равно 2) кодов, за исключением того, что п не менее вероятные символы, взятые вместе, вместо того , чтобы только два наименее вероятной. Замечу , что для п больше 2, не все наборы исходных слов могут правильно образовать п -ичного дерево для кодирования по алгоритму Хаффмана. В этих случаях дополнительные держатели места 0-вероятностные должны быть добавлены. Это происходит потому , что дерево должно сформировать п до 1 подрядчика; для двоичного кодирования, это от 2 до 1 подрядчик, и любого размером набор может сформировать такую организацию. Если количество исходных слов сравнимо с 1 по модулю п -1, то множество исходных слов будет формировать правильный Хаффман дерева.

Адаптивное кодирование Хаффмана

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

Алгоритм Хаффмана шаблон

Чаще всего, вес , используемый в реализации кодирования Хаффмана представляет числовые вероятности, но алгоритм , приведенный выше , не требует этого; она требует только , что веса образуют упорядоченный коммутативный моноид , то есть способ сделать заказ весов и добавить их. Алгоритм шаблона Хаффмана позволяет использовать любой вид весов (расходы, частоты, пар весов, не-численные веса) и один из многих методов , сочетающих ( а не только сложение). Такие алгоритмы могут решать другие задачи минимизации, такие как сведение к минимуму , проблема впервые применена к схемотехнике. max i [ w i + l e n g t h ( c i ) ] <\displaystyle \max _\left[w_+\mathrm \left(c_\right)\right]>

Длина ограниченного кодирование Хаффмана / минимальная дисперсия кодирования Хаффмана

Длина ограниченного кодирования Хаффмана представляет собой вариант , где цель по — прежнему для достижения минимальной взвешенной длины пути, но существует дополнительное ограничение , что длина каждого кодового слова должно быть меньше , чем заданная постоянная. Алгоритм пакета слияния решает эту проблему с помощью простого жадного подхода очень похож на используемом алгоритме Хаффмана. Его время сложность , где максимальная длина кодового слова. Алгоритм не известен , чтобы решить эту проблему или время, в отличии от неупорядоченных и предварительно отсортированных обычных проблем Хаффмана соответственно. O ( n L ) <\displaystyle O(nL)>L <\displaystyle L> O ( n ) <\displaystyle O(n)>O ( n log ⁡ n )

Кодирование Хаффмана с неравной стоимостью буквенных

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

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

Оптимальные алфавитные бинарные деревья (Ху-Такера кодирование)

В стандартной задаче кодирования по алгоритму Хаффмана, то предполагается , что любое кодовое слово может соответствовать любому входному символу. В алфавитной версии, алфавитный порядок входов и выходов должны быть идентичны. Так, например, не может быть присвоен код , но вместо этого должен быть назначен либо или . Это также известно как Х-Такер проблема, после того, как TC Х и Алан Tucker , авторы статьи , представляя первый -time решение этих оптимальных бинарных алфавитных проблем, которая имеет некоторое сходство с алгоритмом Хаффмана, но это не вариантом этот алгоритм. Более поздний метод, то алгоритм-Гарсиа Вахс из Адриано Гарсия и Мишель Л. Wachs (1977), использует простую логику для выполнения того же сравнения в том же общее время , связанное. Эти оптимальные алфавитные бинарные деревья часто используются в качестве бинарных деревьев поиска . A = < a , b , c ><\displaystyle A=\left\> H ( A , C ) = < 00 , 1 , 01 ><\displaystyle H\left(A,C\right)=\left\<00,1,01\right\>> H ( A , C ) = < 00 , 01 , 1 ><\displaystyle H\left(A,C\right)=\left\<00,01,1\right\>> H ( A , C ) = < 0 , 10 , 11 ><\displaystyle H\left(A,C\right)=\left\<0,10,11\right\>> O ( n log ⁡ n )

Канонический код Хаффмана

Если вес , соответствующий в алфавитном порядке входов в порядке, код Хаффмана имеет те же длины, что и оптимальный алфавитный код, которые могут быть найдены из расчета этих длин, что делает Hu-Tucker кодирования ненужным. Код в результате численно (перо) заказал вход иногда называют канонический код Хаффмана и часто код используется на практике, вследствие легкости кодирования / декодирования. Метод для нахождения этого кода иногда называют кодирование Хаффмана Шеннона-Фано , так как он является оптимальным , как кодирование Хаффмана, но алфавитный вероятности веса, как кодирование Шеннона-Фано . Код Хаффмана Шеннона-Фано , соответствующее примере , который, с той же длины , как кодовое слово исходного раствора, также является оптимальным. Но в каноническом коде Хаффмана , результат . < 000 , 001 , 01 , 10 , 11 ><\displaystyle \<000,001,01,10,11\>> < 110 , 111 , 00 , 01 , 10 ><\displaystyle \<110,111,00,01,10\>>

Приложения

Арифметическое кодирование и кодирование Хаффмана результатов эквивалентных — достижение энтропии — когда каждый символ имеет вероятность вид 1/2 к . В других обстоятельствах, арифметическое кодирование может предложить лучшее сжатие , чем кодирование Хаффмана , потому что — интуитивно — его «кодовые слова» могут иметь эффективно нецелые длины биты, тогда как кодовые слова в префиксных кодах , такие как коды Хаффмана могут иметь только целое число бит. Таким образом, кодовое слово длиной к только оптимально соответствует символу вероятность 1/2 к и других вероятностей не представляется оптимальным образом ; в то время как длина кодового слова в арифметическом кодировании может быть сделано , чтобы точно соответствовать истинной вероятности символа. Это различие особенно поразительно для малых размеров алфавита.

Префикс кода все же остается в широком использовании из — за их простоту, высокой скорости, а также отсутствие патентного покрытия . Они часто используются в качестве «фоновым» с другими методами сжатия. Выкачать ( PKZIP «ы алгоритм) и мультимедийные кодеки , такие как JPEG и MP3 имеют передний конец модель и квантование с последующим использованием префиксных кодов; Их часто называют «Хаффман кода» несмотря на то, что большинство приложений используют предопределенные коды переменной длины , а не коды , разработанные с помощью алгоритма Хаффмана.

Код хаффмана

Huffman — Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

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

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже.

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из «узлов» D и A новый «узел», частота вхождения для которого будет равна сумме частот D и A :

Номер в рамке — сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый «узел» с суммарной частотой вхождения. Самая низкая частота теперь у F и нового «узла». Снова сделаем операцию слияния узлов :

Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все «дерево» не сформировано, т.е. пока все не сведется к одному узлу.

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всенда начнинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C — 00. Для следующего символа ( А ) у нас получается — лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим

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

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

В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11. 4 байта 11 раз — 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику — наша таблица будет приблизительно 50 байтов длинны.

Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт — мы получили 20% сжатие информации.

Не плохо. То что мы действительно выполнили — трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.

Что мы можем получить на этом пути ?

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

Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.

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

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

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

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL