Ian H. Witten
Skip Abstract Section
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.
- 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).Google Scholar
- 2 Bentley. J.L., Sleator, D.D., Tarjan, R.E., and Wei, V.K. A locally adaptive data compression scheme. Commun. ACM 29, 4 (Apr. 1986), 320-330. Shows how recency effects can be incorporated explicitly into a text compression system. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 5 Cormack, G.V., and Horspool, R.N. Algorithms for adaptive Huffman codes. Ir$ Process. Lett. 18, 3 (Mar. 19841, 159-166. Describes how adaptive Huffman coding can be implemented efficiently. Google ScholarDigital Library
- 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}Google Scholar
- 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.Google Scholar
- 8 Held, G. Data Compression: Techniques and Applications. Wiley, New York, 1984. Explains a number of ad hoc techniques for compressing text. Google ScholarDigital Library
- 9 Hester, J.H., and Hirschberg, D.S. Self-organizing linear search. ACM Comput. SKI-V. 17, 3 (Sept. 1985), 295-311. A general analysis of the technique used in the present article to expedite access to an array of dynamically changing frequency counts. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 15 Pasco, R. Source coding algorithms for fast data compression. Ph.D. thesis, Dept. of Electrical Engineering, Stanford Univ., Stanford, Calif., 1976. An early exposition of the idea of arithmetic coding, but lacking the idea of incremental operation. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 21 Shannon, C.E. and Weaver, W. The Mathematical Theory of Communication. University of Illinois Press, Urbana, Ill., 1949. A classic book that develops communication theory from the ground up. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google ScholarCross Ref
Index Terms
- Arithmetic coding for data compression
Recommendations
Block arithmetic coding for source compression
We introduce “Block Arithmetic Coding” (BAC), a technique for entropy coding that combines many of the advantages of ordinary stream arithmetic coding with the simplicity of block codes. The code is variable length in to fixed out (V to F), ...
Connectivity compression for non-triangular meshes by context-based arithmetic coding
GRAPHITE '06: Proceedings of the 4th international conference on Computer graphics and interactive techniques in Australasia and Southeast AsiaIn this article, we present an efficient algorithm for encoding the connectivity information of general polygon meshes. The algorithm is a single-resolution lossless compression method for meshes, mainly for non-triangular meshes. In comparison with the ...
Reversible arithmetic coding for quantum data compression
We study the problem of compressing a block of symbols (a block quantum state) emitted by a memoryless quantum Bernoulli source. We present a simple-to-implement quantum algorithm for projecting, with high probability, the block quantum state onto the ...
Comments