The construction of Huffman-equivalent prefix code in NC
Shang‐Hua Teng · ACM SIGACT News · 1987
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.