A comparison of index-based lempel-Ziv LZ77 factorization algorithms
- 1 November 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 45 (1), 1-17
- https://doi.org/10.1145/2379776.2379781
Abstract
Since 1977, when Lempel and Ziv described a kind of string factorization useful for text compression, there has been a succession of algorithms proposed for computing “LZ factorization”. In particular, there have been several recent algorithms proposed that extend the usefulness of LZ factorization, for example, to the calculation of maximal repetitions. In this article, we provide an overview of these new algorithms and compare their efficiency in terms of their usage of time and space.Keywords
This publication has 32 references indexed in Scilit:
- Maximal repetitions in stringsJournal of Computer and System Sciences, 2008
- Computing Longest Previous Factor in linear time and applicationsInformation Processing Letters, 2008
- A taxonomy of suffix array construction algorithmsACM Computing Surveys, 2007
- On-line construction of suffix treesAlgorithmica, 1995
- Approximate string-matching with q-grams and maximal matchesTheoretical Computer Science, 1992
- Better OPM/L Text CompressionIEEE Transactions on Communications, 1986
- Data compression via textual substitutionJournal of the ACM, 1982
- Compression of individual sequences via variable-rate codingIEEE Transactions on Information Theory, 1978
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977
- On the Complexity of Finite SequencesIEEE Transactions on Information Theory, 1976