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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1000-436X |