A comparison of index-based lempel-Ziv LZ77 factorization algorithms Journal Articles

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.

authors

• Al-Hafeedh, Anisa
• Crochemore, Maxime
• Ilie, Lucian
• Kopylova, Evguenia
• Smyth, William
• Tischler, German
• Yusufu, Munina

status

• published 

publication date

• November 2012

has subject area

• 08 Information and Computing Sciences (FoR)
• Information Systems (Science Metrix)

published in

• ACM Computing Surveys  Journal

keywords

• Algorithms
• COMPRESSION
• COMPUTATION
• Computer Science
• Computer Science, Theory & Methods
• Design
• IMPROVEMENTS
• INFORMATION
• LINEAR-TIME
• Lempel-Ziv factorization
• Performance
• REPEATS
• RUNS
• SUFFIX TREE CONSTRUCTION
• Science & Technology
• String
• Technology
• algorithm
• longest common prefix
• periodicity
• suffix array
• suffix tree

Digital Object Identifier (DOI)

• 10.1145/2379776.2379781

start page

• 1

end page

• 17

volume

• 45

issue

• 1