AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

MPI Audience

English

30 Minutes

Saarbrücken

In this talk I will consider the fully compressed pattern matching problem. 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. 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, 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 is at most 2^m, this substantially improves the previously best O(m^2 n) algorithm.

The technique seems to be quite general and can be applied to several different problems related to SLP-compressed strings.

Artur Jeż

--email hidden

passcode not visible

logged in users only

Compressed pattern matching, SLPs, Algorithms for compressed data