Lazy Lempel-Ziv factorization algorithms

DOI10.1145/2699876MaRDI QIDQ5266607zbMATH OpenOpenAlexWikidataFDO

Authors Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi

Publication date 16 June 2017

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2699876

zbMATH Keywords

Burrows-Wheeler transformdata compressionLempel-Ziv factorizationLempel-Ziv parsingLZ77string processingsuffix array

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Lempel-Ziv factorization: simple, fast, practical
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Lempel-Ziv factorization using less time \& space
• A comparison of index-based Lempel-Ziv LZ77 factorization algorithms
• Lempel-Ziv Factorization Revisited

Cites work

• A comparison of index-based Lempel-Ziv LZ77 factorization algorithms
• A faster grammar-based self-index
• A universal algorithm for sequential data compression
• An analysis of the Burrows-Wheeler transform
• An Online Algorithm for Finding the Longest Previous Factors
• Compressed representations of sequences and full-text indexes
• Computing longest previous factor in linear time and applications
• Faster approximate pattern matching in compressed repetitive texts
• Finding approximate repetitions under Hamming distance.
• Hybrid indexes for repetitive datasets
• Indexing compressed text
• Indexing highly repetitive collections
• Lempel-Ziv Factorization Revisited
• Lempel-Ziv factorization using less time \& space
• Lempel-Ziv factorization: simple, fast, practical
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Linear work suffix array construction
• Linear-time computation of local periods
• LPF computation revisited
• Medium-Space Algorithms for Inverse BWT
• On compressing and indexing repetitive sequences
• Permuted Longest-Common-Prefix Array
• Practical compressed suffix trees
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• The Smallest Grammar Problem

Cited in

(14)

• A comparison of index-based Lempel-Ziv LZ77 factorization algorithms
• Lempel-Ziv Factorization Revisited
• LZ77
• LZ77 factorisation of trees
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Engineering practical Lempel-Ziv tries
• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
• Lempel-Ziv factorization: simple, fast, practical
• LCP array construction in external memory
• On the computation of longest previous non-overlapping factors
• LZ77 via prefix-free parsing
• Sublinear time Lempel-Ziv (LZ77) factorization
• Bat-LZ out of hell
• Lempel-Ziv factorization using less time \& space

This page was built for publication: Lazy Lempel-Ziv factorization algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266607)