一种FS算法最差情况下的快速多模式匹配方法

摘要

本发明公开了一种FS算法最差情况下的快速多模式匹配方法。本方法为：1）将模式串集合转换成反向有限自动机，计算坏字符转移函数skip1和好后缀转移函数skip2；2）构建自动机中状态s在遇到字符c时发生失配所用词典，包括：匹配串u在其他模式串中的所有深度大于u的出现位置，后缀suffix(u)在其他模式串中的所有深度大于suffix(u)的出现位置；3）设置一倒计时值cdown；将待匹配文件与模式串集合进行匹配，当skip2跳转时，记录当前失配状态对应的词典，跳转后每匹配一个字符cdown减1；若发生skip1跳转，则cdown增加skip1的跳转值；4）当cdown为0且记录的词典不为空时，利用当前记录的词典搜索对应的子串终止状态，找到相应的跳转位置，继续匹配。

主权项

一种FS算法最差情况下的快速多模式匹配方法，其步骤为：1）将所选的模式串集合转换成反向有限自动机，同时根据模式串中的字符分布计算坏字符转移函数skip1和好后缀转移函数skip2；2）构建该反向有限自动机中的状态s在遇到字符c时发生失配所用的词典dict(s,c)，该词典dict(s,c)包括：已匹配串u在所述模式串集合其他模式串中的所有深度大于u的出现位置，以及已匹配串u的后缀suffix(u)在其他模式串中的所有深度大于suffix(u)的出现位置；其中，c∈Σ，Σ是所述模式串集中的所有字符的集合；3）设置一个倒计时值cdown=skip2(s,c)‑depth(s)；将输入的待匹配文件与所述模式串集合进行匹配，当发生失配使用skip2跳转时，记录当前失配状态对应的词典dict，跳转后每匹配一个字符cdown减1；若发生skip1跳转，则cdown增加skip1的跳转值；其中，skip2(s,c)表示在状态s处遇到失配字符c后，利用skip2函数计算得到的跳转长度，depth(s)表示s在反向有限自动机中的深度；4）当cdown为0且记录的词典不为空时，利用当前记录的词典dict来搜索到对应的子串终止状态，找到相应的跳转位置，然后匹配跳转到该位置，继续匹配。