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

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

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

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

будем называть словом в алфавите Y, а число n — длиной слова A. Длина слова обозначается как l(A).

Пусть задан алфавит W, W={b₁, ..., b_q}. Через B обозначим слово в алфавите W и через S(W) — множество всех непустых слов в алфавите W.

Пусть S=S(Y) — множество всех непустых слов в алфавите Y, и S' — некоторое подмножество множества S. Пусть, также задано отображение F, которое каждому слову A, AÎS(Y), ставит в соответствие слово

B=F(A), BÎS(W).

Слово В будем назвать кодом сообщения A, а переход от слова A к его коду — кодированием.

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

a₁ — B₁,
a₂ — B₂,
. . .
a_r — B_r

Это соответствие называют схемой и обозначают через S. Оно определяет кодирование следующим образом: каждому слову из S'(W)=S(W) ставится в соответствие слово , называемое кодом слова A. Слова B₁ ... B_r называются элементарными кодами. Данный вид кодирования называют алфавитным кодированием.

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

B=B'B"

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

Определение. Схема S обладает свойством префикса, если для любых i и j (1£i, j£r, i¹j) слово B_i не является префиксом слова B_j.

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

Предположим, что задан алфавит Y={a₁,..., a_r} (r>1) и набор вероятностей p₁, . . . , p_r появления символов a₁,..., a_r. Пусть, далее, задан алфавит W, W={b₁, ..., b_q} (q>1). Тогда можно построить целый ряд схем S алфавитного кодирования

a₁ — B₁,
. . .
a_r — B_r

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

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

— длины слов.

Длина l_ср показывает, во сколько раз увеличивается средняя длина слова при кодировании со схемой S.

Можно показать, что l_ср достигает величины своего минимума l_* на некоторой S и определена как

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

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

В нашем случае, алфавит Y={a₁,..., a_r} задает символы входного потока, а алфавит W={0,1}, т.е. состоит всего из нуля и единицы.

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

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

Шаг 2. Объединяем два символа a_ir-1 и a_ir с наименьшими вероятностями p_{i r-1} и p_{i r} в псевдосимвол a'{a_ir-1 a_ir} c вероятностью p_ir-1+p_ir. Дописываем 0 в начало слова B_ir-1 (B_ir-1=0B_ir-1), и 1 в начало слова и B_ir (B_ir=1B_ir).

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

Пример: Пусть у нас есть 4 буквы в алфавите Y={a₁,..., a₄} (r=4), p₁=0.5, p₂=0.24, p₃=0.15, p₄=0.11 . Тогда процесс построения схемы можно представить так:

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

Для того, чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью p₄, получим B₄=101, для p₃ получим B₃=100, для p₂ получим B₂=11, для p₁ получим B₁=0. Что означает схему:

a₁ — 0,
a₂ — 11
a₃ — 100
a₄ — 101

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

Для последовательности из 100 символов, в которой символ a₁ встретится 50 раз, символ a₂ — 24 раза, символ a₃ — 15 раз, а символ a₄ — 11 раз, данный код позволит получить последовательность из 176 бит ( ). Т.е. в среднем мы потратим 1.76 бита на символ потока.

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

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

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

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

Коэффициенты компрессии:8, 1,5, 1 (Лучший, средний, худший коэффициенты)

Класс изображений: Практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах.

Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).

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

Поиск по сайту: