Optimal pattern matching in LZW compressed strings

DOI10.1145/2483699.2483705MaRDI QIDQ2933655zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

compressionLempel-Ziv-Welchpattern matching

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Recommendations

• Optimal pattern matching in LZW compressed strings
• Tying up the loose ends in fully LZW-compressed pattern matching
• Simple and efficient LZW-compressed multiple pattern matching
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Simple and efficient LZW-compressed multiple pattern matching

Cited in

(14)

• Streaming pattern matching with \(d\) wildcards
• Simple and efficient LZW-compressed multiple pattern matching
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Simple and efficient LZW-compressed multiple pattern matching
• Tying up the loose ends in fully LZW-compressed pattern matching
• scientific article; zbMATH DE number 2185628 (Why is no real title available?)
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• scientific article; zbMATH DE number 1839439 (Why is no real title available?)
• Streaming periodicity with mismatches
• A space-optimal grammar compression
• Optimal pattern matching in LZW compressed strings
• Improving Time and Space Complexity for Compressed Pattern Matching
• Pattern matching on run-length grammar-compressed strings in linear time

This page was built for publication: Optimal pattern matching in LZW compressed strings

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