Якимов Антон Сергеевич1, Николаев Сергей Валерьевич2, Корнилков Алексей Петрович3 1Приамурский государственный университет имени Шолом-Алейхема, студент 2Приамурский государственный университет имени Шолом-Алейхема, студент 3Приамурский государственный университет имени Шолом-Алейхема, старший преподаватель кафедры информатики и вычислительной техники
Аннотация Цель данной статьи разработать учебный шаблон, который позволит приобрести необходимые навыки и знания для понимания, использования и реализации кода Хаффмана. Для реализации поставленной задачи используется язык PHP.
IMPLEMENTATION OF HUFFMAN CODE IN PHP
Yakimov Anton Sergeevich1, Nikolaev Sergey Valer'evich2, Kornilkov Alexey Petrovich3 1Sholom-Aleichem Priamursky State University, Student 2Sholom-Aleichem Priamursky State University, Student 3Sholom-Aleichem Priamursky State University, Senior Lecturer, Department of Computer Science
Abstract The purpose of this paper to develop a training template that will acquire the necessary skills and knowledge to understand, use and implementation of the Huffman code. To perform this task, use language PHP.
Библиографическая ссылка на статью:
Якимов А.С., Николаев С.В., Корнилков А.П. Реализация кода Хаффмана на языке PHP // Современные научные исследования и инновации. 2015. № 2. Ч. 1 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/02/46793 (дата обращения: 12.01.2021).
Код Хаффмана является одним из самых распространенных методов сжатия данных. Разработан в 1952 г. [1] и до сих пор используется архиваторами либо полностью, либо как один из этапов многоуровневого сжатия. Для профессий, связанных с информационными технологиями, понимание основных идей кода Хаффмана и методов его реализации, будет актуально и полезно.
Код Хаффмана часто описывается в книгах по информационной безопасности [2, 3, 4] Теоретические основы алгоритма, так же описаны во многих источниках [5, 6]. Алгоритм построение бинарного дерева на Java Script описан в работе А.Б. Веретенникова [7]. С.И. Горяинов рассмотрел перестройку бинарных деревьев в алгоритме Хаффмана [8]. Реализацию алгоритма Хаффмана с заданной длиной разбиений входного потока на машинах Тьюринга с почти линейным временем показал М.А.Герасимов [9]. Зарубежные ученые так же применяют рассматриваемый алгоритм в своих исследованиях [10, 11].
Рассмотрим алгоритм на примере кодировки текста. Существует некий алфавит и каждому символу отводится фиксированное количество бит. Алгоритм Хаффмана кодирует каждый символ в зависимости от частоты использования символа. Символ, который чаще других используется, присваивается короткий двоичный код, следовательно, тот символ, который используется реже всего, имеет самый длинный код. После кодировки, сообщение будет весить меньше, чем изначально.
Представим алгоритм на конкретном примере. Закодируем сообщение: «теория_информации». Частоты каждого символа представлены в табл.1.
Таблица 1 – Сообщение «теория_информации»
т
е
о
р
и
я
_
н
ф
м
а
ц
1
1
2
2
4
1
1
1
1
1
1
1
Теперь будем складывать две самые маленькие частоты. В данном случае сложим частоты символов «т» и «е», а в новом таблице сумму их частот подпишем как «те» (табл.2).
Таблица 2 – Первый этап кодирования сообщения
те
о
р
и
я
_
н
ф
м
а
ц
2
2
2
4
1
1
1
1
1
1
1
Теперь снова ищем два символа с наименьшими частотами. Это символы «я» и «_» (табл.3).
Таблица 3 – Второй этап кодирования сообщения
те
о
р
и
я_
н
ф
м
а
ц
2
2
2
4
2
1
1
1
1
1
Продолжим эти действия до тех пор, пока не останется два столбца. Столбцы, которые будем складывать, выделим полужирным шрифтом (табл.4-11).
Таблица 4 – Третий этап кодирования сообщения
те
о
Р
и
я_
нф
м
а
Ц
2
2
2
4
2
2
1
1
1
Таблица 5 – Четвертый этап кодирования сообщения
те
о
Р
и
я_
нф
ма
ц
2
2
2
4
2
2
2
1
Таблица 6 – Пятый этап кодирования сообщения
те
о
Р
и
я_
нф
мац
2
2
2
4
2
2
3
Таблица 7 – Шестой этап кодирования сообщения
тео
р
И
я_
нф
мац
4
2
4
2
2
3
Таблица 8 – Седьмой этап кодирования сообщения
тео
ря_
И
нф
мац
4
4
4
2
3
Таблица 9 – Восьмой этап кодирования сообщения
тео
ря_
И
нфмац
4
4
4
5
Таблица 10 – Девятый этап кодирования сообщения
теоря_
и
нфмац
8
4
5
Таблица 11 – Десятый этап кодирования сообщения
теоря_
инфмац
8
9
Построим бинарное дерево по таблицам. Левым ветвям будем приписывать в коде 0, а правым ветвям 1. Через дефис будем указывать кодировку символа.
Рисунок 1 – Бинарное дерево
В итоге получилась следующая кодовая таблица (табл.12).
Код Хаффмана является префиксным кодом, т.е. код символа не является частью кода другого символа, следовательно, интерпретируется однозначно. Сравним вес сообщения закодированного с помощью ASCII и сообщение, закодированное по алгоритму Хаффмана.
Сообщение, закодированное с помощью алгоритма Хаффмана, весит примерно в два раза меньше.
Реализация приложения на PHP.
Приложение должно выполнять следующие действия:
Составить таблицу частот (вероятностей появления символов)
Построить бинарное дерево
Сгенерировать код для каждого символа
Вывести закодированный результат
Приводим образец кода, в данном случае, функцию составления таблиц частот (рис.2).
Рисунок 2 – Образец кода
Для ввода сообщения приложение выглядит на рис.3.
Рисунок 3 – Ввод сообщения
После ввода сообщения и нажатия кнопки «Сжать», приложение выдает результат (рис.4).
Рисунок 4 – Сгенерированное сообщение
Отметим при этом, что закодированное сообщение в приложении отличается от варианта выше. Выведем кодовую таблицу для сравнения с таблицей в разделе теория (рис.5).
Рисунок 5 – Кодовая таблица
Заметим, что код каждому символу присвоен другой. Вызвано это тем, что изначально много символов, с одинаковой частотой и в процессе построение дерева, часто был выбор в сложении частот, который при этом не влиял на эффективность алгоритма, или распределение символа в другую ветвь, что также влияло на итоговый код символа. Однако по-прежнему самый частый символ «и» закодирован в 2 бита, символы «р» и «о» 3 битами, что в итоге говорит о том, что вес закодированного сообщения по-прежнему равен 58 бит.
Проведенное исследование может быть использовано в преподавании различных дисциплин, связанных с передачей информации.
Библиографический список
Huffman D. A. et al. A method for the construction of minimum redundancy codes // Proceedings of the IRE. 1952. Т. 40. №. 9. С. 1098-1101.
Горяинов С.И. Перестройка бинарных деревьев в алгоритме Хаффмана // Программные системы и вычислительные методы. 2014. № 4. С. 464-471.
Герасимов М.А. Реализация алгоритма Хаффмана с заданной длиной разбиений входного потока на машинах Тьюринга с почти линейным временем // Вестник Санкт-Петербургского университета. Серия 10: Прикладная математика. Информатика. Процессы управления. 2010. № 3. С. 100-105.
Liu Y. K., Žalik B. An efficient chain code with Huffman coding // Pattern Recognition. 2005. Т. 38. №. 4. С. 553-557.
Lin Y. K., Huang S. C., Yang C. H. A fast algorithm for Huffman decoding based on a recursion Huffman tree // Journal of Systems and Software. 2012. Т. 85. №. 4. С. 974-980.