TCS-TR-A-10-40

Date: Tue Feb 23 12:28:16 2010

Title: An Efficient Matching Algorithm for Acyclic Regular Expressions with Bounded Depth

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

Contact:

First name: Hiroki
Last name: Arimura
Address: Graduate School of Information Science and Technology, Hokkaido University
Email: arim@ist.hokudai.ac.jp

Abstract. In this paper, we study the regular expression matching problem for a subclass of regular expressions of small depth. A regular expression is acyclic if it is over the basis of letters in \Sigma, concatenation '.' and union '|'. By extending the SHIFT-AND approach by Wu and Manber (JACM 39(2),1992), we present an efficient algorithm that solves the regular expression matching problem for acyclic regular expressions with length m and depth d and an input text of length n in O(nmd/w) time using O(md) preprocessing and O(md/w) space in words on unit-cost RAM model with word length w. When the depth d is constant, typical in real applications, our algorithm runs in O(nm/w) time and O(m/w) space, while the algorithm by Bille (ICALP, 2006) runs in O(nm\log w/w) time and O(m\log w/w) space. Hence, this achieves O(\log m) and O(\log w) speed-ups in small automata (m \leq w) and in large automata (m > w) cases, resp., still keeping O(m/w) space.