文章基本信息

标题：Approximating Huffman Codes in Parallel
本地全文：下载
作者：Piotr Berman ; Marek Karpinski ; Yakov Nekrich 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we present some 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)
关键词：Almost OptimalCodes , Approximation Algorithms , Huffman Codes , Optimal Time and Work. , Parallel algorithms