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

摘要

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

主权项

一种基于智能有限自动机的正则表达式匹配方法，其特征在于，该方法为：1）选取合适的正则表达式规则集；2）构建智能有限自动机；3）通过智能有限自动机匹配方法对每个读入的测试集分别进行字符串匹配，并对匹配结果进行统计；   所述的正则表达式规则集选取方法为，采用100个规则集，每个规则集包含100条形式为{.*SubStr1.*SubStr2….*SubStrN}的正则表达式，其中所有子串SubStr1、SubStr2……SubStrN具有相同的长度，测试集为1MB的字符串集；其中，N为100；   所述智能有限自动机的构建过程包括两个步骤：（1）在扩展有限自动机的分支迁移边上增加操作指令来判断是否状态迁移，消除不必要的状态迁移；（2）消除扩展有限自动机中的回退迁移边，从而减少扩展有限自动机的存储空间开销。