A space-efficient Huffman decoding algorithm and its parallelism

✍ Scribed by Yih-Kai Lin; Kuo-Liang Chung

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 178 KB
• Volume: 246
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00080-8

✦ Synopsis

This paper ÿrst transforms the Hu man tree into a single-side growing Hu man tree, then presents a memory-e cient data structure to represent the single-side growing Hu man 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 Hu man tree. Based on the proposed data structure, we present an O(d)-time Hu man decoding algorithm. Using the same example, the memory required in our decoding algorithm is much less than that of [3]. We ÿnally modify our proposed data structure to design an O(1)-time parallel Hu man decoding algorithm on a concurrent read exclusive write parallel random-access machine (CREW PRAM) using d processors.