基于决策树剪枝的模式匹配方法

摘要

本发明提出一种基于决策树剪枝的模式匹配方法，其结合决策树剪枝方法的简化AC算法，包括自动机的生成、自动机的简化、计算失败指针、存储后缀表与匹配的执行等步骤。本发明将传统自动机类型模式匹配算法拆分为两个步骤：匹配可能的判定与匹配确认。通过简化自动机判别文本串与模式集中模式串有无匹配的可能，再进行匹配的确认。在保证速度的前提下，本发明提出的简化方法相比传统自动机类型模式匹配算法内存消耗减少35％‑40％。此外，本发明通过决策树剪枝方法可有效减小自动机规模，删除对分类判定无用的节点，有效降低传统自动机类型模式匹配的内存消耗。