(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(10)申请公布号 CN 101876986 A
(43)申请公布日 2010.11.03
(21)申请号 CN200910226279.4
(22)申请日 2009.11.27
(71)申请人 福建星网锐捷网络有限公司
    地址 350002 福建省福州市仓山区金山大道618号桔园州工业园19号楼
(72)发明人 黄凯明
(74)专利代理机构 北京同达信恒知识产权代理有限公司
    代理人 郭润湘
(51)Int.CI
      G06F17/30
                                                                  权利要求说明书 说明书 幅图
(54)发明名称
      基于有限状态自动机的字符串匹配方法及内容过滤设备
(57)摘要
      本发明公开了一种基于有限状态自动机的字符串匹配方法及内容过滤设备，包括：将DFA中符合设定条件的至少两个顺序关联的状态合并，得到合并后的DFA；相应的字符匹配过程包括：从字符串数据库中依次读取字符，根据当前状态及读取的字符，判断本次匹配是否为字符串匹配；若否，根据当前状态和读取的字符跳转到下一状态；若是，则从对应的字符串存储地址获取当前状态的匹配字符串，并读取下一个字符，判断是否与匹配字符串的下一个字符匹配，当匹配时继续读取下一个字符字符直至字符串匹配成功时，跳转到对应的下一状态；若否，则根据当前状态和读取的字符跳转到下一状态。该方法减少了字符匹配时访问内存的次数，提高了字符匹配的速度和效率。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种基于有限状态自动机DFA的字符串匹配方法，其特征在于，包括：将所述DFA中符合设定条件的至少两个顺序关联的状态中包含的状态跳转情况不相同的特定字符组成匹配字符串，得到至少一个状态为匹配字符串后跳转的合并后的DFA；当基于所述合并后的DFA进行字符匹配时，执行下列步骤：
从字符串数据库中依次读取字符，根据当前状态及本次读取的字符，判断本次匹配是否为字符串匹配；
若否，则根据所述当前状态和读取的字符跳转到下一状态；
若是，则从对应的字符串存储地址获取当前状态的所述匹配字符串，并从所述字符串数据库中读取下一个字符，判断读取的下一个字符是否与所述匹配字符串的下一个字符匹配，若是，则继续从所述字符串数据库中读取下一个字符字符进行判断，直至字符串匹配成功时，跳转到当前状态和所述匹配字符串所对应的下一状态；若否，则根据所述当前状态和读取的字符跳转到下一状态。
2.如权利要求1所述的方法，其特征在于，所述根据当前状态及本次所读取的字符，判断本次匹配是否为字符串匹配，具体包括：
根据当前状态和本次读取的字符，确定出对应的跳转状态的状态序号；
比较确定出的状态序号是否大于状态合并后的DFA中当前状态的最大状态序号，当大于时，确定本次匹配为字符串匹配；否则，确定本次匹配不是字符串匹配。
3.如权利要求2所述的方法，其特征在于，所述合并后的DFA以一维数组的形式存放；
每个当前状态在输入字符后所对应的跳转状态的存储位置，根据该当前状态的状态序号和输入字符所对应的十进制值确定。
4.如权利要求3所述的方法，其特征在于，根据当前状态和本次读取的字符，确定对应的跳转状态的状态序号，具体包括：
根据当前状态及本次所读取的字符的十进制值，计算得到对应的跳转状态在一维数组中的存储位置；
从确定出的存储位置读取所述对应的跳转状态的状态序号。
5.如权利要求4所述的方法，其特征在于，所述计算得到对应的跳转状态的存储位置，具体为：
计算当前状态的状态序号与256的乘积，计算所述乘积与本次输入字符所对应的十进制值之和，得到对应的跳转状态存储位置在一位数组中的存储位置。
6.如权利要求1-5任一所述的方法，其特征在于，所述匹配字符串存储在一个一维数组中；
当需要读取字符串时，根据当前状态的状态序号确定当前状态的所述匹配字符串存储位置，从存储匹配字符串的一位数组中对应的字符串存储位置读取存储的该匹配字符串。
7.一种基于有限状态自动机DFA的字符串匹配装置，其特征在于，包括：
生成模块，用于将所述DFA中符合设定条件的至少两个顺序关联的状态中包含的状态跳转情况不相同的特定字符组成匹配字符串，得到至少一个状态为匹配字符串后跳转的合并后的DFA；
字符串常量结束符判断模块，用于从字符串数据库中依次读取字符，基于所述合并后的DFA根据当前状态及本次读取的字符，判断本次匹配是否为字符串匹配；若是，通知所述第一执行模块；若否，通知所述第二执行模块；
第一执行模块，用于从对应的字符串存储地址获取当前状态的所述匹配字符串，并从所述字符串数据库中读取下一个字符，判断读取的下一个字符是否与所述匹配字符串的下一个字符匹配，若是，则继续从所述字符串数据库中读取下一个字符字符进行判断，直至字符串匹配成功时，跳转到当前状态和所述匹配字符串所对应的下一状态；若否，则通知所述第二执行模块；
第二执行模块，用于根据所述当前状态和读取的字符跳转到下一状态。
8.如权利要求7所述的装置，其特征在于，所述判断模块，具体包括：
第一读取单元，用于从字符串数据库中依次读取字符；
确定单元，用于根据当前状态和所述第一读取单元本次读取的字符，确定出对应的跳转状态的状态序号；
第一判断单元，用于比较确定出的状态序号是否大于状态合并后的DFA中当前状态的最大状态序号；当大于时，确定本次匹配为字符串匹配并通知所述第一执行模块；否则，确定本次匹配不是字符串匹配并通知所述第二执行模块。
9.如权利要求7或8所述的装置，其特征在于，所述第一执行模块，具体包括：
获取单元，用于根据当前状态的状态序号确定当前状态的所述匹配字符串存储位置，从对应的字符串存储位置读取存储的该匹配字符串；
第二读取单元，用于从所述字符串数据库中读取下一个字符；
第二判断单元，用于判断读取的下一个字符是否与所述匹配字符串的下一个字符匹配，若是，
则通知第二读取单元继续从所述字符串数据库中读取下一个字符字符；若否，则通知所述第二执行模块。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。