Abstract:
Since the discovery of the Huffman encoding scheme in 1952, Huffman codes
have been widely used in the efficient storing of data, image and video. Huffman
coding has been subjected to numerous investigations in the past 60 years. Many
techniques have been proposed since then. But still this is an important field as it
significantly reduces storage requin:ment and communication cost. In this thesis,
"Study on Huffman Coding", we have directed our works mainly to Repeated
Huffman Coding that is a lossless compression technique.
The application of Huffman coding technique again and again on a file, then it is
called Repeated Huffman coding. While it is expected that encoded message
length will be smaller in every pass of Repeated Huffman coding, nevertheless
encoding the tree itself will be an overhead in each pass. So repetition count will
.depend upon how efficiently we can represent a Huffman tree.
A memory efficient representation of a Huffman tree is suggested in this thesis.
This representation is very important in the context of Repeated Huffman coding
where ultimate compression ratio depends upon the efficiency of encoding the
Huffman tree. It reduces overhead which incurs in every pass of Repeated
Huffman coding. Because of reduction of overhead, the Huffman Coding scheme
can be applied effectively on a file for a larger number of iterations.
The proposed algorithms require less than 15n/4l memory spaces in the worst case
to represent a Huffman tree for n distinct symbols, which is an improvement over
the existing technique that requires at most 13n/2l memory spaces.
Such a saving in the representation of Huffman trees will improve the
performance of the Repeated Huffman coding as well as Block Huffman coding
where multiple tree headers must be stored for a file oflarge size.
The tree clustering algorithm is also analyzed to get an optimal clustering of a
Huffman tree so that along with reduction of memory requirement search process
.for a symbol in a Huffman tree is speeded up.
