The construction of Huffman-equivalent prefix code in NC

ABSTRACT

In this paper, we show that an optimal prefix code (Huffman-equivalent code) over Σ = {0,1,...,σ} for any n letters a₁,...,a_n of frequency f₁,...,f_n can be constructed in O(log²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.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 2: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 3: [3] Gazit, H. Miller, G. L. Teng, S.-H. Optimal Tree Contraction in EREW Model. Tech. Rept., Univ. of Southern Calif. 1986.
• 4: [4] Huffman, D. A. A method for the Construction of Minimum Redundancy Codes. Proc. IRE pp. 1098- 1101, 1952.
• 5: [5] McMillan, B. Two Inequalities Implied by Unique Decipherability. IRE, Transaction on Information Theory pp. 185-189, 1956.
• 6: [6] Miller, G. L., Reif, J. H. Parallel Tree Contraction and its Application. In FOGS 85, 1985.
• 7: [7] Miller, G. L. Ramachandran, V., Kaltofen, E. Efficient Parallel Evaluation of Straight-line Code and Arithmetic Circuits. Tech. Rept., Univ. of Southern Calif. 1985.
• 8: G. Miller , S. Teng, Dynamic parallel complexity of computational circuits, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.254-263, January 1987, New York, New York, United States [doi>10.1145/28395.28423]
• 9: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Theory, Verification