Код Шеннона - Фано. Код Хаффмана

Введение

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

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

1. Уровень сжатия (compress rating) или отношение (ratio) объемов начального и конечного потоков.
2. Скорость исполнения сжатия, а именно, время, затрачиваемое на сжатие заданного объема информации из входного потока, до создания из него требуемого выходного потока.
3. Качественный показатель сжатия, а именно, значение, которое может показать на сколько сильно выполнено сжатие выходного потока, с помощью применения по отношению к нему повторного сжатия по такому же или другому алгоритму.

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

1. Алгоритмы поточного и словарного типа. К данной группе можно отнести алгоритмы категории RLE (run-length encoding), $LZ^*$ и другие. Характерной чертой всех алгоритмов данного типа считается тот факт, что при кодировании применяется не данные о частотах символов в сообщении, а информация о последовательностях, которые встречались ранее.
2. Алгоритмы, использующие статистический (энтропийный) принцип сжатия. Эта категория алгоритмов способна сжимать информацию за счет неравномерности частот, с которыми разные символы могут встречаться в сообщении. К алгоритмам данного типа следует отнести алгоритмы арифметического и префиксного кодирования (с использованием деревьев Шеннона - Фанно, Хаффмана, секущих).

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

Кодирование при помощи алгоритма Шеннона - Фано

Алгоритм Шеннона - Фано является один из первых созданных алгоритмов сжатия. В основу этого алгоритма положена идея отображения наиболее часто употребляемых символов при помощи более коротких кодов. Причем коды, которые получены при помощи алгоритма Шеннона - Фано, имеют свойство префиксности, то есть, ни один код не может быть началом никакого иного кода. Свойство префиксности способно гарантировать, что кодирование станет взаимно-однозначным. Алгоритм формирования кодов Шеннона - Фано может быть представлен следующим образом:

1. Необходимо выполнить разбиение алфавита на две составляющие, суммарные вероятности символов в которых являются максимально близкими друг к другу.
2. В префиксный код первой части символов следует добавить нуль, в префиксный код второй части символов следует добавить единицу.
3. Для каждой составляющей, имеющей не менее двух символов, следует рекурсивно исполнить шаги от первого до третьего.

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

«ААААБВГДЕЖ».

Соответствующее дерево Шеннона - Фано и коды, которые получены на его базе, изображены на рисунке ниже.

Рисунок 1. Дерево Шеннона - Фано и коды, которые получены на его базе. Автор24 — интернет-биржа студенческих работ

Если не использовать кодирование этого сообщения, то оно будет иметь объем в сорок бит (при условии кодирования каждого символа четырьмя битами), а при использовании алгоритма Шеннона - Фано:

4 • 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 бит.

То есть, размер сообщения сократился на 32.5 %.

Кодирование при помощи алгоритма Хаффмана

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

1. Весь набор символов алфавита следует представить в форме свободных узлов, причем вес узла должен быть пропорциональным частоте символа в сообщении.
2. Из совокупности свободных узлов следует выбрать два узла, имеющие минимальный вес, и создать новый (родительский) узел, имеющий вес, равный сумме весов выбранных узлов.
3. Эти выбранные узлы нужно удалить из перечня свободных, а сформированный на их базе родительский узел следует добавить в этот перечень.
4. Второй и третий шаги необходимо повторять до тех пор, пока в перечне свободных находится более чем один узел.
5. На базе сформированного дерева каждому символу алфавита должен быть присвоен префиксный код.
6. Сообщение следует кодировать при помощи сформированных кодов.

Рассмотрим тот же пример, который приводился и для алгоритма Шеннона - Фано. Дерево Хаффмана и коды, которые получены для сообщения «ААААБВГДЕЖ», изображены на рисунке ниже.

Рисунок 2. Дерево Хаффмана и коды, которые получены для сообщения «ААААБВГДЕЖ». Автор24 — интернет-биржа студенческих работ

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