Faster approximate pattern matching in compressed repetitive texts

DOI10.1007/978-3-642-25591-5_67MaRDI QIDQ3104667zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Paweł Gawrychowski, Simon J. Puglisi

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: Motivated by the imminent growth of massive, highly redundant genomic databases, we study the problem of compressing a string database while simultaneously supporting fast random access, substring extraction and pattern matching to the underlying string(s). Bille et al. (2011) recently showed how, given a straight-line program with $r$ rules for a string $s$ of length $n$, we can build an $Ohr$-word data structure that allows us to extract any substring of length $m$ in $Ohlogn+m$ time. They also showed how, given a pattern $p$ of length $m$ and an edit distance (k leq m), their data structure supports finding all occ approximate matches to $p$ in $s$ in $Ohr(min(mk,k^4+m)+logn)+occ$ time. Rytter (2003) and Charikar et al. (2005) showed that $r$ is always at least the number $z$ of phrases in the LZ77 parse of $s$, and gave algorithms for building straight-line programs with $Ohzlogn$ rules. In this paper we give a simple $Ohzlogn$-word data structure that takes the same time for substring extraction but only $Ohzmin(mk,k^4+m)+occ$ time for approximate pattern matching.

Recommendations

• Approximate string matching on Ziv--Lempel compressed text
• Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching
• Approximate pattern matching in LZ77-compressed texts
• scientific article; zbMATH DE number 1615281

Cited in

(11)

• Improved approximate pattern matching on hypertext
• Block trees
• Approximate pattern matching on elastic-degenerate text
• Approximate pattern matching in LZ77-compressed texts
• Block graphs in practice
• Compressed matching for feature vectors
• LZ-End Parsing in Linear Time
• Pattern matching on elastic-degenerate text with errors
• Lazy Lempel-Ziv factorization algorithms
• Improving Time and Space Complexity for Compressed Pattern Matching
• Mining approximate patterns with frequent locally optimal occurrences

This page was built for publication: Faster approximate pattern matching in compressed repetitive texts

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