Реализация алгоритма Хаффмана

ВВЕДЕНИЕ
Архивация данных является процессом сжатия и сохранения информации на длительный период времени. Архивные данные могут быть использованы для восстановления информации после сбоя системы или удаления файлов. Кроме того, архивирование помогает уменьшить размер файлов, что экономит дисковое пространство и особенно актуально при передаче данных через вычислительные сети и Интернет.
Алгоритм Хаффмана — это метод сжатия данных, который используется в различных архиваторах, например, PKZIP 2, LZH и других [1].
Целью курсовой работы является реализация алгоритма Хаффмана.
Для достижения цели были поставлены следующие задачи:
• ознакомиться с алгоритмом Хаффмана и вариантами его реализации;
• разработать алгоритмы программной реализации;
• создать программу, реализующую разработанные алгоритмы;
• протестировать созданное программное решение.
В разделе 1 приводится общее описание алгоритма Хаффмана.
В разделе 2 описывается вариант реализации алгоритма.
В разделе 3 приводится программная реализация алгоритмов.
В разделе 4 представлены результаты тестирования созданной программы.
 
1 Теоретические сведения об алгоритме Хаффмана
1.1 Алгоритм Хаффмана
Идея состоит в том, чтобы использовать кодирование переменной длины [1,2]. Для разработки алгоритма, который может представлять тот же фрагмент текста используя меньшее количество битов, можно использовать тот факт, что одни символы встречаются в тексте чаще, чем другие.
При кодировании с переменной длиной, символам присваиваются коды с различным количеством битов в зависимости от их частоты их появления в данном тексте. Таким образом, некоторые символы могут в конечном итоге занимать один бит, а некоторые — два бита, некоторые могут быть закодированы с использованием трех битов и так далее.
Проблема с кодированием переменной длины заключается в обратном декодировании закодированных данных. а именно, если коды символов имеют переменную длину, появляется проблема однозначного распознавания кода символа вне зависимости от длин кодов.
Рассмотрим пример кодирования строки символов переменными кодами, приведенный на рисунке 1.1.

Рисунок 1.1. Пример кодирования
Как видно из рисунка, закодированную строку нельзя однозначно декодировать, т.к. результат зависит от разбиения кода на фрагменты, а это можно сделать разными способами, что продемонстрированно на рисунке.
Для однозначного декодирования фрагмента, код должен удовлетворять условию Фано [3], т.е. для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.
Алгоритм Хаффмана основан на построении префиксного кодирования алфавита с минимальной избыточностью [4,5]. Это означает, что помимо соблюдения условия Фано, обеспечивающего однозначное декодирование, символам с большим числом вхождений (или большей вероятностью появления) в кодируемом сообщении ставятся в соответствие более короткие коды.
Пример такого кода приведен на рисунке 1.2.

Рисунок 1.2. Код Хаффмана
Во втором столбце таблицы приведена частота встречи символов в исходном сообщении. Коды удовлетворяют условию Фано и закодированное сообщение может быть интерпретировано единственным верным образом.
Родственным методом для кодирования Хаффмана является кодирование Шеннона-Фано [6]. Отличие методов в том, что алгоритм создания кода Хаффмана формирует дерево кодов снизу-вверх, а Шеннона-Фано - сверху вниз.
В результате кодирование по Хаффману всегда дает оптимальные коды, а по Шеннону-Фано иногда возможны ситуации, когда используется немного больше бит и распределение кодов не оптимально.

1.2 Объектно-ориентированное программирование и C++
Объектно-ориентированный подход – это парадигма программирования, набор правил и критериев по которым создается программный код. Такой подход подразумевает использование при построении программ набор взаимодействующих друг с другом объектов [7].
Данный подход появился в 50-60х годах прошлого века при проектировании подходов к разработке искусственного интеллекта. Такая идея для моделирования ИИ возникла, когда встал вопрос моделирования человеческого восприятия. Человек воспринимает мир как совокупность объектов, с которыми он взаимодействует, наблюдает и использует [8].