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

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

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

А = а, а, ...а,

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

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

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

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

а,-В_и а₂ - В₂,

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

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

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

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

В=В^ХВ".

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

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

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

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

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

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

а, - В,,

а_г-В_п

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ремонт iphone

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

Автосалоны Москвы: купить стиральную машину.

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