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
Publicized: 2017/12/19
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017FCL0004
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>>
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.