Goryainov S.I. Rebuilding of binary trees in Huffman algorithm

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: