Efficient submatch addressing for regular expressions
Ville Laurikari · 2001
String pattern matching in its different forms is an important topic in theoretical computer science.This thesis concentrates on the problem of regular expression matching with submatch addressing,where the position and extent of the substrings matched by given subexpressions must be provided. The algorithms in widespread use at the time either take exponential worst-case time to find a match,can handle only a subset of all regular expressions, or use space proportional to the length of theinput string where constant space would suffice. In this thesis I propose a new method for solving thesubmatch addressing problem using nondeterministic finite automata with transitions augmented bycopy-on-write update operations. The resulting algorithm makes a single pass over the input string, always using time linearly pro-portional to the input. Space consumption depends only on the used regular expression, and not onthe input string. To the author’s knowledge, this is a new result. A prototype of a POSIX.2 com-patible regular expression matcher using the algorithm was done. Benchmarking results indicate thatthe prototype compares favorably against some popular implementations. Furthermore, absence ofexponential or polynomial time worst cases makes it possible to use any regular expression withoutperformance problems, which is not the case with previous implementations or algorithms.