\input zb-basic
\input zb-ioport
\iteman{io-port 06084472}
\itemau{Liu, Tingwen; Sun, Yong; Guo, Li; Fang, Binxing}
\itemti{SDFA: series DFA for memory-efficient regular expression matching.}
\itemso{Moreira, Nelma (ed.) et al., Implementation and application of automata. 17th international conference, CIAA 2012, Porto, Portugal, July 17--20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31605-0/pbk). Lecture Notes in Computer Science 7381, 337-344 (2012).}
\itemab
Summary: Regular expression (RegEx) matching plays an important role in various network, security and database applications. Deterministic finite automata (DFA) is the preferred representation to achieve online RegEx matching in backbone networks, because of its one single pass over inputs for multiple RegExes and guaranteed performance of $O(1)$ memory bandwidth per symbol. However, DFA may occupy prohibitive amounts of memory due to the explosive growth in its state size. In this work, we propose series DFA (SDFA) to address the problem. The main idea is to cut a complex RegEx into several ordered and small RegExes carefully, and then concatenate their compact DFAs in series to match. Experimental results show that SDFA can achieve significant reduction in memory size at the cost of limited number of memory bandwidth.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-31606-7\_30}
\end