In this article, we discuss the problem of enhancing the speed of Huffman decoding. One viable solution to this problem is the multibit scheme which uses the concept of k-bit trees to decode up to k bits at a time. A linear-time optimal solution for the mapping of 2-bit trees into memory is presented. The optimal solution is derived by formulating the memory mapping problem as a binary string mapping problem and observing that at most four different 4-bit patterns can occur within any 2-bit Huffman tree. In addition to reducing the processing time of decoding, the optimal scheme is storage efficient, does not require changes to the encoding process, and is suitable for hardware implementations.
then the Huffman tree minimizes the quantity ji, p, * dj.
Huffman encoding has been used in Liu and Yu (199 l), along with dictionary compression for the efficient storage of large databases. Huffman compression is also used in the JPEG image compression standard to store the AC values obtained via DCT coding. Huffman encoding, arithmetic coding (Witten, Neal, & Cleary, 1987) and the LZW scheme (Welch, 1984) are used in conjunction with lossy schemes to improve the fidelity of compressed images at a given level of compression (Bassiouni, 1993).