РЕАЛИЗАЦИЯ  АЛГОРИТМА  ХАФФМАНА  НА  ЯЗЫКЕ  С++  С  ПОМОЩЬЮ  БИНАРНЫХ  ДЕРЕВЬЕВ

Горяинов  Сергей  Игоревич

студент  3  курса,  кафедра  прикладной  математики  Миасского  филиала  ЧелГУ,  РФ,  г.  Миасс

E -mail:  goryainovsergey@gmail.com

Гудков  Владимир  Юльевич

научный  руководитель,  д-р  физ.-мат.  наук,  доцент  кафедры  прикладной  математики  Миасского  филиала  ЧелГУ,  РФ,  г.  Миасс

Иванова  Марина  Кронидовна

научный  руководитель,  старший  преподаватель  кафедры  прикладной  математики  Миасского  филиала  ЧелГУ,  РФ,  г.  Миасс

Проблема  экономного  кодирования  информации  возникла  в  начале  70-х  годов  прошлого  века,  но  остаётся  актуальной  и  сегодня.  В  настоящее  время  используется  ряд  алгоритмов  сжатия  текстовых  данных,  таких  как  арифметическое  кодирование,  методы  Зива-Лемпела,  дифференциальное  кодирование  и  др.  Алгоритм  Хаффмана  —  классический  вариант  адаптивного  алгоритма  оптимального  префиксного  кодирования  информации  с  минимальной  избыточностью.  Как  метод  сжатия  данных  без  потерь,  он  основан  на  устранении  избыточности  представления  информации.  Экономное  кодирование  достигается  за  счет  представления  маловероятных  событий  более  длинными  словами,  чем  событий  с  высокой  вероятностью  наступления.  Популярность  данного  метода  в  программах  сжатия  данных  обусловлена  простотой  и  скоростью  декодирования,  а  также  несложной  аппаратной  реализацией.

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

Перейдём  к  описанию  алгоритма.

На  вход  программы  подаётся  файл,  содержащий  текст.  Затем  осуществляется  анализ  данного  текста,  выполняется  подсчёт  частот  находящихся  в  нём  различных  символов,  заполнение  массивов  данных  и  их  сортировка.

Следующий  шаг  —  построение  бинарного  дерева.  Элементы,  имеющие  большие  частоты,  располагаются  справа,  а  элементы  с  меньшими  частотами  —  слева.

При  построении  кода  для  каждого  символа  программа  проходит  по  левым  ссылкам  узлов  дерева  до  первого  встреченного  листа  и  обнаруживает  первый  элемент  для  объединения.  После  этого  лист  удаляется  из  дерева,  и  начинается  аналогичный  проход  для  поиска  второго  элемента,  который  после  обнаружения  также  удаляется  из  дерева.

К  коду  всех  символов  первого  из  найденных  листов  добавляется  единица,  к  коду  всех  символов  второго  листа  добавляется  ноль.  Так,  например,  если  символ  «а»  имел  код  01,  то,  если  он  окажется  в  первом  из  найденных  листов,  код  примет  вид  101,  если  же  во  втором,  то  001.

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

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

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

После  этого  выводится  исходная  строка  и  количество  бит,  занимаемых  этой  строкой,  закодированная  строка  и  количество  бит,  которые  требуются  для  ее  кодирования.

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

В  таблице  1  приведены  зависимости  времени  работы  программы  от  длины  строки  и  степень  сжатия  от  числа  уникальных  элементов.  Для  анализа  выбраны  тексты  длиной  около  3000,  10000,  30000  и  50000  символов.

Таблица  1.

Зависимость  времени  работы  программы  от  длины  строки  и  степени  сжатия  от  числа  уникальных  элементов

Средний  коэффициент  сжатия  для  таких  текстов  равен  1,5.

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

Таблица  2.

Зависимость  времени  работы  программы  от  длины  входной  строки  при  фиксированном  количестве  уникальных  символов

Зависимость  времени  работы  от  длины  входной  строки  символов  представлена  графически  (рисунок  1),  и  на  указанном  участке  соответствует  функции,  заданной  уравнением 

со  средней  ошибкой  аппроксимации  1  %.

Рисунок  1.  Зависимость  времени  работы  программы  от  длины  строки  символов

В  таблице  3  представлены  результаты  обработки  текстов,  в  которых  частоты  символов  и  их  общая  длина  постоянны,  изменяется  только  количество  уникальных  символов.

Таблица  3.

Зависимость  времени  работы  программы  и  степени  сжатия  от  числа  уникальных  символов

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

Рисунок  2.  Зависимость  времени  работы  программы  от  числа  уникальных  символов

График  зависимости  степени  сжатия  от  числа  уникальных  символов  при  одинаковых  частотах  всех  символов  представлен  на  рис.  3.  Полученная  линия  близка  к  логарифмической  функции

,

средняя  ошибка  аппроксимации  которой  составляет  3,4  %.

Рисунок  3.Зависимость  степени  сжатия  от  числа  уникальных  символов

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

Анализируя  зависимости,  представленные  на  рисунке  1  и  на  рисунке  2,  можно  сделать  вывод  о  том,  что  время,  требуемое  на  перестройку  бинарного  дерева,  составляет  малую  часть  общего  времени  работы  программы,  затрачиваемого  на  анализ  строки,  на  последующее  ее  кодирование  и  на  вычисление  степени  сжатия.

График,  представленный  на  рисунке  1,  описывается  уравнением  .  На  этом  графике  представлена  зависимость  времени  работы  программы  от  длины  строки  входных  символов.  При  этом  число  уникальных  символов  является  константой.  Это  означает,  что  время,  затрачиваемое  программой  на  работу  с  бинарным  деревом,  приблизительно  является  константой,  так  как  на  него  влияют  и  другие  процессы,  выполняемые  операционной  системой  в  данный  момент  времени.  Следовательно,  основная  часть  времени  тратится  на  анализ  входной  строки  и  ее  последующее  кодирование,  а  время,  затрачиваемое  на  работу  с  бинарным  деревом,  включая  его  перестройки,  не  оказывает  значительное  влияние.

График  зависимости,  представленные  на  рисунке  2,  описывается  линейным  законом.  На  данном  графике  описывается  зависимость  времени  работы  программы  от  количества  уникальных  символов.  Это  означает,  что  время,  затрачиваемое  на  анализ  входной  строки  и  ее  кодирование,  приблизительно  является  константой  или  меняется  незначительно,  а  основная  часть  времени  работы  программы  зависит  от  работы  с  бинарным  деревом.  Исходя  из  того,  что  время  работы  в  этом  случае  подчиняется  линейному  закону,  можно  сделать  вывод  о  том,  что  наличие  полной  перестройки  бинарного  дерева  в  ходе  работы  программы  хоть  и  оказывает  влияние  на  время  работы,  но,  всё  же,  не  слишком  значительное.  Этап  работы  с  бинарным  деревом  может  оказывать  большое  влияние  на  время  работы  программы  только  при  очень  больших  количествах  уникальных  символов.

Список  литературы:

1.Александров  О.Е.  Компрессия  данных  или  измерение  и  избыточность  информации.  Метод  Хаффмана:  Методические  указания  к  лабораторной  работе  /  О.Е.  Александров  Екатеринбург:  УГТУ–УПИ,  2000.  —  36  с.

2.Кудряшов  Б.Д.  Теория  информации:  Учебник  для  вузов.  СПб.:  Питер,  2009.  —  320  с.:  ил.  —  (Серия  «Учебник  для  вузов»).

3.Колмогоров  А.Н.  Теория  информации  и  теория  алгоритмов.  М.:  Наука,  1987.  —  304  с.

4.Свирид  Ю.В.  Основы  теории  информации:  Курс  лекций.  Мн.:  БГУ,  2003.  —  139  с.

5.Смирнов  М.А.  Обзор  применения  методов  безущербного  сжатия  данных  в  СУБД:  Рукопись.  СПб.:  ГУАП,  2004.  —  58  с.

6.Шеннон  К.  Работы  по  теории  информации  и  кибернетике.  М.:  Издательство  иностранной  литературы,  1963.  —  825  с.