An Efficient Algorithm of Huffman Decoder with Nearly Constant Decoding Time

P.-C. Wang, C.-L. Lee, and H.-Y. Chang (Taiwan)


Huffman codes, decoding, and data compression.


This paper introduces a Huffman decoding algorithm based on the single-side growing Huffman tree. The proposed scheme exploits an intrinsic property of the single-side growing Huffman tree to utilize the instructions of the mod ern processor. The data structure is proved to have lin ear space complexity O(d + 2n), where d is the maximal length of the Huffman codes and n is the number of sym bols. More importantly, each Huffman decoding could be carried out by a constant number of instructions and two memory accesses, regardless the length of Huffman codes. As demonstrated in the experimental results, the proposed scheme yields a nearly constant decoding time and outper form the existing schemes. Our source code is publicly available.

Important Links:

Go Back