Lightweight Lempel-Ziv Parsing

Abstract

We introduce a new approach to LZ77 factorization that uses O(n/d) words of working space and O(dn) time for any d >= 1 (for polylogarithmic alphabet sizes). We also describe carefully engineered implementations of alternative approaches to lightweight LZ77 factorization. Extensive experiments show that the new algorithm is superior in most cases, particularly at the lowest memory levels and for highly repetitive data. As a part of the algorithm, we describe new methods for computing matching statistics which may be of independent interest.

12 pages

References in corpus (2)

• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• A Faster Grammar-Based Self-Index

Cited by in corpus (7)

• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• LZ-End Parsing in Compressed Space
• Lempel-Ziv Parsing in External Memory
• Indexing Highly Repetitive String Collections
• The Cyborg Astrobiologist: Matching of Prior Textures by Image Compression for Geological Mapping and Novelty Detection
• Faster Lightweight Lempel-Ziv Parsing
• Approximating LZ77 via Small-Space Multiple-Pattern Matching