The construction of Huffman-equivalent prefix code in NC
Author:
Open Access
- 1 July 1987
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 18 (4) , 54-61
Abstract
In this paper, we show that an optimal prefix code (Huffman-equivalent code) over Σ = {0,1,...,σ} for any n letters a 1 ,..., a n of frequency f 1 ,..., f n can be constructed in O (log 2 n ) time, using only polynomial number of processors. This is done by a uniform reduction of optimal prefix coding problem to a min-plus circuit value problem of polynomial size and linear degree. Thus we can use the parallel circuit evaluation algorithms presented in [7] and [8] to construct a time-efficient and processor-efficient parallel algorithm for optimal prefix coding problem.Keywords
This publication has 8 references indexed in Scilit:
- Optimal Tree Contraction in the EREW Model1988
- Dynamic parallel complexity of computational circuits1987
- A logarithmic time sort for linear size networksJournal of the ACM, 1987
- Efficient parallel evaluation of straight-line code and arithmetic circuits1986
- Parallel tree contraction and its application1985
- Sorting inc logn parallel stepsCombinatorica, 1983
- Two inequalities implied by unique decipherabilityIEEE Transactions on Information Theory, 1956
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952