Eng During last 365 days Approved articles: 2071,   Articles in work: 296 Declined articles: 786 
Library

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

Published in journal "Software systems and computational methods", 2014-4 in rubric "Data encryption and data protection", pages 464-471.

Resume: 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

DOI: 10.7256/2305-6061.2014.4.13755

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

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

Correct link to this article:
just copy this link to clipboard