Experimental Analysis of an Online Dictionary Matching Algorithm for Regular Expressions with Gaps

Dictionary matching for regular expressions has gained recent interest because of a multitude of applications, including DNA sequence analysis, XML filtering, and network traffic analysis. In some applications, allowing wildcard and character class gaps in strings is enough, but usually the full expressive power of regular expressions is needed. In this paper we present and analyze a new algorithm for online dictionary matching for regular expressions. The unique feature of our algorithm is that it builds upon an algorithm for dictionary matching of string patterns with wildcard gaps, but is also capable of treating more complex regular expressions. In our experiments we used real data from expressions used for filtering spam e-mail. The size of the dictionary, that is, the number of different regular expressions to be matched varied from one to 3080. To find out how our algorithm scales to much larger numbers of patterns, we made small random changes to these patterns to produce up to 100000 patterns that are similar in style. We found out that the scalability of our algorithm is very good, being at its best for 10000–20000 patterns. Our algorithm outperforms the tested competitors for large dictionaries, GNU grep already for tens of patterns and Google’s RE2 for hundreds of patterns.