Shunsuke Inenaga, Ayumi Shinohara and Masayuki Takeda

**A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems**

Abstract: |

We study the fully compressed pattern matching problem (FCPM
problem):
Given and T which are descriptions of
text PT and pattern P respectively, find the occurrences of P in T
without decompressing or T.
This problem is rather challenging since patterns are also given in a
compressed form.
In this paper we present an FCPM algorithm for Psimple collage systems.
Collage systems are a general framework that can represent various kinds of
dictionary-based compressions, and simple collage systems are a subclass
that includes LZW and LZ78 compressions.
Collage systems are of the form 〈 ,
where D, S 〉 is a dictionary and D is a sequence of
variables
from S.
Our FCPM algorithm performs in DO(|| time,
where D||^{2} + mn log
|S|)n = |
and T| = || D || + |S|m = |.
This is faster than the previous best result of
P|O(m time.
^{2}n^{2}) |

Download paper: | ||

PostScript |