A Heuristic for Constructing Smaller Automata Based on Suffix Sorting and Its Application in Network Security
Inbok Lee, Victor Craig Valgenti, Min S. KIM, Sung-il OH · IEICE Transactions on Information and Systems · 2018
In this paper we show a simple heuristic for constructing smaller automata for a set of regular expressions, based on suffix sorting: finding common prefixes and suffixes in regular expressions and merging them. It is an important problem in network security. We applied our approach to random and real-world regular expressions. Experimental results showed that our approach yields up to 12 times enhancement in throughput.