Arithmetic coding revisited

ABSTRACT

Over the last decade, arithmetic coding has emerged as an important compression tool. It is now the method of choice for adaptive coding on myltisymbol alphabets because of its speed, low storage requirements, and effectiveness of compression. This article describes a new implementation of arithmetic coding that incorporates several improvements over a widely used earlier version by Witten, Neal, and Cleary, which has become a de facto standard. These improvements include fewer multiplicative operations, greatly extended range of alphabet sizes and symbol probabilities, and the use of low-precision arithmetic, permitting implementation by fast shift/add operations. We also describe a modular structure that separates the coding, modeling, and probability estimation components of a compression system. To motivate the improved coder, we consider the needs of a word-based text compression program. We report a range of experimental results using this and other models. Complete source code is available.

REFERENCES

• 1: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 2: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 3: BOOKSTEIN, A. AND KLEIN, S. T. 1993. Is Huffman coding dead?. Computing 50, 4, 279-296.
• 4: BURROWS, W. AND WHEELER, D.J. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124. Digital Equipment Corp., Maynard, MA.
• 5: CAPOCELLI, R. M. AND DE SANTIS, A. 1991. New bounds on the redundancy of Huffman codes. IEEE Trans. Inf. Theor. IT-37, 1095-1104.
• 6: CHEVION, D., KARNIN, E. D., AND WALACH, E. 1991. High efficiency, multiplication free approximation of arithmetic coding. In Proceedings of the 1991 IEEE Data Compression Conference, J. A. Storer and J. Reif, Eds. IEEE Computer Society Press, Los Alamitos, CA, 43-52.
• 7: CLEARY, J. G. AND WITTEN, I. g. 1984. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 396-402.
• 8: Gordon V. Cormack , R Nigel Horspool, Algorithms for adaptive Huffman codes, Information Processing Letters, v.18 n.3, p.159-165, March 1984 [doi>10.1016/0020-0190(84)90021-8]
• 9: G. V. Ormack , R. N. S. Horspool, Data compression using dynamic Markov modelling, The Computer Journal, v.30 n.6, p.541-550, Dec. 1987
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Peter M. Fenwick, A new data structure for cumulative frequency tables, Software—Practice & Experience, v.24 n.3, p.327-336, March 1994 [doi>10.1002/spe.4380240306]
• 12: Gennady Feygin , P. Glenn Gulak , Paul Chow, Minimizing excess code length and VLSI complexity in the multiplication free approximation of arithmetic coding, Information Processing and Management: an International Journal, v.30 n.6, p.805-816, 1994 [doi>10.1016/0306-4573(94)90008-6]
• 13: GALLAGER, R. G. 1978. Variations on a theme by Huffman. IEEE Trans. Inf. Theor. IT-24, 6 (Nov.), 668-674.
• 14: GALLAGER, R. a. AND VAN VOORHIS, D. C. 1975. Optimal source codes for geometrically distributed integer alphabets. IEEE Trans. Inf. Theor. IT-21, 2 (Mar.), 228-230.
• 15: GOLOMB, S.W. 1966. Run-length encodings. IEEE Trans. Inf. Theor. IT-12, 3 (July), 399-401.
• 16: CORPORATE Tech Correspondence, Technical correspondence, Communications of the ACM, v.31 n.9, p.1139-1140, Sept. 1988 [doi>10.1145/48529.315819]
• 17: Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
• 18: HORSPOOL, R. N. AND CORMACK, G.V. 1992. Constructing word-based text compression algorithms. In Proceedings of the 1992 IEEE Data Compression Conference, J. Storer and M. Cohn, Eds. IEEE Computer Society Press, Los Alamitos, CA, 62-71.
• 19: Paul G. Howard , Jeffrey Scott Vitter, Analysis of arithmetic coding for data compression, Information Processing and Management: an International Journal, v.28 n.6, p.749-763, Nov.–Dec. 1992 [doi>10.1016/0306-4573(92)90066-9]
• 20: HOWARD, P. G. AND VITTER, J. S. 1994. Arithmetic coding for data compression. Proc. IEEE 82, 6, 857-865.
• 21: HUFFMAN, D.A. 1952. A method for the construction of minimum-redundancy codes. Proc. Inst. Radio Eng. 40, 9 (Sept.), 1098-1101.
• 22: JIANG, J. 1995. Novel design of arithmetic coding for data compression. IEE Proc. Comput. Dig. Tech. 142, 6 (Nov.), 419-424.
• 23: D. W. Jones, Application of splay trees to data compression, Communications of the ACM, v.31 n.8, p.996-1007, Aug. 1988 [doi>10.1145/63030.63036]
• 24: Donald E. Knuth, Dynamic Huffman coding, Journal of Algorithms, v.6 n.2, p.163-180, June 1985 [doi>10.1016/0196-6774(85)90036-7]
• 25: KUHN, M. 1996. Implementation of JBIG (including a QM-coder). ftp://ftp.informatik. uni-erlangen, de/pub/doc/ISO/JBIG/jbigkit-0.9.tar.gz
• 26: LANGDON, G. G. 1984. An introduction to arithmetic coding. IBM J. Res. Dev. 28, 2 (Mar.), 135-149.
• 27: LANGDON, G. G. AND RISSANEN, J. 1981. Compresson of black-and-white images with arithmetic coding. IEEE Trans. Commun. COM-29, 858-867.
• 28: MANSTETTEN, D. 1992. Tight upper bounds on the redundancy of Huffman codes. IEEE Trans. Inf. Theor. 38, 1 (Jan.), 144-151.
• 29: A. Moffat, Word-based text compression, Software—Practice & Experience, v.19 n.2, p.185-198, February 1989 [doi>10.1002/spe.4380190207]
• 30: MOFFAT, A. 1990a. Implementing the PPM data compression scheme. IEEE Trans. Commun. 38, 11 (Nov.), 1917-1921.
• 31: MOFFAT, A. 1990b. Linear time adaptive arithmetic coding. IEEE Trans. Inf. Theor. 36, 2 (Mar.), 401-406.
• 32: MOFFAT, A. 1997. Critique of "Novel design of arithmetic coding for data compression". IEE Proc. Comput. Digit. Tech.
• 33: MOFFAT, A. AND TURPIN, A. 1997. On the implementaiton of minimum-redundancy prefix codes. IEEE Trans. Commun. 45, 10 (Oct.), 1200-1207.
• 34: Alistair Moffat , Neil Sharman , Ian H. Witten , Timothy C. Bell, An empirical evaluation of coding methods for multi-symbol alphabets, Information Processing and Management: an International Journal, v.30 n.6, p.791-804, 1994 [doi>10.1016/0306-4573(94)90007-8]
• 35: W. B. Pennebaker , J. L. Mitchell , G. G. Langdon, Jr. , R. B. Arps, An overview of the basic principles of the Q-Coder adaptive binary arithmetic coder, IBM Journal of Research and Development, v.32 n.6, p.717-726, November 1988
• 36: RISSANEN, J. 1976. Generalised Kraft inequality and arithmetic coding. IBM J. Res. Dev. 20, 198-203.
• 37: RISSANEN, J. AND LANGDON, G. G. 1979. Arithmetic coding. IBM J. Res. Dev. 23, 2 (Mar.), 149-162.
• 38: RISSANEN, J. AND LANGDON, G. G. 1981. Universal modeling and coding. IEEE Trans. Inf. Theor. IT-27, 1 (Jan.), 12-23.
• 39: RISSANEN, J. AND MOHIUDDIN, K. M. 1989. A multiplication-free multialphabet arithmetic code. IEEE Trans. Comm. 37, 2 (Feb.), 93-98.
• 40: RUBIN, F. 1979. Arithmetic stream coding using fixed precision registers. IEEE Trans. Inf. Theor. IT-25, 6 (Nov.), 672-675.
• 41: M. Schindler, A Fast Renormalisation for Arithmetic Coding, Proceedings of the Conference on Data Compression, p.572, March 30-April 01, 1998
• 42: SHANNON, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 79-423.
• 43: Jeffrey Scott Vitter, Design and analysis of dynamic Huffman codes, Journal of the ACM (JACM), v.34 n.4, p.825-845, Oct. 1987 [doi>10.1145/31846.42227]
• 44: WITTEN, I. g. AND BELL, T. C. 1991. The zero frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Trans. Inf. Theor. 37, 4 (July), 1085-1094.
• 45: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 46: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 47: WITTEN, I. g., NEAL, R. M., AND CLEARY, J. a. 1988. Authors' response to "Compress and Compact discussed further". Commun. ACM 31, 9 (Sept.), 1140-1145.
• 48: ZIv, J. AND LEMPEL, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theor. IT-23, 3, 337-343.

INDEX TERMS

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

Additional Classification:
  E. Data

General Terms:
Algorithms, Performance

Keywords:
approximate coding, arithmetic coding, text compression, word-based model