A Level-based Practical Parallel Algorithm for Huffman Encoding

The construction of optimal prefix codes plays a significant and influential role in applications concerning information processing and communication problems. For decades, different algorithms were proposed treating the issue of Huffman codes construction and various optimizations were introduced. In this paper we propose a detailed practical time-efficient parallel algorithm for generating Huffman codes on CREW PRAM model exploiting n processors, where n is equal to the number of symbols in the alphabet. We first compute the codeword length for each symbol concurrently with a direct parallelization of the Huffman tree construction algorithm alleviating the complexity of dealing with the original tree-like data structure, and then the Huffman codes corresponding to symbols are generated in parallel based on a recursive formula introduced in previous sequential methods. The proposed algorithm achieves an O(n) time in the worst case where we have a one-sided Huffman tree, which is rarely encountered in practice, and O(log((logn – 1)!)) in the best case where the Huffman tree is nearly balanced

کلیدواژه ها:

Data Structures ، Parallel Algorithms ، Optimal Prefix Codes ، Huffman Codes ، PRAM