For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
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>>
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.