Beating O(nm) in approximate LZW-compressed pattern matching
From MaRDI portal
Publication:2872073
DOI10.1007/978-3-642-45030-3_8zbMATH Open1329.68313arXiv1308.6509OpenAlexW2592880556MaRDI QIDQ2872073FDOQ2872073
Authors: Paweł Gawrychowski, Damian Straszak 
Publication date: 14 January 2014
Published in: Algorithms and Computation (Search for Journal in Brave)
Abstract: Given an LZW/LZ78 compressed text, we want to find an approximate occurrence of a given pattern of length m. The goal is to achieve time complexity depending on the size n of the compressed representation of the text instead of its length. We consider two specific definitions of approximate matching, namely the Hamming distance and the edit distance, and show how to achieve O(nm^0.5k^2) and O(nm^0.5k^3) running time, respectively, where k is the bound on the distance. Both algorithms use just linear space. Even for very small values of k, the best previously known solutions required O(nm) time. Our main contribution is applying a periodicity-based argument in a way that is computationally effective even if we need to operate on a compressed representation of a string, while the previous solutions were either based on a dynamic programming, or a black-box application of tools developed for uncompressed strings.
Full work available at URL: https://arxiv.org/abs/1308.6509
Recommendations
Cited In (7)
- Approximate pattern matching in LZ77-compressed texts
- Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts
- Faster approximate pattern matching in compressed repetitive texts
- Approximate string matching on Ziv--Lempel compressed text
- Circular pattern matching with \(k\) mismatches
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- Title not available (Why is that?)
This page was built for publication: Beating \(O(nm)\) in approximate LZW-compressed pattern matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872073)
