Метод Хаффмана и родственные методы


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Метод Хаффмана и родственные методы

Метод Хаффмана (Huffman method)

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

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

Для заданного распределения частот символов может существовать несколько возможных кодов Хаффмана. Возможно определить 'каноническое' дерево Хаффмана, выбрав одно из возможных деревьев. Такое каноническое дерево может быть очень компактно, передавая только длину в битах для каждого кодового слова. Такой метод используется в большинстве архиваторов (PkZip, Lha, Zoo, Arj, ...).

Метод Шеннона-Фано (Shannon-Fano method)

Родственным методом для кодирования Хаффмана является кодирование Шеннона-Фано, которое осуществляется следующим образом:

Делим множество символов на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписываем "0", для правого - "1".
Повторяем шаг (1) до тех пор, пока все подмножества не будут состоять из одного элемента.

Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано - сверху вниз. Кодирование по Хаффману всегда дает оптимальные коды, по Шеннону-Фано иногда используется немного больше бит.

Алгоритмы Хаффмана и Шеннона-Фано являются одними из классических, поэтому они часто используются в графических форматах. Они берут только частоту появления одинаковых байт в изображении и сопоставляют символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требуют двух проходов по изображению. Коэффициенты сжатия алгоритмов : 1/8, 2/3, 1. Требуют записи в файл таблицы соответствия кодируемых символов и кодирующих цепочек. На практике используются их разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее адаптивно, т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.

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

Арифметический метод (Arithmetic method)

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

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

Работа арифметического кодера состоит в представлении числа интервалом вещественных чисел от 0 до 1. По мере увеличения длины сообщения, интервал, необходимый для его представления, становится все меньше и меньше, а число бит, необходимых для задания этого интервала, увеличивается. Каждый символ сообщения по порядку сокращает этот интервал пропорционально вероятности появления этого символа. Наиболее вероятный символ меньше всех сокращает интервал, и таким образом добавляет меньше бит к коду сообщения.

В качестве примера арифметического кодирования рассмотрим такой пример: алфавит состоит из двух символов X и Y с вероятностями 0.66 и 0.33. Кодируя такое сообщение, посмотрим на первый символ: если это символ X, выбираем интервал (0; 2/3), если же это символ Y, то - (2/3; 1). Продолжая таким образом для двух символов, мы получим: XX - (0; 4/9), XY - (4/9; 6/9), YX - (6/9; 8/9) и для YY - (8/9; 1).

В этом примере арифметический код не полностью эффективен, по причине сжатия короткого сообщения - на длинных сообщениях эффективность кодирования реально приближается к 100%.

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

Использование вероятностей символов по отдельности - не совсем хорошая оценка для энтропии данных: мы можем также использовать вероятности сочетаний символов. Лучшие из известных на сей момент компрессоры, использующие этот подход: DMC (Dynamic Markov Coding) начинает работу с марковской модели 0-порядка и постепенно расширяет начальную модель в процессе сжатия; PPM (Prediction by Partial Matching), ищет появления сжимаемого текста в контексте n-го порядка. Оба метода таким образом получают более лучшую модель сжимаемых данных, и в сочетании с арифметическим кодированием, приводят к лучшей степени сжатия.

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

Sarmin Alexey