The macro model for data compression (Extended Abstract)

ABSTRACT

A general model for data compression is presented which includes most data compression systems in the literature as special cases. All macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy. Different varieties of macro schemes may be defined by varying the interpretation of pointers, for instance, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary. Other varieties of macros schemes may be defined by restricting the type of overlapping or recursion that may be used. Trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed as well as how the work of other authors (such as Lempel-Ziv) relates to this model.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 3: M. R. Garey, D. S. Johnson, and L. Stockmeyer {1976}. "Some Simplified NP-Complete Problems". Theoretical Computer Science 1, 237-267.
• 4: W. D. Hagamen, D. J. Linden, H. S. Long, and J. C. Weber {1972}. "Encoding Verbal Information as Unique Numbers", IBM Systems Journal 11.
• 5: Bruce Hahn, A new technique for compression and storage of data, Communications of the ACM, v.17 n.8, p.434-436, Aug. 1974 [doi>10.1145/361082.361086]
• 6: D. A. Huffman {1952}. "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE 40, 1098-1101.
• 7: R. M. Karp {1972}. "Reducibility Among Combinatorial Problems", in Miller and Thatcher (eds.), Complexity of Computations, Plenum Press, New York, N.Y.
• 8: A. Lempel and J. Ziv {1976}. "On the Complexity of Finite Sequences", IEEE Transactions on Information Theory, 22:1, 75-81.
• 9: M. E. Lesk {1970}. "Compressed Text Storage", Computer Science Technical Report #3- Bell Laboratories, Murray Hill.
• 10: D. Maier {1976}. "The Complexity of Some Problems on Subsequences and Supersequences", Technical Report 219, Dept. of Electrical Engineering and Computer Science, Princeton University, Princeton, N.J.
• 11: D. Maier {1977}. "The Complexity of Some Problems on Subsequences and Supersequences", Conference on Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, Canada.
• 12: D. Maier and J. A. Storer {1977}. "A Note Concerning the Superstring Problem". Technical Report 233, Dept. of Electrical Engineering and Computer Science, Princeton University, Princeton, N.J.
• 13: J. P. McCarthy {1973}. "Automatic File Compression", International Computing Symposium (North Holland).
• 14: B. A. Marron , P. A. D. de Maine, Automatic data compression, Communications of the ACM, v.10 n.11, p.711-715, Nov. 1967 [doi>10.1145/363790.363813]
• 15: A. Mayne and E. B. James {1975}. "Information Compression by Factorising Common Strings", The Computer Journal 18:2, 157-160.
• 16: J. A. Storer {1977}. "NP-Completeness Results Concerning Data Compression", Technical Report 234, Dept. of Electrical Engineering and Computer Science, Princeton University, Princeton, N.J.
• 17: J. A. Storer {1977b}. "PLCC- A Compiler-Compiler for PL1 and PLC Users", Technical Report 236, Dept. of Electrical Engineering and Computer Science, Princeton University, Princeton, N.J.
• 18: J. A. Storer and T. G. Szymanski {1977}. "The Macro Model for Data Compression" Technical Report 235, Dept. of Electrical Engineering and Computer Science, Princeton University, Princeton, N.J.
• 19: Bruce Hahn, A new technique for compression and storage of data, Communications of the ACM, v.17 n.8, p.434-436, Aug. 1974 [doi>10.1145/361082.361086]
• 20: M. Rodeh, V. R. Pratt, and S. Even {1976}. "A Linear Time Algorithm for Finding Repetitions and its Application to Data Compression&rdguo;, Technical Report #72, Dept. of Computer Science, Technicon, Israel.
• 21: S.S. Ruth and P. J. Kreutzer {1972}. "Data Compression for Large Business Files", Datamation 18:9, 62-66.
• 22: M. Visvalingam {1976}. "Indexing with Coded Deltas - A Data Compaction Technique", Software - Practice and Experience 6, 397-403.
• 23: Robert A. Wagner, Common phrases and minimum-space text storage, Communications of the ACM, v.16 n.3, p.148-152, March 1973 [doi>10.1145/361972.361982]
• 24: J. Ziv and A. Lempel {1977}. "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory 23:3, 337-343.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Theory