A memory-efficient huffman decoding algorithm

To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory-efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(logn)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from logn to Sigma(n)(i=1) [i/(h - 1)] x w(i)logh/Sigma w(i), where w(i) is the frequency for i(th) symbol and h is a pre-defined value.