Approximating LZ77 via Small-Space Multiple-Pattern Matching

DOI10.1007/978-3-662-48350-3_45zbMath1466.68090arXiv1504.06647OpenAlexW1800055261MaRDI QIDQ3452816

Johannes Fischer, Travis Gagie, Tomasz Kociumaka, Paweł Gawrychowski

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items

Strictly in-place algorithms for permuting and inverting permutations ⋮ Approximating LZ77 via Small-Space Multiple-Pattern Matching ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Lempel-Ziv-like parsing in small space ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation ⋮ LZ77 computation based on the run-length encoded BWT ⋮ Dynamic index and LZ factorization in compressed space ⋮ Refining the \(r\)-index ⋮ Streaming Dictionary Matching with Mismatches ⋮ A Space-Optimal Grammar Compression. ⋮ Real-Time Streaming Multi-Pattern Search for Constant Alphabet ⋮ Small-space LCE data structure with constant-time queries ⋮ LZ-End Parsing in Linear Time ⋮ Streaming dictionary matching with mismatches

Cites Work

• Simple real-time constant-space string matching
• Time-space-optimal string matching
• On-line construction of suffix trees
• Faster compressed dictionary matching
• Algorithmics on SLP-compressed strings: A survey
• Sublinear Space Algorithms for the Longest Common Substring Problem
• Lempel Ziv Computation in Small Space (LZ-CISS)
• Dictionary Matching in a Stream
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Constructing Efficient Dictionaries in Close to Sorting Time
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• A universal algorithm for sequential data compression
• Two-way string-matching
• Uniqueness Theorems for Periodic Functions