Tongxin xuebao (Oct 2013)

States constrain-based algorithm for large scale regular expression matching

  • Wei HE,
  • Yun-fei GUO,
  • Hong-chao HU

Journal volume & issue
Vol. 34
pp. 183 – 190

Abstract

Read online

By analysis of state explosion in deterministic finite automata DFA,a novel algorithm Group2-DFA based on state constrains was proposed to reduce the memory usage.With the state constrains,states in NFA were classified into several groups.Group2-DFA introduces two-level classification and merges NFA and DFA together to a hybrid FA construction.The experiments show that Group2-DFA can reduce memory usage efficiently and keep high throughput with a small increase of memory reading time.With 300 regex rules,Group2-DFA can cut 75% states and achieve 1Gbps throughput.

Keywords