Huffman coding with unequal letter costs

ABSTRACT

(MATH) In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size &Sgr;_w freq w, &124;c(w)&124;. The problem has a well-known polynomial-time algorithm due to Huffman [15].Here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. The goal is to minimize the weighted average codeword length &Sgr;_w freq (w) cost(c(w)), where cost s is the sum of the (possibly non-uniform) lengths of the letters in s. Despite much previous work, the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm. Here we describe a polynomial-time approximation scheme (PTAS) for the problem.

REFERENCES

• 1: Shimon Even Abraham~Lempel and Martin Cohen. An algorithm for optimal prefix parsing of a noiseless and memoryless channel. IEEE Transactions on Information Theory, 19(2):208--214, March 1973.
• 2: Julia Abrahams. Code and parse trees for lossless source encoding. Communications in Information and Systems, 1(2):113--146, April 2001.
• 3: Doris Altenkamp , Kurt Mehlhorn, Codes: Unequal Probabilities, Unequal Letter Cost, Journal of the ACM (JACM), v.27 n.3, p.412-427, July 1980 [doi>10.1145/322203.322205]
• 4: Toby Berger and Raymond~W. Yeung. Optimum 1-ended binary prefix codes. IEEE Transactions on Information Theory, 36(6):1434--1441, November 1990.
• 5: N. M. Blachman. Minimum cost coding of information. IRE Transactions on Information Theory, PGIT-3:139--149, 1954.
• 6: N. M. Blachman. Minimum cost coding of information. IRE Transactions on Information Theory, PGIT-3:139--149, 1954.
• 7: N. Cot. Complexity of the variable-length encoding problem. In Proc. 6th Southeast Conference on Combinatorics, Graph Theory and Computing, pages 211--244, 1975.
• 8: Norbert Cott. Characterization and Design of Optimal Prefix Codes. PhD Thesis, Stanford University, Department of Computer Science, June 1957.
• 9: I. Csisz'ar. Simple proofs of some theorems on noiseless channels. Inform. Contr., 514:285--298, 1969.
• 10: E. N. Gilbert. How good is morse code. Inform Control, 14:585--565, 1969.
• 11: E. N. Gilbert. Coding with digits of unequal costs. IEEE Trans. Inform. Theory, 41:596--600, 1995.
• 12: M. Golin and G. Rote. A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs. IEEE Transactions on Information Theory, 44(5):1770--1781, 1998.
• 13: Mordecai J. Golin , Neal Young, Prefix Codes: Equiprobable Words, Unequal Letter Costs, SIAM Journal on Computing, v.25 n.6, p.1281-1292, Dec. 1996 [doi>10.1137/S0097539794268388]
• 14: K. Hinderer. On dichotomous search with direction-dependent costs for a uniformly hidden objec. Optimization, 21(2):215--229, 1990.
• 15: D. A. Huffman. A method for the construction of minimum redundancy codes. In Proc. IRE 40}, volume 10, pages 1098--1101, September 1952.
• 16: K. A. S. Immink. Codes for Mass Data Storage Systems. Shannon Foundations Publishers, 1999.
• 17: I. Itai. Optimal alphabetic trees. SIAM J. Computing, 5:9--18, 1976.
• 18: Sanjiv Kapoor , Edward M. Reingold, Optimum lopsided binary trees, Journal of the ACM (JACM), v.36 n.3, p.573-590, July 1989 [doi>10.1145/65950.65955]
• 19: Richard Karp. Minimum-redundancy coding for the discrete noiseless channel. IRE Transactions on Information Theory, IT-7:27--39, January 1961.
• 20: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 21: R. M. Krause. Channels which transmit letters of unequal duration. Inform. Contr., 5:13--24, 1962.
• 22: R.S. Marcus. Discrete Noiseless Coding. M.S. Thesis, MIT E.E. Dept, 1957.
• 23: K. Mehlhorn. An efficient algorithm for constructing nearly optimal prefix codes. IEEE Trans. Inform. Theory, 26:513--517, September 1980.
• 24: Phillip G. Bradford , Mordecai J. Golin , Lawrence L. Larmore , Wojciech Rytter, Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property, Proceedings of the 6th Annual European Symposium on Algorithms, p.43-54, August 24-26, 1998
• 25: Y. Perl , M. R. Garey , S. Even, Efficient Generation of Optimal Prefix Code: Equiprobable Words Using Unequal Cost Letters, Journal of the ACM (JACM), v.22 n.2, p.202-214, April 1975 [doi>10.1145/321879.321883]
• 26: A. De Santis R. M. Capocelli and G. Persiano. Binary prefix codes ending in a 1. IEEE Transactions on Information Theory, 40(4):1296--1302, July 1994.
• 27: Shlomi Dolev , Ephraim Korach , Dmitry Yukelson, The sound of silence—guessing games for saving energy in mobile environment, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.273, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301377]
• 28: L. E. Stanfel, Tree Structures for Optimal Searching, Journal of the ACM (JACM), v.17 n.3, p.508-517, July 1970 [doi>10.1145/321592.321601]
• 29: B. Varn. Optimal variable length codes (arbitrary symbol cost and equal code word probability). Information Control, 19:289--301, 1971.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms