基于智能有限自动机的正则表达式匹配方法

摘要

本发明公开了一种基于智能有限自动机(Smart Finite Automaton，SFA)的正则表达式匹配方法：选取合适的正则表达式规则集；构建智能有限自动机；通过智能有限自动机匹配方法对每个读入的测试集分别进行字符串匹配，并对匹配结果进行统计。实验结果表明，与XFA相比，SFA在存储空间开销上减少了44.1％，在存储器访问次数上减少了69.1％，提高了正则表达式匹配的时空效率。解决了XFA存在的冗余迁移边问题，能够有效的节省存储空间，同时也提高了XFA的性能。为当前网络带宽和业务流量迅猛增长环境下，正则表达式匹配方法应用时面临的线速数据包处理的吞吐量要求和存储空间需求提供了一种行之有效的解决方案。

主权项

一种基于智能有限自动机的正则表达式匹配方法，其特征在于，该方法为：1)选取合适的正则表达式规则集；2)构建智能有限自动机；3)通过智能有限自动机匹配方法对每个读入的测试集分别进行字符串匹配，并对匹配结果进行统计。