Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic

DOI10.1007/978-3-642-23719-5_36MaRDI QIDQ3092248zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.4203

zbMATH Keywords

Lempel-Ziv compressionpattern matching

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)

Abstract: Countless variants of the Lempel-Ziv compression are widely used in many real-life applications. This paper is concerned with a natural modification of the classical pattern matching problem inspired by the popularity of such compression methods: given an uncompressed pattern s[1..m] and a Lempel-Ziv representation of a string t[1..N], does s occur in t? Farach and Thorup gave a randomized O(nlog^2(N/n)+m) time solution for this problem, where n is the size of the compressed representation of t. We improve their result by developing a faster and fully deterministic O(nlog(N/n)+m) time algorithm with the same space complexity. Note that for highly compressible texts, log(N/n) might be of order n, so for such inputs the improvement is very significant. A (tiny) fragment of our method can be used to give an asymptotically optimal solution for the substring hashing problem considered by Farach and Muthukrishnan.

Recommendations

• scientific article; zbMATH DE number 2185629
• Optimal pattern matching in LZW compressed strings
• Optimal pattern matching in LZW compressed strings
• scientific article; zbMATH DE number 1263249
• String matching in Lempel-Ziv compressed strings
• Practical and flexible pattern matching over Ziv-Lempel compressed text.
• Approximate string matching on Ziv--Lempel compressed text
• scientific article; zbMATH DE number 1615281
• Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
• Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts

Cited in

(20)

• String matching in Lempel-Ziv compressed strings
• Comparison of LZ77-type parsings
• The complexity of compressed membership problems for finite automata
• Approximate pattern matching in LZ77-compressed texts
• Simple and efficient LZW-compressed multiple pattern matching
• Substring compression problems
• Optimal pattern matching in LZW compressed strings
• Longest -gapped repeat and palindrome
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• scientific article; zbMATH DE number 1263249 (Why is no real title available?)
• Approximation of grammar-based compression via recompression
• Efficient algorithms for Lempel-Ziv encoding
• Computing the Antiperiod(s) of a String
• Optimal pattern matching in LZW compressed strings
• Space-efficient conversions from SLPs
• Internal pattern matching queries in a text and applications
• A textbook solution for dynamic strings
• A textbook solution for dynamic strings
• Pattern matching on run-length grammar-compressed strings in linear time
• A \textit{really} simple approximation of smallest grammar

This page was built for publication: Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic

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