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
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 (5)
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)
