Метод Хаффмана — это метод оптимального кодирования информации, позволяющий свести к минимуму избыточность кода.
Введение
Проблема сжатия информации обладает довольно давней историей, которая является значительно более давней, чем даже история развития вычислительных средств, шедшая, как правило, параллельно с историей возникновения проблем кодирования и шифрования информации. Любой алгоритм сжатия оперируют входным информационным потоком, минимальной единицей которой считается бит, а максимальной единицей могут быть несколько бит, то есть байт или несколько байт.
Задачей процедуры информационного сжатия обычно является формирование наиболее компактного выходного потока информации из некоего изначально не сжатого входного потока с помощью определённых преобразований. Главными техническими характеристиками процессов сжатия и итогов их работы могут считаться следующие параметры:
- Степень сжатия (compress rating) или отношение (ratio) объемов начального и результирующего потоков.
- Скорость выполнения сжатия, то есть, время, которое затрачивается на сжатие определённого информационного объема из входного потока, до формирования из него аналогичного выходного потока.
- Качество сжатия, то есть значение, которое показывает на сколько сильно сжат выходной поток, при помощи использования по отношению к нему повторного сжатия по такому же или другому алгоритму.
Кодирование информации методом Хаффмана
Кодирование информационных данных по методу Хаффмана считается несложным алгоритмом для формирования кодов переменной длины, которые имеют минимальную среднюю длину. Данный очень распространённый алгоритм заложен в основу большого количества компьютерных программ, предназначенных для сжатия текстовых и графических информационных данных. Некоторые из них применяют в исходном варианте алгоритм Хаффмана, а иные используют его как один из этапов процесса сжатия, состоящего из многих уровней. Метод Хаффмана способен реализовать идеальное сжатие, то есть, сжимает данные до их энтропии, при условии, что вероятности символов точно равны отрицательным степеням двойки. Алгоритм реализует построение кодового дерева по принципу «снизу вверх», а далее спускается вниз по дереву, чтобы выстроить каждый индивидуальный код справа налево (от самого младшего бита к самому старшему).
Метод информационного сжатия на базе бинарных кодирующих деревьев был разработан Д. А. Хаффманом в 1952 году, то есть, ещё до создания современных цифровых компьютеров. Обладая высокой эффективностью, этот метод и его разнообразные адаптивные варианты положены в основу многих методик, применяемых в сегодняшних алгоритмах кодирования. Код Хаффмана не часто применяется по отдельности, как правило, его используют в связке с иными алгоритмами кодирования. Метод Хаффмана может считаться примером формирования кодов переменной длины, которые имеют минимальную среднюю длину. Метод кодирования Хаффмана включает в свой состав следующие основные этапы:
- Формирование оптимального кодового дерева.
- Формирование отображения код-символ на базе выстроенного дерева.
Алгоритм использует тот факт, что определённые символы из стандартного 256-символьного набора в каком-либо тексте могут попадаться чаще средней периодичности повторений, а все остальные встречаются значительно реже. Таким образом, если для записи распространенных символов применять укороченные наборы бит, имеющие длину менее восьми, а для записи редких символов использовать длинные битовые наборы, то суммарный объем файла должен стать меньше. В итоге формируется систематизация данных в виде двоичного дерева.
Например, A = {a1, a2, ..., an} является алфавитом из n разных символов, а W = {w1, w2, ..., wn} является соответствующим ему набором положительных целых весов. Тогда должен существовать набор бинарных кодов C = {c1, c2, ..., cn}, такой что:
- ci не должен являться префиксом для cj, при i! = j.
- минимальная длина (|ci| длина кода ci) именуется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.
Двоичным деревом является ориентированное дерево, полу степень исхода любой из вершин которого не должна превышать два. Вершина бинарного дерева, полу степень захода которой равняется нулю, именуется корнем. Для оставшихся вершин дерева полу степень захода равняется единице.
Предположим Т является бинарным деревом. А=(0,1) является двоичным алфавитом и каждому ребру Т-дерева соответствует одна из букв алфавита таким образом, что все ребра, которые исходят из одной вершины, помечены разными буквами. В таком случае каждому листу Т-дерева может быть приписано уникальное кодовое слово, которое образовано из букв, помечающих ребра, попадающиеся при движении от корня к выбранному листу. Отличительной особенностью приведённого метода кодирования считается тот факт, что найденные коды являются префиксными.
Понятно, что стоимость хранения информации, которая закодирована с помощью Т-дерева, равняется суммарному значению длины путей от корня ко всем листам дерева, взвешенных частотой соответствующего кодового слова или длиной взвешенных путей. Например, при кодировке символов в стандарте ASCII, каждый символ представляет собой кодовое слово фиксированной, а именно равной восьми битам, длины. Стоимость хранения 39 кодовых слов в кодировке ASCII равна 312, вне зависимости от относительной частоты отдельных символов в этом потоке.
Алгоритм Хаффмана даёт возможность уменьшения стоимости сохранения потока кодовых символов путем необходимого подбора длины кодовых слов, который может минимизировать длину взвешенных путей. Дерево, обладающее минимальной длиной путей, называется деревом Хаффмана.
Стандартный алгоритм Хаффмана на входе имеет таблицу частот встречаемости символов в сообщении. Затем на базе данной таблицы должно быть построено дерево кодирования Хаффмана (Н-дерево).
Алгоритм декодирования подразумевает просмотр потоков битов и синхронное передвижение от корня вниз по дереву Хаффмана.
