States constrain-based algorithm for large scale regular expression matching
By analysis of state explosion in deterministic finite automata DFA,a novel algorithm Group<sup>2</sup>-DFA based on state constrains was proposed to reduce the memory usage.With the state constrains,states in NFA were classified into several groups.Group<sup>2</sup>-DFA intr...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2013-10-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2013.10.021/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | By analysis of state explosion in deterministic finite automata DFA,a novel algorithm Group<sup>2</sup>-DFA based on state constrains was proposed to reduce the memory usage.With the state constrains,states in NFA were classified into several groups.Group<sup>2</sup>-DFA introduces two-level classification and merges NFA and DFA together to a hybrid FA construction.The experiments show that Group<sup>2</sup>-DFA can reduce memory usage efficiently and keep high throughput with a small increase of memory reading time.With 300 regex rules,Group<sup>2</sup>-DFA can cut 75% states and achieve 1Gbps throughput. |
|---|---|
| ISSN: | 1000-436X |