A space-efficient Huffman decoding algorithm and its parallelism
This paper first transforms the Huffmann tree into a single-side growing Huffman tree, then presents a memory-efficient data structure to represent the single-side growing Huffman tree, which requires (n + d)[log(2)n]-bits memory space, 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(d)-time Huffman decoding algorithm. Using the same example, the memory required in our decoding algorithm is much less than that of [3], We finally modify our proposed data structure to design an O(1)-time parallel Huffman decoding algorithm on a concurrent read exclusive write parallel random-access machine (CREW PRAM) using d processors. (C) 2000 Elsevier Science B.V. All rights reserved.
decoding algorithm single-side growing huffman tree data structure huffman code parallel algorithm