de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Faster Fully Compressed Pattern Matching by Recompression

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons79297

Jeż,  Artur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Jeż, A. (2015). Faster Fully Compressed Pattern Matching by Recompression. ACM Transactions on Algorithms, 11(3): 20, pp. 1-43. doi:10.1145/2631920.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-CD10-E
Abstract
In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)-that is, context-free grammars generating exactly one string; the term fully means that both the pattern and the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. This technique yields an O((n + m) log M) algorithm for compressed pattern matching, assuming that M fits in O(1) machine words, where n (m) is the size of the compressed representation of the text (pattern, respectively), and M is the size of the decompressed pattern. If only m + n fits in O(1) machine words, the running time increases to O((n + m) log M log(n + m)). The previous best algorithm due to Lifshits has O(n(2)m) running time.