Применение теории графов

Графы широко используются в различных отраслях науки.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо «да», либо «нет». Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. «Опрос» завершается, когда удается установить то, что требовалось.

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

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

Алгоритм Хаффмана — адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

Этот алгоритм был разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

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

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

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

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

Кодирование — это преобразование сообщений в сигнал, т. е. преобразование сообщений в кодовые комбинации.

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

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

Символы входного алфавита образуют список свободных узлов.

Каждый лист имеет вес, который равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.

Обратным процессом кодирования является декодирование.

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

Рассмотрю данный алгоритм Хаффмана на придуманных мною задачах.

Задача № 1. Закодировать по методу Хаффмана сообщение: