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(log n)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from log n to Σ_iⁿ┌i/(h - 1)┐ × w_ilog h/Σw_i, where w_i is the frequency for i_th symbol and h is a pre-defined value.