MDC-DFA: A multi-dimensional cube deterministic finite automata-based feature matching algorithm
2015
The regular expression matching algorithm (REM) is widely applied in the deep packet inspection(DPI), which is more flexible and efficient compared with conventional exact matching algorithm. The REM based on the deterministic finite automaton (DFA) is applicable in the high speed networks due to its linear matching speed. However, it faces the problem of the state explosion simultaneously. Therefore, we propose a multi-dimensional cube deterministic finite automata algorithm (MDC-DFA) for anomaly feature matching. The algorithm divides and compresses redundant states by each dimension, and achieves equivalent state transition by constructing dynamic nodes. Theory and simulation results show that, compared with conventional deterministic finite automata algorithm, the algorithm achieves a logarithm-level compression to the number of states and the storage space while maintaining the time complexity.
Keywords:
- Mathematical optimization
- Deterministic finite automaton
- Nondeterministic finite automaton
- Deterministic automaton
- Klee–Minty cube
- Deterministic algorithm
- Two-way deterministic finite automaton
- Mathematics
- Quantum finite automata
- DFA minimization
- Theoretical computer science
- Algorithm design
- Computer science
- Algorithm
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
1
Citations
NaN
KQI