Regular Expression Matching Algorithms using Dual Position Automata

摘要

This paper introduces an automaton model called a dual position automaton (a dual PA), and then gives a bit-parallel algorithm for generating a dual PA from a regular expression (RE). For any RE r over an alphabet E, our translation algorithm generates a dual PA consisting of m(m + 1) bits in O(m[m/w]) time and space, where w is the length of a computer word, m = ∑_(a∈∑) m_a and m_a is the number of occurrences of an alphabet symbol a in r. Furthermore, we give a method to construct a compact DFA representation from a dual PA. This DFA representation requires only (m + 1) ∑_(a∈∑)2~(m_a) bits. Finally, we show RE matching algorithms using such a DFA representation.