Improved DFA algorithm based on multi-dimensional finite automata

Abstract

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.

Keywords

• regular expression
• DFA
• finite automata
• state explosion