TCS-TR-A-10-47

Date: Fri Nov 12 20:26:06 2010

Title: Fast Bit-Parallel Matching for Network and Regular Expressions

Authors: Yusaku Kaneta, Shin-ichi Minato, and Hiroki Arimuta

Contact:

First name: Hiroki
Last name: Arimura
Address: Graduate School of Information Science and Technology, Hokkaido University, N14 W9, Sapporo 060-0814, Japan
Email: arim@ist.hokudai.ac.jp

Abstract. In this paper, we extend the SHIFT-AND approach by Baeza-Yates and Gonnet (CACM 35(10), 1992) to the matching problem for network expressions, which are regular expressions without Kleene-closure and useful in applications such as bioinformatics and event stream processing. Following the study of Navarro (RECOMB, 2001) on the extended string matching, we introduce new operations called Scatter, Gather, and Propagate to efficiently compute epsilon-moves of the Thompson NFA using the Extended SHIFT-AND approach with integer addition. By using these operations and a property called the bi-monotonicity of the Thompson NFA, we present an efficient algorithm for the network expression matching that runs in O(ndm/w) time using O(dm) preprocessing and O(dm/w) space, where m and d are the length and the depth of a given network expression, n is the length of an input text, and w is the word length of the underlying computer. Furthermore, we show a modified matching algorithm for the class of regular expressions that runs in O(ndm log(m)/w) time.