Approximate pattern matching in LZ77-compressed texts

DOI10.1016/J.JDA.2014.10.003MaRDI QIDQ2343301zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Simon J. Puglisi, Paweł Gawrychowski

Publication date 4 May 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2014.10.003

zbMATH Keywords

compressed approximate pattern matchingLZ77

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Approximate string matching on Ziv--Lempel compressed text
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• scientific article; zbMATH DE number 1615281
• Faster approximate pattern matching in compressed repetitive texts

Cites work

• A faster grammar-based self-index
• A universal algorithm for sequential data compression
• Algorithmics on SLP-compressed strings: a survey
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximate string matching on Ziv--Lempel compressed text
• Approximate String Matching: A Simpler Faster Algorithm
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Compression of individual sequences via variable-rate coding
• Data structure lower bounds on random access to grammar-compressed strings
• Fast parallel and serial approximate string matching
• Faster approximate pattern matching in compressed repetitive texts
• Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Random access to grammar-compressed strings
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
• The Smallest Grammar Problem

Cited in

(9)

• Block trees
• Dynamic index and LZ factorization in compressed space
• Finger search in grammar-compressed strings
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Faster approximate pattern matching in compressed repetitive texts
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Random access in persistent strings and segment selection
• Sublinear time Lempel-Ziv (LZ77) factorization

This page was built for publication: Approximate pattern matching in LZ77-compressed texts

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