Data compression with finite windows

ABSTRACT

Several methods are presented for adaptive, invertible data compression in the style of Lempel's and Ziv's first textual substitution proposal. For the first two methods, the article describes modifications of McCreight's suffix tree data structure that support cyclic maintenance of a window on the most recent source characters. A percolating update is used to keep node positions within the window, and the updating process is shown to have constant amortized cost. Other methods explore the tradeoffs between compression time, expansion time, data structure size, and amount of compression achieved. The article includes a graph-theoretic analysis of the compression penalty incurred by our codeword selection policy in comparison with an optimal policy, and it includes empirical studies of the performance of various adaptive compressors from the literature.

REFERENCES

• 1: Abramson, N. Information Theory and Coding. McGraw-Hill, 1963, 61.
• 2: Basharin, G.P. On a statistical estimate for the entropy of a sequence of independent random variables. Theory Prob. Appl. 4, (1959), 333-336.
• 3: Bell, T.C. Better OPM/L text compression. IEEE Trans. Commun. C0M-34, 12 (1986), 1176-1182.
• 4: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 5: 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]
• 6: Cleary, J.G., and Witten, I.H. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4 (1984), 396-402.
• 7: 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
• 8: Dantzig, G.B., Blattner, W.O., and Rao, M.R. Finding a Cycle in a Graph with Minimum Cost to Time Ratio with Application to a Ship Routing Problem. Theory of Graphs, P. Rosenstiehl, ed. Gordon and Breach, 1966.
• 9: Elias, P. Universal codeword sets and representations of the integers. /GEE Trans. Info. Theory IT-21, 2 (1975), 194-203.
• 10: S. Even , M. Rodeh, Economical encoding of commas between strings, Communications of the ACM, v.21 n.4, p.315-317, April 1978 [doi>10.1145/359460.359480]
• 11: Gallager, R.G. Variations on a theme by Huffman. IEEE Trans. lnfo. Theory IT-24, 6 (1978), 668-674.
• 12: Gasbarro, }. An Architecture for High-Performance VLSI Testers. Ph.D. dissertation, Department of Electrical Engineering, Stanford University, 1988.
• 13: Golomb, S.W. Run-Length Encodings. IEEE Trans. Info. Theory IT-12 (1966), 399-401.
• 14: Guazzo, M. A General Minimum Redundancy Source-coding Algorithm. IEEE Trans. Info. Theory IT-26, I (1980), 15-25.
• 15: Gu Guoan , John Hobby, Using string matching to compress Chinese characters, Stanford University, Stanford, CA, 1982
• 16: Horspool, R.N., and Cormack, G.V. Dynamic Markov Modelling-- A Prediction Technique. In Proceedings of the 19th Annual Hawaii International Conference on System Sciences (1986), 700-707.
• 17: Huffman, D.A. A method for the construction of minimum-redundancy codes. In Proceedings of the I.R.E. 40 (1952), 1098-1101.
• 18: Hunter, R., and Robinson, A.H. International digital facsimile coding standards. In Proceedings of the IEEE 68, 7 (1980), 854-867.
• 19: Matti Jakobsson, Compression of character strings by an adaptive dictionary, BIT, v.25 n.4, p.593-603, 1985 [doi>10.1007/BF01936138]
• 20: Jones, C.B. An efficient coding system for long source sequences. IEEE Trans. Info. Theory IT-27, 3 (1981), 280-291.
• 21: Kempf, M., Bayer, R., and Gfintzer, U. Time Optimal Left to Right Construction of Position Trees. Acta Informatica, 24 (1987), 461-474.
• 22: 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
• 23: 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]
• 24: Langdon, G.G., Jr. A note on the Ziv-Lempel model for compressing individual sequences IEEE Trans. Info. Theory IT-29, 2 (1983}, 284-287.
• 25: Langdon, G.G., Jr., and Rissanen, J. Compression of Black-White Images with Arithmetic Coding. IEEE Trans. Commun. COM-29, 6 (1981), 858-867.
• 26: Langdon, G.G., Jr., and Rissanen, J. A Double Adaptive File Compression Algorithm. IEEE Trans. Commun. COM-31, 11 (1983), 1253-1255.
• 27: Lawler, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
• 28: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 29: Miller, V.S., and Wegman, M.N. Variations on a theme by Ziv and Lempel. IBM Res. Rep. RC 10630 (#47798), 1984. Combinatorial Algorithms on Words, NATO ASI Series F, 12 (1985), 131-140.
• 30: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 31: Richard Clark Pasco, Source coding algorithms for fast data compression., 1976
• 32: Rissanen, J., and Langdon, G.G.. Jr. Arithmetic Coding. IBM Journal of Research and Development 23, 2 (1979), 149-162.
• 33: Rissanen, J., and Langdon, G.G., Jr. Universal Modeling and Coding. IEEE Trans. Info. Theory IT-27, 1 (1981}, 12-23.
• 34: Michael Rodeh , Vaughan R. Pratt , Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM (JACM), v.28 n.1, p.16-24, Jan. 1981 [doi>10.1145/322234.322237]
• 35: Shannon, C.E. A mathematical theory of communication. The Bell System Technical Journal 27, 3, 379-423 and 27, 4 (1948), 623-656.
• 36: James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982 [doi>10.1145/322344.322346]
• 37: Vitter, J.S. Design and analysis of dynamic Huffman coding. Brown University Technical Report No. CS-85-13, 1985.
• 38: Wether, P. Linear Pattern Matching Algorithms. Fourteenth Annual Symposium on Switching and Automata Theory, 1-11, 1973.
• 39: Welch, T.A. A technique for high performance data compression. IEEE Comp. 17, 6 (1984}, 8-19.
• 40: 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]
• 41: Ziv, J. Coding theorems for individual sequences IEEE Trans. Info. Theory IT-24,4 (1978), 405-412.
• 42: Ziv, J., and Lempel, A. A universal algorithm for sequential data compression. IEEE Trans. Info. Theory IT-23, 3 (1977), 337-343.
• 43: Ziv, J., and Lempel, A. Compression of individual sequences via variable-rate coding. IEEE Trans. Info. Theory IT-24, 5 (1978}, 530-536.

INDEX TERMS

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

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Pattern matching

General Terms:
Algorithms, Design, Experimentation, Theory