Parallel algorithms for data compression

ABSTRACT

Parallel algorithms for data compression by textual substitution that are suitable for VLSI implementation are studied. Both “static” and “dynamic” dictionary schemes are considered.

REFERENCES

• 1: BILARDI, G., PRACCHI, M., AND PREPARATA, F. P.A critique and appraisal of VLSI models of computation. In Conference on VLSI Systems and Computations. Carnegie-Mellon Univ., Pittsburgh, Pa., 1981, pp. 81-88.
• 2: KUCERA, H., AND FRANCIS, W. N.Computational Analysis of Present-Day American English. Brown University Press, Providence, R.I., 1967.
• 3: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 4: M. S. Paterson , W. L. Ruzzo , L. Snyder, Bounds on minimax edge length for complete binary trees, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.293-299, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802481]
• 5: 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]
• 6: SEERY, J. B., AND ZIV, J.A universal data compression algorithm: Description and preliminary results. Tech. Memorandum 77-1212-6. Bell Laboratories, Murray Hill, N.J., 1977.
• 7: SEERY, J. B., AND ZIV, J.Further results on universal data compression. Tech. Memorandum 78- 1212-8. Bell Laboratories, Murray Hill, N.J., 1978.
• 8: SHANNON, C. E.Prediction of entropy of printed English text. In Key Papers in the Development oflnformation Theory, D. Slepian, Ed. IEEE, New York, 1973, pp. 42--46.
• 9: STORER, J. A. NP-completeness results concerning data compression. Tech. Rep. 234. Dept. Electrical Engineering and Computer Sci., Princeton Univ., Princeton, N.J., 1977.
• 10: STORER, J. A.Combining pipes and trees in VLSI. Tech. Rep. CS-82-107. Dept. Computer Sci., Brandeis Univ., Waltham, Mass., 1982.
• 11: 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]
• 12: 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]
• 13: ZIv, J., AND LEMPEL, A.A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23, 3 (1977), 337-343.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

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

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification