Горяинов С.И. Перестройка бинарных деревьев в алгоритме Хаффмана

Аннотация: Предметом данного исследования является время, затрачиваемое на полную перестройку бинарного дерева, а также степень сжатия текста в алгоритме Хаффмана. В работе определяются зависимости времени работы программы и степени сжатия текста от длины строки при произвольном количестве уникальных символов, при фиксированном количестве уникальных символов, а также при фиксированной длине строки и различном количестве уникальных символов. Показано, что время, требуемое на перестройку бинарного дерева, составляет незначительную часть общего времени работы программы. Алгоритм построения кодов символов включает следующие этапы: 1) считывание файла, содержащего текст; 2) подсчёт частот различных символов текста; 3) заполнение массивов данных и их сортировка; 4) построение бинарного дерева. В ряде источников утверждается, что подход, использующий полную перестройку бинарного дерева неэффективен. Однако это утверждение не подкреплено соответствующими фактами. В данной работе с помощью анализа текстов различной длины и количеством уникальных символов, представленного в табличном и графическом виде, показано, что перестройка бинарного дерева незначительно влияет на время работы программы.

Ключевые слова:

Abstract: the subject of this study is the time required to complete a full rebuilding of a binary tree, as well as the degree of compression of text in Huffman algorithm. The author defines dependencies of both time of program execution and the level of text compression from the length of string formed of random set of unique symbols, from the length of string if it consists of fixed set of unique symbols and in the case of the fixed length of string having different number of unique symbols. It is shown that the time required to rebuild a binary tree is a small part of the total time of the program execution. An algorithm for constructing the character codes comprises the following steps: 1) reading the text from file; 2) counting different symbols of the text; 3) filling and sorting the data array; 4) building binary tree. Some sources state that the approach with full rebuilding of a binary tree is ineffective. However, that statement is not supported by relevant facts. The author proves through the analysis of texts of varying length and different sets of unique characters, presented in tabular and graphical form, that the rebuilding of a binary tree has little effect on the program execution time.

Keywords: