Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Канонический алгоритм Хаффмана

Один из классических алгоритмов, известных с 60-х гг. Использует только частоту появления одинаковых байтов во входном блоке данных. Ставит в соответствие символам входного потока, которые встречаются ча­ще, цепочку битов меньшей длины. И напротив, встречающимся редко -цепочку большей длины. Для сбора статистики требует двух проходов по входному блоку (также существуют однопроходные адаптивные варианты алгоритма).

Для начала введем несколько определений.

Определение. Пусть задан алфавит *Ґ={ai,.... ar}, состоящий из конечно­го числа букв. Конечную последовательность символов из Y

А = а, а, ...а,

будем называть словом в алфавите Ч*, а число п - длиной слова А. Длина слова обозначается как 1(A).

Пусть задан алфавит П, Q={b\, .... Ьч}. Через В обозначим слово в алфа­вите Q, и через 5(П) - множество всех непустых слов в алфавите Я.

Пусть S=SQҐ) - множество всех непустых слов в алфавите *F и S'~ неко­торое подмножество множества 5. Пусть также задано отображение F, ко­торое каждому слову A, AeSi^V) ставит в соответствие слово B=F(A), BeS(Q). Слово В будем называть кодом сообщения А, а переход от слова А к его коду - кодированием.

Определение. Рассмотрим соответствие между буквами алфавита ¥ и некоторыми словами алфавита П:

а,-Ви а2 - В2,

а, - Вг. Это соответствие называют схемой и обозначают через £. Оно определя­ет кодирование следующим образом: каждому слову А = а,а1...а^ из

S'(d)=S(Q) ставится в соответствие слово B = BjBl ...В^ , называемое кодом

слова А. Слова В\... ВТ называются элементарными кодами. Данный вид ко­дирования называют алфавитным кодированием.

Определение. Пусть слово В имеет вид

В=ВХВ".

Тогда слово В' называется началом или префиксом слова В, а В"- кон­цом слова В. При этом пустое слово Л и само слово В считаются началами и концами слова В.

Определение. Схема £ обладает свойством префикса, если для любых i и у (\ui,j<r, tej) слово В/ не является префиксом слова Bj.

Теорема 1. Если схема £ обладает свойством префикса, то алфавитное кодирование будет взаимно-однозначным.

Доказательство теоремы можно найти в [4].

( =1 появления символов а,. аг. Пусть, далее, задан

Предположим, что задан алфавит Ч'={а/, ..., аг} (г>1) и набор вероятностей р, рг

алфавит £2, П={6;, ..., bq) (q>l). Тогда можно построить целый ряд схем £ алфавитного кодирования

а, - В,,

агп

обладающих свойством взаимной однозначности.

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

Длина /ср показывает, во сколько раз увеличивается средняя длина слова при кодировании с помощью схемы £.

Можно показать, что /q, достигает величины своего минимума Л на неко­торой I и определяется как

Определение. Коды, определяемые схемой Е с /ср= /., называются кодами с минимальной избыточностью или кодами Хаффмана.

Коды с минимальной избыточностью дают в среднем минимальное уве­личение длин слов при соответствующем кодировании.

В нашем случае алфавит *F={a;, ..., аг) задает символы входного потока, а алфавит П={0,1}, т. е. состоит всего из нуля и единицы.

Алгоритм построения схемы £ можно представить следующим образом:

Шаг 1. Упорядочиваем все буквы входного алфавита в порядк: убыва­ния вероятности. Считаем все соответствующие слова В, из алфавита £2= {0,1} пустыми.

Шаг 2. Объединяем два символа а,-,., и а,> с наименьшими вероятностями pir.i n pir в псевдосимвол a'{air.,air} с вероятностью р^+Рь- Дописываем 0 в начало слова В^, (fi|V.,=05ir.i) и 1 в начало слова Bir (Bj=lBir).

Шаг 3. Удаляем из списка упорядоченных символов ам и ain заносим туда псевдосимвол a'{air.flir}. Проводим шаг 2, добавляя при необходимости 1 или 0 для всех слов Bh соответствующих псевдосимволам, до тех пор пока в списке не останется 1 псевдосимвол.

Пример. Пусть у нас есть 4 буквы в алфавите у¥={аи..., а4} (r=A'\, />i=0.5,

Производя действия, соответствующие 2-му шагу, мы получаем псевдо­символ с вероятностью 0.26 (и приписываем 0 и 1 соответствующим сло­вам). Повторяя же эти действия для измененного списка, мы получаем псевдосимвол с вероятностью 0.5. И наконец, на последнем этапе мы полу­чаем суммарную вероятность 1.0.

Для того чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью рл получим 54=101, для р3 получим 5з=100, тяр2 получим i?2=l 1, ДЛя/?1 получим 5|»0.

Эта схема представляет собой префиксный код, являющийся кодом Хаффмана. Самый часто встречающийся в потоке символ а, мы будем ко­дировать самым коротким словом 0, а самый редко встречающийся а4 -длинным словом 101.

Для последовательности из 100 символов, в которой символ а\ встретится 50 раз, символ а2 - 24 раза, символ а3 - 15 раз, а символ «4-11 раз, данный код

позволит получить последовательность из 176 бит .То есть в среднем мы потратим 1.76 бита на символ потока.

Доказательства теоремы, а также того, что построенная схема действи­тельно задает код Хаффмана, заинтересованный читатель найдет в [4].

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

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее адаптив­но, т. е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по входному блоку и необходимости хранения таблицы вме­сте с файлом. Кодирование с фиксированной таблицей применяется в каче­стве последнего этапа архивации в JPEG и в алгоритме CCITT Group, рас­смотренных в разд. 2.

Характеристики канонического алгоритма Хаффмана: Степени сжатия: 8,1.5,1 (лучшая, средняя, худшая степени). ' Симметричность по времени: 2:1 (за счет того, что требует двух i проходов по массиву сжимаемых данных).

Микрозаймы в Тюмени срочно

Характерные особенности: один из немногих алгоритмов, который I не увеличивает размера исходных данных в худшем случае (если не счи-j тать необходимости хранить таблицу перекодировки вместе с файлом).