An improved DFA for fast regular expression matching
ACM SIGCOMM Computer Communication Review2008Vol. 38(5), pp. 29–40
Citations Over TimeTop 10% of 2008 papers
Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci, Gianni Antichi, Andrea Di Pietro
Abstract
Modern network devices need to perform deep packet inspection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement regular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue. This paper presents a new representation for deterministic finite automata (orthogonal to previous solutions), called Delta Finite Automata (δFA), which considerably reduces states and transitions and requires a transition per character only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.
Related Papers
- → Space-time tradeoff in regular expression matching with semi-deterministic finite automata(2011)49 cited
- → SI-DFA: Sub-expression integrated Deterministic Finite Automata for Deep Packet Inspection(2013)6 cited
- → A Memory Efficient Regular Expression Matching by Compressing Deterministic Finite Automata(2015)