Memory efficient data structure for static huffman tree

Abstract

Since the discovery of the Huffman encoding scheme in 1952, Huffman encoding scheme is widely used in text, image and video compression. Huffman coding has been subjected to numerous investigations in the past 50 years. Many techniques have been presented since then. But still this is an important field as it significantly reduces storage requirement and communication cost. In this research, we have directed our work to a new memory efficient data structure for the static Huffman tree. If Huffman Coding technique is applied again and again on a file then it is called Repeated Huffman Coding. If Huffman coding technique is applied block by block in a large file then it is called Block Huffman coding. Memory efficient representation of Huffman tree increases the compression ratio of Repeated and Block Huffman coding. It also reduces the cost of transmission. The presented algorithm requires I{n log,l + x + I + !log, (n /I)} / sl memory spaces in the worst case to represent a Huffman tree, where n is the number of source symbols, x is the size of the alphabet set and I is the depth of the Huffman tree, which is an improvement over the existing technique that requires (n+l) and (n+4l) memory spaces in the worst case. We also presented a new memory efficient Huffman decoding. In this decoding process we do not need to reconstruct Huffman table or tree in the receiver end for decoding a compressed file. This technique may be used in a device with small amount of memory.