Код Хаффмана

Под кодированием символов из некоторого множества будем понимать установление соответствия каждому из них некоторой битовой последовательности. Мы уже давно знакомы с некоторыми кодировки. Например с 7-битной ASCII кодировкой или 8-битной Windows-1251. Это так намазываемые равномерные кодировки. Это означает, что длина кодирующей последовательности одинакова для всех символов.
Идея кодирования Хаффмана состоит в отказе от равномерности кода — символы, которые встречаются в кодируемом тексте чаще предполагается кодировать более короткими битовыми последовательностями. Такие коды в которых длина кодов различных символов отличается, называют неравномерными.
Алгоритм Хафмана, является примером жадного алгоритма в котором строится бинарное дерево листьями которого являются символы текста. Глубина листа (расстояние до корня) тем меньше, чем выше встречаемость символа в тексте. Бинарное дерево кода строится путем последовательного объединения наиболее редких символов. При этом образуется новая вершина, соответствующая множеству объединяемых символов. Новой вершине приписывается частота равная сумме частот объединяемых вершин.
Процесс объединения продолжается до получения дерева. Т.е. в списке множеств символов останется только один элемент — объединение всех символов текста. Частота этого последнего узла равна количеству символов в тексте.
Например, возьмем английскую поговорку «so many men, so many minds». Сосчитаем сколько раз встретилась каждая буква и построим дерево префиксного кодирования по алгоритму Хаффмана. Получится что-то вроде такого:

so many men, so many minds

so many men, so many minds

Если одно из детей вершины обозначить через 0, а другого — 1, то путь от корня к листику можно задать последовательностью нулей и единиц. Чем дальше от корня будет расположен лист, тем длиннее будет код. Поскольку мы каждый раз объединяли вершины с наименьшей частотой, у «редких» вершин будет длинный код, а у частых — короткий.

Для написания программы решения задачи я использовал очередь с приоритетами. Программа генерирует код и печатает текст, запроса к сервису Google, который рисует соответствующее дерево.
Сам код приведен ниже.

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

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)