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.
