Faster Fully Compressed Pattern Matching by Recompression

DOI10.1007/978-3-642-31594-7_45zbMath1272.68481arXiv1111.3244OpenAlexW1730038947MaRDI QIDQ2843278

Artur Jeż

Publication date: 12 August 2013

Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

straight-line programspattern matchingLempel-Ziv compressioncompressed pattern matchingalgorithms for compressed datastraight-line programms

Mathematics Subject Classification ID

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

Related Items (14)

Equality Testing of Compressed Strings ⋮ Approximation of smallest linear tree grammar ⋮ String Indexing with Compressed Patterns ⋮ A \textit{really} simple approximation of smallest grammar ⋮ Unnamed Item ⋮ Cadences in grammar-compressed strings ⋮ Approximation of grammar-based compression via recompression ⋮ Tree compression using string grammars ⋮ The complexity of compressed membership problems for finite automata ⋮ Grammar-based compression of unranked trees ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ Internal dictionary matching ⋮ A Space-Optimal Grammar Compression. ⋮ One-variable word equations in linear time

This page was built for publication: Faster Fully Compressed Pattern Matching by Recompression