Improved DFA algorithm based on multi-dimensional finite automata
Compiling multiple regular expression signatures into a combined DFA can blowup in state and storage space.Explanations from the prospective of information theory and multi-dimensional mathematical model were proposed fo-cusing on the most serious state explosion.Redundancy states were divided into...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2015-05-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015101/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539655314440192 |
|---|---|
| author | ONGYang-yang G IUQin-rang L ANGZhen-xi Y HAOXiang-yu S INGChi-qiang X IAOHui-juan J ENGZhi-bin P |
| author_facet | ONGYang-yang G IUQin-rang L ANGZhen-xi Y HAOXiang-yu S INGChi-qiang X IAOHui-juan J ENGZhi-bin P |
| author_sort | ONGYang-yang G |
| collection | DOAJ |
| description | Compiling multiple regular expression signatures into a combined DFA can blowup in state and storage space.Explanations from the prospective of information theory and multi-dimensional mathematical model were proposed fo-cusing on the most serious state explosion.Redundancy states were divided into zero-dimensional ones and one-dimensional ones.The former were compressed by dimension,and the later were dynamically built.The space com-plexity of the model came to the theoretical lower bound by the above methods.Then the multi-dimensional finite auto-mata (MFA) was proposed with the model.Experiments show that,the construction time taken by MFA is slightly less than XFA and is 2～3 orders of magnitude lower than DFA,STT redundancy compression algorithms and Hybrid-FA; the memory space of MFA is slightly higher than XFA,but is 1～2 orders of magnitude lower than DFA,STT redundancy compression algorithms,mDFA and Hybrid-FA; in the aspect of matching time,MFA ranks after DFA and Hybrid-FA,but ranks before XFA,and it achieves 1～2 orders of magnitude lower than that of STT redundancy compression algo-rithms and mDFA. |
| format | Article |
| id | doaj-art-5f3c3c01ec9e4dd882b8a968f8e1e9c3 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2015-05-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-5f3c3c01ec9e4dd882b8a968f8e1e9c32025-01-14T06:46:27ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2015-05-013617418659693261Improved DFA algorithm based on multi-dimensional finite automataONGYang-yang GIUQin-rang LANGZhen-xi YHAOXiang-yu SINGChi-qiang XIAOHui-juan JENGZhi-bin PCompiling multiple regular expression signatures into a combined DFA can blowup in state and storage space.Explanations from the prospective of information theory and multi-dimensional mathematical model were proposed fo-cusing on the most serious state explosion.Redundancy states were divided into zero-dimensional ones and one-dimensional ones.The former were compressed by dimension,and the later were dynamically built.The space com-plexity of the model came to the theoretical lower bound by the above methods.Then the multi-dimensional finite auto-mata (MFA) was proposed with the model.Experiments show that,the construction time taken by MFA is slightly less than XFA and is 2～3 orders of magnitude lower than DFA,STT redundancy compression algorithms and Hybrid-FA; the memory space of MFA is slightly higher than XFA,but is 1～2 orders of magnitude lower than DFA,STT redundancy compression algorithms,mDFA and Hybrid-FA; in the aspect of matching time,MFA ranks after DFA and Hybrid-FA,but ranks before XFA,and it achieves 1～2 orders of magnitude lower than that of STT redundancy compression algo-rithms and mDFA.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015101/regular expressionDFAfinite automatastate explosion |
| spellingShingle | ONGYang-yang G IUQin-rang L ANGZhen-xi Y HAOXiang-yu S INGChi-qiang X IAOHui-juan J ENGZhi-bin P Improved DFA algorithm based on multi-dimensional finite automata Tongxin xuebao regular expression DFA finite automata state explosion |
| title | Improved DFA algorithm based on multi-dimensional finite automata |
| title_full | Improved DFA algorithm based on multi-dimensional finite automata |
| title_fullStr | Improved DFA algorithm based on multi-dimensional finite automata |
| title_full_unstemmed | Improved DFA algorithm based on multi-dimensional finite automata |
| title_short | Improved DFA algorithm based on multi-dimensional finite automata |
| title_sort | improved dfa algorithm based on multi dimensional finite automata |
| topic | regular expression DFA finite automata state explosion |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015101/ |
| work_keys_str_mv | AT ongyangyangg improveddfaalgorithmbasedonmultidimensionalfiniteautomata AT iuqinrangl improveddfaalgorithmbasedonmultidimensionalfiniteautomata AT angzhenxiy improveddfaalgorithmbasedonmultidimensionalfiniteautomata AT haoxiangyus improveddfaalgorithmbasedonmultidimensionalfiniteautomata AT ingchiqiangx improveddfaalgorithmbasedonmultidimensionalfiniteautomata AT iaohuijuanj improveddfaalgorithmbasedonmultidimensionalfiniteautomata AT engzhibinp improveddfaalgorithmbasedonmultidimensionalfiniteautomata |