Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2002 Copyright 2002 University of Bonn, Department of Computer Science, Abt. V
8977

Jan 18, 2002

Approximating Huffman Codes in Parallel (Revised Version)
Piotr Berman, Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work.

Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) and with n processors. This represents a useful improvement since most practical situations satisfy H = O(log n).

Last Change: 11/05/14 at 10:25:49
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V