Efficient multi-pattern matching algorithm based on dual-state coding
一种基于双重状态编码的多模式匹配算法

Multi-pattern matching algorithm based on finite automata is one of the core technologies on network content filtering and managing. However, with the pattern set becomes larger, it needs too much storage cost. To decrease its space complexity, meanwhile keeping low time complexity, this paper proposed a method based on keywords predisposing and state coding. Keywords predisposing could filter out massive irrelevant matching, it obviously decreased the complexity. And state coding eliminated much failure transitions, could efficiently decrease the storage cost. Theoretical analysis and simulation results show, compared to traditional algorithm based on TCAM, this algorithm can provide a high throughput with a moderate memory requirement.