Computer Science – Data Structures and Algorithms
Scientific paper
2011-11-14
Computer Science
Data Structures and Algorithms
9 pages + 14 appendix, submitted to a conference. The new version presents a slightly better running time and much simplified
Scientific paper
In this paper, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs), i.e. a context-free grammars generating exactly one string; the term fully means that both the pattern and the text are given in the compressed form. A novel algorithmic technique of dealing with SLPs is introduced and applied: the SLPs are recompressed, 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 log(n+m)) algorithm for compressed pattern matching, where n (m) is the size of the compressed representation of the text (pattern, respectively), while M is the size of the decompressed pattern. Since M <= 2^m, this greatly improves the previously best O(m^2n) algorithm. Since LZ compression standard reduces to SLP with log(N / n) overhead and in O(n log(N/n)) time, the presented algorithm can be straightforwardly applied also to the fully LZ-compressed pattern matching problem, yielding an O(s log s log M) running time algorithm, where s = n log(N/n) + m log(M/m). To author's best knowledge there are no fully compressed pattern matching algorithms for LZ other than adaptations of FCPM for SLP.
No associations
LandOfFree
Faster fully compressed pattern matching by recompression does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Faster fully compressed pattern matching by recompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster fully compressed pattern matching by recompression will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-218513