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

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

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

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

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

будем называть словом в алфавите Y

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

Пусть задан алфавит W , W

={b1, ..., bq}. Через 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 :

— B1,

— B2,

. . .

— Br

Это соответствие называют схемой и обозначают через S

. Оно определяет кодирование следующим образом: каждому слову

из S'(W )=S(W

) ставится в соответствие слово

, называемое кодом слова A. Слова B1 ... Br

называются элементарными кодами. Данный вид кодирования называют алфавитным кодированием.

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

B=B' B"

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

и само слово B считаются началами и концами слова B.

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

не является префиксом слова Bj.

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

Предположим, что задан алфавит Y

={a1,..., ar} (r>1) и набор вероятностей p1, . . . , pr

появления символов a1,..., ar. Пусть, далее, задан алфавит W , W

={b1, ..., bq} (q>1). Тогда можно построить целый ряд схем S алфавитного кодирования

— B1,

. . .

— Br

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

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

— длины слов.

Длина lср

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

Можно показать, что lср

достигает величины своего минимума l*

на некоторой Sи определена как

Определение. Коды, определяемые схемой S

с lср= l*, называются кодами с минимальной избыточностью, или кодами Хаффмана.

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

В нашем случае, алфавит Y ={a1,..., ar} задает символы входного потока, а алфавит W

={0,1}, т.е. состоит всего из нуля и единицы.

Алгоритм построения схемы S

можно представить следующим образом:

Шаг 1. Упорядочиваем все буквы входного алфавита в порядке убывания вероятности. Считаем все соответствующие слова Bi

из алфавита W ={0,1} пустыми.

Шаг 2. Объединяем два символа air-1

и air

с наименьшими вероятностями pi

r-1 и pi

r в псевдосимвол a'{air-1 air} c вероятностью pir-1+pir. Дописываем 0 в начало слова Bir-1

(Bir-1=0Bir-1), и 1 в начало слова Bir

(Bir=1Bir).

Шаг 3. Удаляем из списка упорядоченных символов air-1

и air, заносим туда псевдосимвол a'{air-1air}. Проводим шаг 2, добавляя при необходимости 1 или ноль для всех слов Bi, соответствующих псевдосимволам, до тех пор, пока в списке не останется 1 псевдосимвол.

Пример: Пусть у нас есть 4 буквы в алфавите Y

={a1,..., a4} (r=4), p1=0.5, p2=0.24,

p3=0.15, p4=0.11

. Тогда процесс построения схемы можно представить так:

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

Для того, чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью p4, получим B4=101, для p3

получим B3=100, для p2

получим B2=11, для p1

получим B1=0. Что означает схему:

— 0,

— 11

— 100

— 101

Эта схема представляет собой префиксный код, являющийся кодом Хаффмана. Самый часто встречающийся в потоке символ a1

мы будем кодировать самым коротким словом 0, а самый редко встречающийся a4

длинным словом 101.

Для последовательности из 100 символов, в которой символ a1

встретится 50 раз, символ a2

— 24 раза, символ a3

— 15 раз, а символ a4

— 11 раз, данный код позволит получить последовательность из 176 бит (

). Т.е. в среднем мы потратим 1.76 бита на символ потока.

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

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

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

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

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

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

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

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

Алгоритм Хаффмана с фиксированной таблицей CCITTGroup 3

Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей группой по стандартизации Международного Консультационного Комитета по Телеграфии и Телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.

Определение: Набор идущих подряд точек изображения одного цвета называется серией.Длина этого набора точек называется длиной серии.

В таблице, приведенной ниже, заданы два вида кодов:

Коды завершения серий — заданы с 0 до 63 с шагом 1.

Составные (дополнительные) коды — заданы с 64 до 2560 с шагом 64.

Каждая строка изображения сжимается независимо. Мы считаем, что в нашем изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то мы считаем, что строка начинается белой серией с длиной 0. Например, последовательность длин серий 0, 3, 556, 10, ... означает, что в этой строке изображения идут сначала 3 черных точки, затем 556 белых, затем 10 черных и т.д.

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

Алгоритм компрессии выглядит так:

for(по всем строкам изображения) {

    Преобразуем строку в набор длин серий;

    for(по всем сериям) {

        if(серия белая) {

            L= длина серии;

            while(L > 2623) { // 2623=2560+63

                L=L-2560;

                ЗаписатьБелыйКодДля(2560);

            }

            if(L > 63) {

                L2=МаксимальныйСостКодМеньшеL(L);

                L=L-L2;

                ЗаписатьБелыйКодДля(L2);

            }

            ЗаписатьБелыйКодДля(L);

            //Это всегда код завершения

        }

        else {

            [Код аналогичный белой серии,

            с той разницей, что записываются

            черные коды]

        }

    }

    // Окончание строки изображения

}

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

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

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>)+

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Где ()* — повтор 0 или более раз, ()+.— повтор 1 или более раз, [] — включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0><Ч-3><Б-512><Б-44><Ч-10>, или, согласно таблице, 001101011001100101001011010000100

(разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т.е. коэффициент сжатия составляет примерно 17 раз.

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

Изображение, для которого очень выгодно применение алгоритма CCITT-3. (Большие области заполнены одним цветом).

Изображение, для которого менее выгодно применение алгоритма CCITT-3. (Меньше областей, заполненных одним цветом. Много коротких “черных” и “белых” серий).

Заметим, что единственное “сложное” выражение в нашем алгоритме: L2=МаксимальныйДопКодМеньшеL(L)

— на практике работает очень просто: L2=(L>>6)*64, где >> — побитовый сдвиг L влево на 6 битов (можно сделать то же самое за одну побитовую операцию & — логическое И).

Упражнение: Дана строка изображения, записанная в виде длин серий — 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, размером 120 байт ((442+2+..+231)/8). Подсчитать коэффициент компрессии этой строки алгоритмом CCITT Group 3.

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

Таблица кодов завершения:

Длина серии	Код белой подстроки	Код черной подстроки	Длина серии	Код белой подстроки	Код черной подстроки
0	00110101	0000110111	32	00011011	000001101010
1	00111	010	33	00010010	000001101011
2	0111	11	34	00010011	000011010010
3	1000	10	35	00010100	000011010011
4	1011	011	36	00010101	000011010100
5	1100	0011	37	00010110	000011010101
6	1110	0010	38	00010111	000011010110
7	1111	00011	39	00101000	000011010111
8	10011	000101	40	00101001	000001101100
9	10100	000100	41	00101010	000001101101
10	00111	0000100	42	00101011	000011011010
11	01000	0000101	43	00101100	000011011011
12	001000	0000111	44	00101101	000001010100
13	000011	00000100	45	00000100	000001010101
14	110100	00000111	46	00000101	000001010110
15	110101	000011000	47	00001010	000001010111
16	101010	0000010111	48	00001011	000001100100
17	101011	0000011000	49	01010010	000001100101
18	0100111	0000001000	50	01010011	000001010010
19	0001100	00001100111	51	01010100	000001010011
20	0001000	00001101000	52	01010101	000000100100
21	0010111	00001101100	53	00100100	000000110111
22	0000011	00000110111	54	00100101	000000111000
23	0000100	00000101000	55	01011000	000000100111
24	0101000	00000010111	56	01011001	000000101000
25	0101011	00000011000	57	01011010	000001011000
26	0010011	000011001010	58	01011011	000001011001
27	0100100	000011001011	59	01001010	000000101011
28	0011000	000011001100	60	01001011	000000101100
29	00000010	000011001101	61	00110010	000001011010
30	00000011	000001101000	62	00110011	000001100110
31	00011010	000001101001	63	00110100	000001100111

<

Таблица составных кодов:

Длина серии	Код белой подстроки	Код черной подстроки	Длина серии	Код белой подстроки	Код черной подстроки
64	11011	0000001111	1344	011011010	0000001010011
128	10010	000011001000	1408	011011011	0000001010100
192	01011	000011001001	1472	010011000	0000001010101
256	0110111	000001011011	1536	010011001	0000001011010
320	00110110	000000110011	1600	010011010	0000001011011
384	00110111	000000110100	1664	011000	0000001100100
448	01100100	000000110101	1728	010011011	0000001100101
512	01100101	0000001101100	1792	00000001000	совп. с белой
576	01101000	0000001101101	1856	00000001100	— // —
640	01100111	0000001001010	1920	00000001101	— // —
704	011001100	0000001001011	1984	000000010010	— // —
768	011001101	0000001001100	2048	000000010011	— // —
832	011010010	0000001001101	2112	000000010100	— // —
896	011010011	0000001110010	2176	000000010101	— // —
960	011010100	0000001110011	2240	000000010110	— // —
1024	011010101	0000001110100	2304	000000010111	— // —
1088	011010110	0000001110101	2368	000000011100	— // —
1152	011010111	0000001110110	2432	000000011101	— // —
1216	011011000	0000001110111	2496	000000011110	— // —
1280	011011001	0000001010010	2560	000000011111	— // —

Если в одном столбце встретятся два числа с одинаковым префиксом, то это опечатка.

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213.(3), средний 2, в худшем случае увеличивает файл в 5 раз.

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

Симметричность: Близка к 1.

Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.

Содержание раздела