Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

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:

Huffman algorithm, binary tree rebuilding, compression of text data, program execution time, thrifty information encoding, prefix encoding, unique symbols, the degree of text compression, length of input string, average approximation error


This article can be downloaded freely in PDF format for reading. Download article


References
1. Aleksandrov O.E. Kompressiya dannykh ili izmerenie i izbytochnost' informatsii. Metod Khaffmana: Metodicheskie ukazaniya k laboratornoy rabote / O. E. Aleksandrov – Ekaterinburg: UGTU–UPI, 2000. – 36 s.
2. Kudryashov B.D. Teoriya informatsii: Uchebnik dlya vuzov. – SPb.: Piter, 2009. – 320 s.: il. – (Seriya «Uchebnik dlya vuzov»)
3. Kolmogorov A.N. Teoriya informatsii i teoriya algoritmov. – M.: Nauka, 1987. – 304 s.
4. Svirid Yu.V. Osnovy teorii informatsii: Kurs lektsiy. – Mn.: BGU, 2003. – 139 s.
5. Smirnov M.A. Obzor primeneniya metodov bezushcherbnogo szhatiya dannykh v SUBD: Rukopis'. – SPb.: GUAP, 2004. – 58 s.
6. Shennon K. Raboty po teorii informatsii i kibernetike. – M.: Izdatel'stvo inostrannoy literatury, 1963. – 825 s