A RUN-TIME EFFICIENT IMPLEMENTATION OF COMPRESSED PATTERN MATCHING AUTOMATA
Tetsuya Matsumoto, Kazuhito Hagio, Masayuki Takeda · International Journal of Foundations of Computer Science · 2009
We present a run-time efficient implementation of compressed pattern matching automata (CPMA) of Kida et al. (2003), where a text is given as a truncation-free collage system [Formula: see text] such that variable sequence [Formula: see text] is encoded by any prefix code. We first build CPMA directly from P and [Formula: see text] in [Formula: see text] time and space, and then convert it into the decoder-embedded CPMA (DECPMA), where |P| is the pattern length and [Formula: see text] is the number of variables defined in [Formula: see text]. The bound [Formula: see text] improves the bound [Formula: see text] achieved by a straightforward application of the method of Kida et al. We experimentally show that a combination of recursive-pairing compression and byte-oriented Huffman coding allows both a high compression ratio and a high speed CPM.