Application of Lempel–Ziv factorization to the approximation of grammar-based compression

A. Apostolico, S. Leonardi, Some theory and practice of greedy off-line textual substitution, DCC 1998, pp. 119–128.

P. Berman, M. Karpinski, L.L. Larmore, W. Plandowski, W.W. Rytter, On the complexity of pattern matching for highly compressed two-dimensional texts, in: A. Apostolico, J. Hein (Eds.), Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 1264, Springer, Berlin, 1997, pp. 40–51. Full version to appear in JCSS 2002.

M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Rasala, A. Sahai, A. Shelat, Approximating the smallest grammar: Kolmogorov complexity in natural models, STOC 2002.

Crochemore, 1994

M. Farach, Optimal suffix tree construction with large alphabets, FOCS 1997.

M. Farach, M. Thorup, String matching in Lempel–Ziv compressed strings, Proceedings of the 27th Annual Symposium on the Theory of Computing, 1995, pp. 703–712.

L. Ga̧sieniec, M. Karpinski, W. Plandowski, W. Rytter, Efficient algorithms for Lempel–Ziv encoding, Proceedings of the 5th Scandinavian Workshop on Algorithm Theory, Springer, Berlin, 1996.

M. Hirao, A. Shinohara, M. Takeda, S. Arikawa, Faster fully compressed pattern matching algorithm for balanced straight-line programs, Proceedings of the 7th International Symposium on String Processing and Information Retrieval (SPIRE2000), IEEE Computer Society, Silver Spring, MD, September 2000, pp. 132–138.

Karpinski, 1997, Pattern-matching for strings with short description, Nordic J. Comput., 4, 172

Kieffer, 2000, Grammar-based codes, IEEE Trans. Inform. Theory, 46, 737, 10.1109/18.841160

D. Knuth, The Art of Computing, Vol. III, 2nd Ed., Addison-Wesley, Reading, MA, 1998, p. 474.

J.K. Lanctot, Ming Li, En-hui Yang, Estimating DNA Sequence Entropy, SODA 2000.

E. Lehman, A. Shelat, Approximation algorithms for grammar-based compression, SODA 2002.

Lempel, 1977, A Universal algorithm for sequential data compression, IEEE Trans. Inform. Theory, IT-23, 337

Miyazaki, 2000, An improved pattern-matching algorithm for strings in terms of straight-line programs, J. Discrete Algorithms, 1, 187

C. Nevill-Manning, Inferring sequential structure, Ph.D. Thesis, University of Waikato, 1996.

Rytter, 2000, Compressed and fully compressed pattern-matching in one and two-dimensions, Proc. IEEE, 88, 1769, 10.1109/5.892712

W. Rytter, Application of Lempel–Ziv factorization to the approximation of grammar-based compression, in: Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 2373, Springer, Berlin, June 2002, pp. 20–31.