Context-Sensitive Grammar Transform: Compression and Pattern Matching

Shirou MARUYAMA  Youhei TANAKA  Hiroshi SAKAMOTO  Masayuki TAKEDA 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E93-D  No.2  pp.219-226
Publication Date: 2010/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
compressed pattern matching,  grammar-based compression,  KMP automaton, 

Full Text: PDF

Summary: 
A framework of context-sensitive grammar transform for speeding-up compressed pattern matching (CPM) is proposed. A greedy compression algorithm with the transform model is presented as well as a Knuth-Morris-Pratt (KMP)-type compressed pattern matching algorithm. The compression ratio is a match for gzip and Re-Pair, and the search speed of our CPM algorithm is almost twice faster than the KMP-type CPM algorithm on Byte-Pair-Encoding by Shibata et al., and in the case of short patterns, faster than the Boyer-Moore-Horspool algorithm with the stopper encoding by Rautio et al., which is regarded as one of the best combinations that allows a practically fast search.