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!
|
| _version_ | 1841539795280461824 |
|---|---|
| author | Wei HE Yun-fei GUO Hong-chao HU |
| author_facet | Wei HE Yun-fei GUO Hong-chao HU |
| author_sort | Wei HE |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3160519b882c430ea7c3931e52011bd4 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2013-10-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-3160519b882c430ea7c3931e52011bd42025-01-14T06:41:33ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2013-10-013418319059676065States constrain-based algorithm for large scale regular expression matchingWei HEYun-fei GUOHong-chao HUBy 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.http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2013.10.021/regular expressionstate explosionautomata convertstate constrains |
| spellingShingle | Wei HE Yun-fei GUO Hong-chao HU States constrain-based algorithm for large scale regular expression matching Tongxin xuebao regular expression state explosion automata convert state constrains |
| title | States constrain-based algorithm for large scale regular expression matching |
| title_full | States constrain-based algorithm for large scale regular expression matching |
| title_fullStr | States constrain-based algorithm for large scale regular expression matching |
| title_full_unstemmed | States constrain-based algorithm for large scale regular expression matching |
| title_short | States constrain-based algorithm for large scale regular expression matching |
| title_sort | states constrain based algorithm for large scale regular expression matching |
| topic | regular expression state explosion automata convert state constrains |
| url | http://www.joconline.com.cn/zh/article/doi/10.3969/j.issn.1000-436x.2013.10.021/ |
| work_keys_str_mv | AT weihe statesconstrainbasedalgorithmforlargescaleregularexpressionmatching AT yunfeiguo statesconstrainbasedalgorithmforlargescaleregularexpressionmatching AT hongchaohu statesconstrainbasedalgorithmforlargescaleregularexpressionmatching |