A Heuristic for Constructing Smaller Automata Based on Suffix Sorting and Its Application in Network Security

Inbok LEE  Victor C. VALGENTI  Min S. KIM  Sung-il OH  

IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.3   pp.613-615
Publication Date: 2018/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —)
string algorithm,  regular expression,  automata,  network security,  

Full Text: PDF(271.9KB)
>>Buy this Article

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.