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
