首页 | 本学科首页   官方微博 | 高级检索  
     


Parallel construction of binary trees with near optimal weighted path length
Authors:D G Kirkpatrick  T Przytycka
Affiliation:(1) Department of Computer Science, The University of British Columbia, V6T 1Z4 Vancouver, British Columbia, Canada;(2) Odense University, Odense, Denmark
Abstract:We present parallel algorithms to construct binary trees with almost optimal weighted path length. Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present anO (logn)-time andn(log lognl logn)-EREW-processor algorithm which constructs a tree with error less than 0.18, andO (k logn log* n)-time andn-CREW-processor algorithm which produces a tree with error at most l/n k , and anO (k 2 logn)-time andn 2-CREW-processor algorithm which produces a tree with error at most l/n k . As well, we describe two sequential algorithms, anO(kn)-time algorithm which produces a tree with error at most l/n k , and anO(kn)-time algorithm which produces a tree with error at most 
$$1/2^{n2^k }$$
. The last two algorithms use different computation models.The first author's research was supported in part by NSERC Research Grant 3053. A part of this work was done while the second author was at the University of British Columbia.
Keywords:Huffman trees  Near optimal trees  Optimal trees  Parallel algorithms  PRAM  Prefix codes
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号