Arithmetic coding for data compression

ABSTRACT

The state of the art in data compression is arithmetic coding, not the better-known Huffman method. Arithmetic coding gives greater compression, is faster for adaptive models, and clearly separates the model from the channel encoding.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Abramson, N. Information Theory and Coding. McGraw-Hill, New York, 1963. This textbook contains the first reference to what was to become the method of arithmetic coding (pp. 61-62).
	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	Cleary, J.C., and Witten, I.H. A comparison of enumerative and adaptive codes. IEEE Trans. Inf. Theory IT-30,2 (Mar. 1984). 306-315. Demonstrates under quite general conditions that adaptive coding outperforms the method of calculating and transmitting an exact model of the message first.
	4	Clearv. I.G.. and Witten. I.H. Data comoression using adaptive coding and'partial string matching. IEEE T>ans. Commu~ C&-32,4 (Apr. 1984). 396-402. Presents an adaptive modeling method that reduces a large sample of mixed-case English text to around 2.2 bits/character when arithmetically coded.
	5	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]
	6	Cormack, G.V., and Horspool, R.N. Data compression using dynamic Markov modeling. Res. Rep., Computer Science Dept., Univ. of Walerloo, Ontario, Apr. 1985. Also to be published in Cornput. 1. Presents an adaptive state-modeling technique that, in conjunction with arithmetic coding, produces results competitive with those of {4}
	7	Gallager, R.G. Variations on a theme by Huffman. IEEE Trans. tnf Theory IT-24, 6 (Nov. 19781, 668-674. Presents an adaptive Huffman coding algorithm, and derives new bounds on the redundancy of Huffman codes.
	8	Gilbert Held , Thomas Marshall, Data compression: techniques and applications: hardware and software considerations (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1986
	9	J. H. Hester , D. S. Hirschberg, Self-organizing linear search, ACM Computing Surveys (CSUR), v.17 n.3, p.295-311, Sept. 1985 [doi>10.1145/5505.5507]
	10	Huffman, D.A. A method for the construction of minimumredundancy codes. Proc. Inst. Electr. Radio Eng. 40, 9 (Sept. 1952), 1098-1101. The classic paper in which Huffman introduced his famous coding method.
	11	Hunter, R., and Robinson, A.H. International digital facsimile coding standards. Proc. Inst. Electr. Electron. Eng. 68, 7 (July 1980), 854-867. Describes the use of Huffman coding to compress run lengths in black/white images.
	12	Kucera, H., and Francis, W.N. Compufational Analysis of Present-Day American English. Brown University Press, Providence, R.I.. 1967. This large corpus of English is often used for computer experiments with text, including some of the evaluation reported in the present article.
	13	Langdon, G.G. An introduction to arithmetic coding. IBMI. Res. Dev. 28, 2 (Mar. 1984), 135-149. Introduction to arithmetic coding from the point of view of hardware implementation.
	14	Langdon, G.G., and Rissanen, J. Compression of black-white images with arithmetic coding. 1EEE Trans. Commun. COM 29,6 (June 1981), 858.-867. Uses a modeling method specially tailored to black/white pictures, in conjunction with arithmetic coding, to achieve excellent compression results.
	15	Richard Clark Pasco, Source coding algorithms for fast data compression., 1976
	16	Rissanen, J.J. Generalized Kraft inequality and arithmmatic coding. IBM 1. Res. Dev. 20 (May 1976), 198-203. Another early exposition of the idea of arithmetic coding.
	17	Rissanen. J.J. Arithmetic codings as number representations. Acta Polytech. Stand. Math. 31 (Dec. 1979), 44-51. Further develops arithmetic coding as a practical technique for data representation.
	18	Rissanen, J., and Langdon, G.G. Arithmetic coding. IBM J. Res. Dev. 23, 2 (Mar. 1979). 149-162. Describes a broad class of arithmetic codes.
	19	Rissanen, J.. and Langdon, G.G. Universal modeling and coding. IEEE Trans. Znf Theory IT-27, 1 (Jan. 1981), 12-23. Shows how data cornpression can be separated into modeling for prediction and coding with respect to a model.
	20	Rubin, F. Arithmetic stream coding using fixed precision registers. IEEE Trans. If. Theory IT-25, 6 (Nov. 1979), 672-675. One of the first papers to present all the essential elements of practical arithmetic coding, including fixed-point computation and incremental operation.
	21	Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
	22	Welch, T.A. A technique for high-performance data compression. Computer 17, 6 (June 1984), 8-19. A very fast coding technique based on the method of {23}, but whose compression performance is poor by the standards of {4} and {6} An improved implementation of this method is widely used in UNIX systems under the name compress.
	23	Ziv, J., and Lempel, A. Compression of individual sequences via variable-rate coding. IEEE Trans. InJ Theory IT-24, 5 (Sept. 1978), 530-536. Describes a method of text compression that works by replacing a substring with a pointer to an earlier occurrence of the same substring. Although it performs quite well, it does not provide a clear separation between modeling and coding.