CN101551803A - 一种建立模式匹配状态机、模式识别的方法和装置 - Google Patents

Abstract

本发明公开了一种建立模式匹配状态机、模式识别的方法和装置，属于模式匹配技术领域。使用的方法包括：获取划分后得到的子关键字字段；根据所述子关键字字段，生成状态转移Goto函数；并根据Goto函数，生成所述各状态节点的失效Failure函数；根据Goto函数和Failure函数，生成各状态节点的下一跳状态转移δ函数，根据生成的δ函数进行模式状态的匹配。所述建立装置包括：获取模块，Goto函数生成模块，Failure函数生成模块，δ函数生成模块。通过在多字节AC算法消除其原有Failure链，连同原有Goto函数一同转换成统一的δ转移函数，且在对失效链进行转换的过程中对于会Failure到初始状态的表项不生成，从而避免了大规模的存储空间的增长，优化了AC算法的存储结构，提高了AC算法的处理速度。

Description

一种建立模式匹配状态机、模式识别的方法和装置

技术领域

本发明涉及模式匹配技术领域，特别涉及一种建立模式匹配状态机、模式识别的方法和装置。

背景技术

模式匹配一般是指在文本数据中搜索预定义的关键字。模式匹配问题是计算机科学中的一个基本问题，其研究内容在信息检索、模式识别等众多领域均有重要价值，在拼写检查、语言翻译、数据压缩、搜索引擎、入侵检测、内容过滤、计算机病毒特征码匹配以及基因序列比较等应用中起着重要的作用。比如，在一些信息获取、文本编辑应用中，用户会指定一些关键字，需要在文本中快速定位关键字的位置。

Aho-Corasick算法(阿霍-克若思克算法，简称AC算法)描述了一种简单有效的算法，能够在任意的文本中定位有限数目的关键字的所有位置。其原理是：首先根据这一系列关键字定义一个有限状态模式匹配机，然后把文本作为模式匹配机的输入。只要匹配到关键字，就会通报本关键字匹配成功。其中，AC算法可以根据每次输入的字节数，划分为原始AC算法(每次输入1个字节)和多字节AC算法。

参见图1，为现有技术提供的利用原始AC构建的函数示意图，以用户指定关键字集合{he，she，his，hers}为例，用户希望在文本搜索中出现任一个关键字，就输出搜索结果，通知用户。利用原始AC进行模式匹配的过程如下：根据关键字集合{he，she，his，hers}生成Goto函数(图1A所示)、Failure(图1B所示)、Output函数(图1C所示)，包括两个步骤：第一步确定状态和Goto函数(以g表示)，第二步计算Failure函数(以f表示)。Output函数的构建在第一步开始，在第二步完成。以输入文本”sshe”进行搜索为例，当输入s时，g(0，s)＝3，所以迁移到状态3；输入第二个s，Goto函数失败，g(3，s)＝fail，则调用Failure函数，f(3)＝0表示跳转到状态0，然后g(0，s)＝3，所以当前状态仍然是状态3；输入h，g(3，h)＝4，迁移到状态4；输入‘e’，g(4，e)＝5，迁移到状态5；因为Output(5)＝{she，he}，所以本次搜索发现了{she，he}两个用户预定义关键字。

由于原始AC算法的每次输入都是1个字节，为了提高算法效率，Satang提出了改进AC算法(即多字节AC算法)，其基本思想是：每次输入n个字节并进行检测，因为定义的n个字节的特征串在输入的待测数据中的位置有可能并非正好是从输入数据起始位置开始的n的整数倍上，可能会出现任意偏移0个到n-1个字符，为了避免检测遗漏，因此需要对所有偏移位置都进行检测，即并行的采用n个检测状态匹配机来进行同时检测。

参见图2，为现有技术提供的利用多字节AC构建的函数示意图，以用户指定的关键词的组合为{S1：：technical；S2：technically；S3：tel.；S4：telephone；S5：phone；S6：elephant}为例，检测步长n为4字节；图2A给出了构造得到的Goto函数示意图，从状态q0开始，输入tech转移到q1，输入tele转移到q2，输入phon转移到q3，输入elep转移到q4等等。由于匹配模式不一定都是4字节的整数倍，因此还需要补充短的字段，图2B给出了带Failure函数的示意图，该图补充了短的字段。

采用多字节的AC，可以在每次跳转以n字节为步长，相对于原始的AC算法实现n字节跳转需要访问n次内存，现在只需要访问一次，是原始的AC的访问速度的4倍。

但是，无论是原始AC算法，还是多字节AC算法，由于Failure函数的出现，会导致AC模式匹配状态机在Goto函数出现Failure时要多一次或多次访问内存的操作-需要去读取Failure函数，影响了AC算法的效率。

并且，特别是针对多字节AC算法，状态转移表的索引不只是输入状态，还要包括输入的字符串，所以每条记录必须把完整的Failure链保存下来，不然一旦匹配失败，将找不到失败后的状态，参见图3，为针对图2提供的多字节AC算法的的状态示意图，以图中的<q2，phon>记录，如果只保存第一级失效的q3状态，当输入的字符串在q3状态下仍然失效时，则需要查询到在q3输入状态下的Failure输出状态，但q3的Failure输出状态是保存在q3的父状态即<q0，phon>条目中的，由于无法从简单的从q3反推出q3的上一级状态是q0，也就无法在这个状态表中进行新的失效函数的查询，因此会导致无法工作下去。

并且，由于Failure链不定长，无法在一个表项保存，所以应当另建Failure链表用来保存完整Failure链，通过指针函数等形式将原始表中的Failure指向新建的完整Failure链表的某个地址，而这样处理方法复杂多变，且需要额外的存储空间，因此需要额外的处理步骤。

综上，为了提高AC算法的效率，现有技术提供一种针对原始AC算法去除Failure函数得方法，其中，该方法通过引入一个δ函数，取代原先的Goto函数g，即将所有Goto函数和Failure函数合并了后的新的转移函数δ，其创建要以Goto函数和Failure函数为基础。建立了这个δ函数以后，AC算法的模式匹配状态机就由一个有限的状态集合S及这个下一跳转移函数δ组成。对于每一个状态r下的输入字符a，δ(s，a)都会有一个属于有限的状态集合S的输出状态s，也就是说对于每一个输入字符，都有一个确定的输出状态。这样实际上就没有了Failure函数了，在进行模式匹配时简单的执行state←δ(state，a_i)即可。其中，生成该δ函数的步骤为：

1.新建一个空的状态集合S；

2.对于最起始的状态0，将每一个输入的Goto函数生成的状态做为δ函数的输出状态：δ(0，a)＝g(0，a)，如果输出状态r不为0，则将该状态r加入到空的状态集合中去：S←S∪r；

3.从状态集合中取出每一个新的状态s，将该状态s先从状态集合S中删除，对于该状态s下的每一个输入字符a，执行：

(1).如果转移函数g(s，a)的输出不是fail，则将该输出状态设置为该状态下的δ函数的输出，如：δ(s，a)＝g(s，a)；

(2).如果转移函数g(s，a)的输出是fail，则将该输出状态的失效函数的输出状态作为新的输入状态，执行转移函数δ，将其输出状态做为转移函数的输出状态：δ(s，a)＝δ(f(s)，a)；

4.依次类推，直到状态集合S中的状态为空。

针对图1，图4为采用δ函数后消除Failure的状态转移示意图，其中，以状态8为例，在图1中只有Goto到状态9的转移函数和Failure到状态0的失效函数，但现在经过合并后，就把失效到状态0的失效函数转成了输入h到状态1的新的δ函数了，其中，输入为“.”是指除了s、h外所有其他的字符。有了这样的δ函数后，就不需要考虑是Failure还是Goto函数了，可以依据δ函数的指示进行明确的一步跳转，提高原始AC算法的效率。

但是，在实际实现时，为了保证运行效率，每个状态下的可转移状态都是一个256个单元的一维数组，对每个输入状态下的所有可能的n个输入都填入下一跳转移输出δ函数，n个字节的所有可能输入是n×256个可能，而实际有效的输入不会超过5个，这样的存储形式，会造成资源的浪费。

发明内容

为了解决AC算法中的Failure函数处理导致的复杂存储、处理和低效率的问题，提高AC算法的处理速度，本发明实施例提供了一种建立模式匹配状态机、模式识别的方法和装置。所述技术方案如下：

一种建立模式匹配状态机的方法，所述方法包括：

根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；

根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

一种模式识别的方法，所述方法包括：

根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；

根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

根据所述δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和所述子关键字字段为索引的δ函数的表项，则设置所述初始状态节点q0为所述输入状态节点的δ函数的输入状态，根据所述新的输入状态和所述子关键字字段执行δ函数；如果在初始状态节点q0无法获取到所述子关键字字段的匹配，则设置所述q0为输出状态。

一种建立模式匹配状态机的装置，所述装置包括：

根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；

根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

根据所述δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和所述子关键字字段为索引的δ函数的表项，则设置所述初始状态节点q0为所述输入状态节点的δ函数的输入状态，根据所述新的输入状态和所述子关键字字段执行δ函数；如果在初始状态节点q0无法获取到所述子关键字字段的匹配，则设置所述q0为输出状态。

一种模式识别的装置，所述装置包括：

模式匹配状态机建立模块，用于根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

处理模块，用于根据所述模式匹配状态机建立模块建立的δ函数，根据所述δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和所述子关键字字段为索引的δ函数的表项，则设置所述初始状态节点q0为所述输入状态节点的δ函数的输入状态，根据所述新的输入状态和所述子关键字字段执行δ函数；如果在初始状态节点q0无法获取到所述子关键字字段的匹配，则设置所述q0为输出状态。

本发明实施例提供的技术方案的有益效果是：

通过在多字节的AC算法消除其原有的Failure链，连同原有的Goto函数一同转换成一种统一的δ转移函数，在对失效链进行转换的过程中对于会Failure到初始状态的表项不生成，从而不会导致大规模的存储空间的增长，节约了存储空间，同时优化了AC算法的存储结构，简单并固化了AC算法的处理步骤，从而最终提高了AC算法的处理速度。

附图说明

图1是现有技术提供的利用原始AC算法构建的函数示意图；

图2是现有技术提供的利用多字节AC算法构建的函数示意图；

图3是现有技术提供的多字节AC算法的状态示意图；

图4是现有技术提供的原始AC算法采用δ函数后消除Failure的状态转移示意图；

图5是本发明实施例1提供的建立模式匹配状态机的方法流程图；

图6是本发明实施例1提供的多字节AC算法消除Failure的状态示意图；

图7是本发明实施例1提供的未采用本发明实施例提供的技术方案的多字节AC的有向图示意图；

图8是本发明实施例1提供的未采用本发明实施例提供的技术方案的多字节AC的状态转移表示意图；

图9是本发明实施例1提供的相对于图7采用本发明实施例提供的技术方案去除Failure链的有向示意图；

图10是本发明实施例1提供的相对于图7采用本发明实施例提供的技术方案去除Failure链的状态转移表示意图；

图11是本发明实施例2提供的建立模式匹配状态机的装置示意图；

图12是本发明实施例3提供的模式识别的装置示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进一步地详细描述。

本发明实施例提供的建立模式匹配状态机的方法如下：根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；根据子关键字字段，生成状态转移Goto函数；并根据Goto函数，生成各状态节点的失效Failure函数；根据Goto函数和Failure函数，生成各状态节点的下一跳状态转移δ函数。

其中，在获取子关键字字段时，按预设字节为单位，对预定义的关键字集合中的关键字进行划分，得到子关键字字段，其中，对关键字划分时，如果不满足预设字节的长度，不满足预设字节长度的字符构成子关键字字段。

其中，根据Goto函数和Failure函数，生成各状态节点的下一跳状态转移δ函数，具体为：

依次获取状态队列S中的每一个状态节点，当获取每一个状态节点时，从状态队列S中删除获取的状态节点，并根据获取的状态节点和子关键字字段，生成状态节点对应的下一跳状态转移δ函数的输出。其中，更为具体详细的过程如下：

创建状态队列S，状态队列初始为空；

从起始状态节点q0开始，根据q0的Goto函数和子关键字字段，判断字段串字段对应的Goto函数的输出状态节点是否存在；当输出状态节点存在时，设置字段串字段对应Goto函数的输出状态节点为字段串字段对应δ函数的输出状态节点；并将非q0的输出状态节点依次添加到状态队列S中；

按照在状态队列S中的状态节点先进先出的原则，依次获取状态队列中的每一个状态节点，当获取一个状态节点时，从状态队列中删除获取的状态节点，并根据获取的状态节点和子关键字字段，生成状态节点对应的δ函数的输出，并将非空的输出状态节点依次添加到状态队列S中；

直到状态队列为空。

上述根据获取的状态节点和子关键字字段，生成状态节点对应的δ函数的步骤，具体为：

将字段串字段做为状态节点的输入，判断状态节点对应的Goto函数的输出状态节点是否存在；

如果状态节点的Goto函数的输出状态节点不存在，则判断状态节点的Failure函数输出是否为初始状态节点q0，如果是，则不建立状态节点的δ函数输出表项，结束；否则，根据状态节点的Failure函数的输出状态节点和子关键字字段，获取状态节点的δ函数的输出；

如果Goto函数的输出状态节点存在，将Goto函数的输出状态节点设置为状态节点的δ函数的输出，并将δ函数的输出状态节点添加到状态队列。

其中，根据输出状态节点的Failure函数的输出状态节点和子关键字字段，获取δ函数的输出，具体为：

将状态节点的Failure函数的输出状态节点和子关键字字段做为δ函数的输入，获取δ函数的输出，生成Failure函数的输出状态节点的δ函数的输出，其中，当δ函数的输出不存在，则不建立状态节点的δ函数输出表项，结束。

进一步地，利用上述建立的模式状态匹配机，进行模式识别时，根据δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和子关键字字段为索引的δ函数的表项，则设置初始状态节点q0为输入状态节点的δ函数的输入状态，根据新的输入状态和子关键字字段执行δ函数；如果在初始状态节点q0无法获取到子关键字字段的匹配，则设置q0为输出状态。

本发明实施例提供的技术方案，不会导致大规模的存储空间的增长，节约了存储空间，同时优化了AC算法的存储结构，简单并固化了AC算法的处理步骤，从而最终提高了AC算法的处理速度，具体内容请参见如下各实施例：

实施例1

参见图5，本发明实施例提供了一种建立模式匹配状态机的方法，该方法利用了消除Failure链后δ函数处理的简洁性，又避免了大量Fail到初始状态q0的分支的存储，具体步骤如下：

101：将模式库中的字符串按预设长度为边界，将各种特征字符串分割成一连串的分段；

其中，将模式库中的字符串按预设长度为边界进行划分时，该预设长度可以为预设字节n，相应地，对于不足n字节的也单独形成一个分段。

例如，以背景技术中提到的关键字段{technical、technically、tel、telephone、phone、elephant}这些特征串，预设字节以4字节为例，则形成{tech nica l、tech nica lly、tel、tele phon e、phone}这样的分段，其中，tech、nica、l等等，可以称为字符串字段(或子关键字段)。

102：以分段获取的单元为单位，生成Goto有向图和相应的Goto函数。

其中，在生成Goto有向图和相应的Goto函数时，可以采用现有技术提供的任一生成Goto函数的方法。

103：以生成的Goto有向图为基础，生成各状态节点的Failure函数。

104：针对各状态节点，为每一个状态节点生成转移δ函数；具体内容如下：

104A：建立空的状态队列S；

104B：对于最起始的初始状态q0，将每一个输入的Goto函数生成的状态做为δ函数的输出状态：δ(0，a)←g(0，a)，如果输出状态r不为0，则将该状态r加入到空的状态队列S中去：S←S∪r；其中，本实施例中a为各字符串字段，如tech、nica等等。

104C：从状态队列中取出每一个新的状态s，将该状态s先从状态队列S中删除，对于该状态s下的输入字符a，执行如下步骤：

201：判断转移函数g(s，a)的输出是否是fail，如果是，则执行步骤202；否则执行步骤205；

202：判断该状态下的失效函数Failure输出是否为初始状态q0；如果是，则执行步骤203，否则，执行步骤204；

步骤203：不建立该节点的的转移函数表项，结束该状态的处理；

步骤204：将该状态的Failure的输出状态作为新的输入状态，执行转移函数δ，将其输出状态做为转移函数的输出状态：δ(s，a)←δ(f(s)，a)；

步骤205：将该输出状态设置为该状态下的δ函数的输出，如：δ(s，a)←g(s，a)；并将输出状态节点添加到状态队列S中。

同理，重复采用上述步骤，直到状态队列S的状态为空为止。

对于每一个状态r下的输入字符串，δ(s，a)都会有一个属于有限的状态队列S的输出状态s，也就是说对于每一个输入的字符，都有一个确定的输出状态。这样实际上就没有了Failure函数了，在进行模式匹配时简单的执行state←δ(state，a_i)即可。

当在执行state←δ(state，a_i)，如果不能在状态转移表中查询到和“输入状态+输入字符串”为索引的表项，就直接将q0设置为下一状态，即所有的输入状态下默认的最终的Failure处理函数输出都为q0。

综上所述，详细论述了建立模式匹配状态机的方法的过程，参见图6下面仍以上述提到的关键字段{technical、technically、tel、telephone、phone、elephant}为例，采用本发明实施例提供建立模式匹配状态机的方法获取的多字节AC算法去除Failure的状态转移表的示意图，相比与图3，图中提供的状态转移表增加了图中的：

<q6，e>

NULL

s5

为了进一步说明采用本发明实施例提供的建立模式匹配状态机的方法所带来的有益效果，以{s1：mnop hook，s2：ijlk mnop rest，s3：efgh ijlk mnop sina，s4：abcd efgh ijlk mnop qrst}，为例进行说明，其中定义步长为4字节，参见图7为未采用本发明实施例提供的技术方案的多字节AC的有向图示意图，其中，图中较细的直线代表Goto函数，其上的字符串代表输入字符串，较粗的曲线为Failure函数，很明显存在很多条重复的Failure链；相应地，参见图8，为未采用本发明实施例提供的技术方案的多字节AC的状态转移表示意图；其中，图示的存储结构造成了43％的不定长Failure链，对处理效率影响极大。

以图7为例，详细的说明应用本发明实施例提供的方法后是如何消除掉冗余的Failure链，内容如下：

首先，创建状态队列S，该状态队列初始为空集合队列；

然后，针对初始状态q0，根据Goto函数以及字符串，生成非q0的q41、q31、q21和q11，并将生成的q41、q31、q21和q11添加到状态队列S中；

其次，根据先在状态队列中先进先出的原则，依次获取状态队列S中的元素s，即在状态队列S中存在的状态节点，并在获取一个状态节点的同时，将其从状态队列S中删除，例如：

获取q41，删除S中的q41，根据Goto函数和字段串，可以判断得到：G(q41，hook)＝q42，即对应于该状态q41当输入字符串字段为hook时，输出状态节点存在，则设置δ(q41，hook)＝G(q41，hook)＝q42；新生成的状态节点q42，匹配成功关键字S1：mnop hook；对应于该状态q41当输入字符串字段为其它时，由于F(q41)＝q0，所以，不生成δ函数的输出表项，结束。

获取q31，删除S中的q31，根据Goto函数和字段串，可以判断得到：G(q31，mnop)＝q32，则设置δ(q31，mnop)＝G(q31，mnop)＝q32，添加q32到状态队列S中；对应于该状态q31当输入字符串字段为其它时，由于F(q31)＝q0，所以，不生成δ函数的输出表项，结束。

同理可得，获取q21，删除S中的q21，生成δ(q21，ijkl)＝G(q21，ijkl)＝q22，添加q22到状态队列S中；对应于该状态q21当输入字符串字段为其它时，由于F(q21)＝q0，所以，不生成δ函数的输出表项，结束。

同理，获取q11，删除S中的q11，生成δ(q11，efgh)＝G(q11，efgh)＝q12，添加q12到状态队列S中；对应于该状态q11当输入字符串字段为其它时，由于F(q11)＝q0，所以，不生成δ函数的输出表项，结束。

获取q32，删除S中的q32，生成δ(q32，rest)＝G(q32，rest)＝q33，当输出状态为q33时，匹配成功关键字S2：ijkl mnop rest；由于F(q31)＝q41，而δ(q41，hook)＝q42，所以，δ(q32，hook)＝q42，匹配成功关键字S1：mnop hook。

获取q22，删除S中的q22，生成δ(q22，mnop)＝G(q22，mnop)＝q23，添加该q23到状态队列S中。

获取q12，删除S中的q12，生成δ(q12，ijkl)＝G(q12，ijkl)＝q13，添加该q13到状态队列S中；

获取q23，删除S中的q23，生成δ(q23，sina)＝G(q23，sina)＝q24，匹配成功关键字s3：efgh ijlk mnop sina；F(q23)＝q32，所以δ(q23，rest)＝δ(q32，rest)＝q33，匹配成功关键字s2：：ijkl mnop rest；由因为F(q32)＝q41，所以所以δ(q23，hook)＝δ(q41，hook)＝q42，匹配成功关键字S1：mnop hook。

获取q13，删除S中的q13，生成δ(q13，mnop)＝G(q13，mnop)＝q14，添加q14到状态队列S中；

获取q14，删除队列S中的q14，生成δ(q14，qrst)＝G(q14，qrst)＝q15，匹配成功关键字s4：abcd efgh ijlk mnop qrst。由于F(q14)＝q23，所以δ(q14，sina)＝δ(f(q14)，sina)＝δ(q23，sina)＝q24，匹配成功关键字s3：efgh ijlk mnop sina；

又由于F(q23)＝q32，所以δ(q14，rest)＝δ(f(q14)，rest)＝δ(f(q23)，rest)＝δ(q32，rest)＝q33，匹配成功关键字s2：：ijkl mnop rest；又因为F(q32)＝q41，所以δ(q14，hook)＝δ(f(q14)，hook)＝δ(f(q23)，hook)＝δ(f(q32)，hook)＝δ(q41，hook)＝q42，匹配成功关键字S1：mnop hook。

综上，成功获取到δ函数的输出表项，参见图9，为采用本发明实施例提供的技术方案去除Failure链的有向示意图，参见图10，为采用本发明实施例提供的技术方案去除Failure链的状态转移表示意图。

综上，本发明实施例提供的建立模式匹配状态机的方法，可以去除多字节AC算法中的Failure链，优化了存储节约了存储资源，并且提高了处理效率。通过在多字节的AC算法消除其原有的Failure链，连同原有的Goto函数一同转换成一种统一的δ转移函数，在对失效链进行转换的过程中对于会Failure到初始状态的表项不生成，从而不会导致大规模的存储空间的增长，节约了存储空间，同时优化了AC算法的存储结构，简单并固化了AC算法的处理步骤，从而最终提高了AC算法的处理速度。

实施例2

参见图11，本发明实施例提供了一种建立模式匹配状态机的装置，装置包括：

获取模块，用于根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

Goto函数生成模块，用于根据获取模块获取的子关键字字段，生成状态转移Goto函数；

Failure函数生成模块，用于根据Goto函数生成模块生成的Goto函数，生成各状态节点的失效Failure函数；

δ函数生成模块，用于根据Goto函数生成模块生成的Goto函数和Failure函数生成模块生成的Failure函数，生成各状态节点的下一跳状态转移δ函数。

其中，获取模块具体包括：

划分单元，用于按预设字节为单位，对预定义的关键字集合中的关键字进行划分，

第一获取单元，用于根据划分单元的划分得到子关键字字段，

第二获取单元，用于当划分单元的划分关键字时，如果不满足预设字节长度，获取由不满足预设字节长度的字符构成子关键字字段。

其中，δ函数生成模块具体包括：

创建单元，用于创建状态队列S，状态队列初始为空；从起始状态节点q0开始，根据q0的Goto函数和子关键字字段，判断字段串字段对应的Goto函数的输出状态节点是否存在；当输出状态节点存在时，设置字段串字段对应Goto函数的输出状态节点为字段串字段对应δ函数的输出状态节点；并将输出状态节点依次添加到状态队列中；

获取单元，用于根据预设规则，依次获取状态队列中的每一状态节点，当获取一个状态节点时，从状态队列中删除获取的状态节点，并根据获取的状态节点和子关键字字段，生成状态节点对应的δ函数的输出，并将非空的输出状态节点依次添加到状态队列S中直到状态队列为空。其中，该预设规则具体可以为在状态队列S中的状态节点先进先出的规则。

其中，获取单元具体包括：

获取及删除子单元，用于获取状态队列S中的一个状态节点，并删除状态队列中的获取的状态节点；

第一判断子单元，用于根据获取的状态节点和子关键字字段，判断子关键字字段和状态节点对应的Goto函数的输出状态节点是否存在；

第一处理子单元，用于当第一判断子单元判断的结果为否时，则判断状态节点的Failure函数输出是否为初始状态节点q0，如果是，则不建立状态节点的δ函数表项，结束；否则，根据状态节点的Failure函数的输出状态节点和子关键字字段，获取δ函数的输出；

第二处理子单元，用于第一判断子单元判断的结果为是时，将Goto函数的输出状态节点设置为状态节点的δ函数的输出状态节点，并将输出状态节点添加到状态队列。

进一步地，装置还包括：

设置模块，用于如果获取不到以输入状态节点和输入子关键字字段为索引的表项，则设置初始状态节点q0为状态节点的δ函数的输出。

本发明实施例提供的建立模式匹配状态机的装置，可以去除多字节AC算法中的Failure链，优化了存储节约了存储资源，并且提高了处理效率。通过在多字节的AC算法消除其原有的Failure链，连同原有的Goto函数一同转换成一种统一的δ转移函数，在对失效链进行转换的过程中对于会Failure到初始状态的表项不生成，从而不会导致大规模的存储空间的增长，节约了存储空间，同时优化了AC算法的存储结构，简单并固化了AC算法的处理步骤，从而最终提高了AC算法的处理速度。

实施例3

参见图12，本发明实施例提供了一种模式识别的装置，所述装置包括：

模式匹配状态机建立模块，用于根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；根据子关键字字段，生成状态转移Goto函数；并根据Goto函数，生成各状态节点的失效Failure函数；根据Goto函数和Failure函数，生成各状态节点的下一跳状态转移δ函数。

处理模块，用于根据模式匹配状态机建立模块建立的δ函数，根据δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和子关键字字段为索引的δ函数的表项，则设置初始状态节点q0为输入状态节点的δ函数的输入状态，根据新的输入状态和子关键字字段执行δ函数；如果在初始状态节点q0无法获取到子关键字字段的匹配，则设置q0为输出状态。

本发明实施例提供的模式识别的装置，可以去除多字节AC算法中的Failure链，优化了存储节约了存储资源，并且提高了处理效率。通过在多字节的AC算法消除其原有的Failure链，连同原有的Goto函数一同转换成一种统一的δ转移函数，在对失效链进行转换的过程中对于会Failure到初始状态的表项不生成，从而不会导致大规模的存储空间的增长，节约了存储空间，同时优化了AC算法的存储结构，简单并固化了AC算法的处理步骤，从而最终提高了AC算法的处理速度。

通过本发明实施例所提供的技术方案，可以在通信等领域进行广泛，如可用于移动网的内容计费，也可应用于固定网的按业务QoS分配中等等。

本发明实施例中的部分步骤，可以利用软件实现，相应的软件程序可以存储在可读取的存储介质中，如光盘或硬盘等。

以上所述仅为本发明的具体实施例，并不用以限制本发明，对于本技术领域的普通技术人员来说，凡在不脱离本发明原理的前提下，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (14)

1.一种建立模式匹配状态机的方法，其特征在于，所述方法包括：

根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；

根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

2.如权利要求1所述的建立模式匹配状态机的方法，其特征在于，所述根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段，具体为：

按预设字节为单位，对所述预定义的关键字集合中的关键字进行划分，得到子关键字字段，其中，对所述关键字划分时，如果不满足所述预设字节的长度，所述不满足所述预设字节长度的字符构成子关键字字段。

3.如权利要求1所述的建立模式匹配状态机的方法，其特征在于，所述根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数，具体为：

依次获取状态队列S中的每一个状态节点，当获取每一个状态节点时，从所述状态队列S中删除所述获取的状态节点，并根据所述获取的状态节点和所述子关键字字段，生成所述状态节点对应的下一跳状态转移δ函数的输出。

4.如权利要求3所述的建立模式匹配状态机的方法，其特征在于，所述根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数，具体为：

创建状态队列S，所述状态队列初始为空；

从起始状态节点q0开始，根据所述q0的Goto函数和所述子关键字字段，判断所述子关键字字段对应的Goto函数的输出状态节点是否存在；当所述输出状态节点存在时，设置所述子关键字字段对应Goto函数的输出状态节点为所述子关键字字段对应δ函数的输出状态节点；并将所述非q0的输出状态节点依次添加到所述状态队列S中；

按照预设规则，依次获取所述状态队列中的每一个状态节点，当获取一个状态节点时，从所述状态队列中删除所述获取的状态节点，并根据所述获取的状态节点和所述子关键字字段，生成所述状态节点对应的δ函数的输出，并将所述非空的输出状态节点依次添加到所述状态队列S中；

直到所述状态队列为空。

5.如权利要求4所述的建立模式匹配状态机的方法，其特征在于，所述根据所述获取的状态节点和所述子关键字字段，生成所述状态节点对应的δ函数，具体为：

根据获取的所述状态节点和所述子关键字字段，判断所述子关键字字段和所述状态节点对应的Goto函数的输出状态节点是否存在；

如果所述Goto函数的输出状态节点不存在，则判断所述状态节点的Failure函数输出是否为初始状态节点q0，如果是，则不建立所述状态节点的δ函数输出表项，结束；否则，根据所述状态节点的Failure函数的输出状态节点和所述子关键字字段，获取所述状态节点的δ函数的输出；

如果所述Goto函数的输出状态节点存在，将所述Goto函数的输出状态节点设置为所述状态节点的δ函数的输出，并将所述δ函数的输出状态节点添加到所述状态队列。

6.如权利要求5所述的建立模式匹配状态机的方法，其特征在于，所述根据所述输出状态节点的Failure函数的输出状态节点和所述子关键字字段，获取所述δ函数的输出，具体为：

将所述状态节点的Failure函数的输出状态节点和所述子关键字字段做为δ函数的输入，生成所述Failure函数的输出状态节点的δ函数的输出，其中，当所述δ函数的输出不存在，则不建立所述状态节点的δ函数输出表项，结束。

7.如权要要求3所述的建立模式匹配状态机的方法，其特征在于，所述预设规则具体为按照所述状态队列S中的状态节点先进先出的规则。

8.一种模式识别的方法，其特征在于，所述方法包括：

根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；

根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

根据所述δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和所述子关键字字段为索引的δ函数的表项，则设置所述初始状态节点q0为所述输入状态节点的δ函数的输入状态，根据所述新的输入状态和所述子关键字字段执行δ函数；如果在初始状态节点q0无法获取到所述子关键字字段的匹配，则设置所述q0为输出状态。

9.一种建立模式匹配状态机的装置，其特征在于，所述装置包括：

获取模块，用于根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；

Goto函数生成模块，用于根据所述获取模块获取的子关键字字段，生成状态转移Goto函数；

Failure函数生成模块，用于根据所述Goto函数生成模块生成的Goto函数，生成所述各状态节点的失效Failure函数；

δ函数生成模块，用于根据所述Goto函数生成模块生成的Goto函数和所述Failure函数生成模块生成的Failure函数，生成各状态节点的下一跳状态转移δ函数。

10.如权利要求9所述的建立模式匹配状态机的装置，其特征在于，所述获取模块具体包括：

划分单元，用于按预设字节为单位，对所述预定义的关键字集合中的关键字进行划分，

第一获取单元，用于根据所述划分单元的划分得到子关键字字段，

第二获取单元，用于当所述划分单元的划分所述关键字时，如果不满足所述预设字节长度，获取由所述不满足所述预设字节长度的字符构成子关键字字段。

11.如权利要求9所述的建立模式匹配状态机的装置，其特征在于，所述δ函数生成模块具体包括：

创建单元，用于创建状态队列S，所述状态队列初始为空；从起始状态节点q0开始，根据所述q0的Goto函数和所述子关键字字段，判断所述字段串字段对应的Goto函数的输出状态节点是否存在；当所述输出状态节点存在时，设置所述字段串字段对应Goto函数的输出状态节点为所述字段串字段对应δ函数的输出状态节点；并将所述非q0输出状态节点依次添加到所述状态队列中；

获取单元，用于根据预设规则，依次获取所述状态队列中的每一状态节点，当获取一个状态节点时，从所述状态队列中删除所述获取的状态节点，并根据所述获取的状态节点和所述子关键字字段，生成所述状态节点对应的δ函数的输出，并将所述非空的输出状态节点依次添加到所述状态队列S中直到所述状态队列为空。

12.如权利要求11所述的建立模式匹配状态机的装置，其特征在于，所述获取单元具体包括：

获取及删除子单元，用于获取所述状态队列S中的一个状态节点，并删除所述状态队列中的所述获取的状态节点；

第一判断子单元，用于根据获取的所述状态节点和所述子关键字字段，判断所述子关键字字段和所述状态节点对应的Goto函数的输出状态节点是否存在；

第一处理子单元，用于当所述第一判断子单元判断的结果为否时，则判断所述状态节点的Failure函数输出是否为初始状态节点q0，如果是，则不建立所述状态节点的δ函数表项，结束；否则，根据所述状态节点的Failure函数的输出状态节点和所述子关键字字段，获取所述δ函数的输出；

第二处理子单元，用于所述第一判断子单元判断的结果为是时，将所述Goto函数的输出状态节点设置为所述状态节点的δ函数的输出状态节点，并将所述输出状态节点添加到所述状态队列。

13.如权利要求9所述的建立模式匹配状态机的装置，其特征在于，所述装置还包括：

设置模块，用于如果获取不到以输入状态节点和输入子关键字字段为索引的表项，则设置所述初始状态节点q0为所述状态节点的δ函数的输出。

14.一种模式识别的装置，其特征在于，所述装置包括：

模式匹配状态机建立模块，用于根据预设规则，划分预定义的关键字集合中的关键字，获取划分后得到的子关键字字段；根据所述子关键字字段，生成状态转移Goto函数；并根据所述Goto函数，生成所述各状态节点的失效Failure函数；根据所述Goto函数和所述Failure函数，生成各状态节点的下一跳状态转移δ函数。

处理模块，用于根据所述模式匹配状态机建立模块建立的δ函数，根据所述δ函数执行子关键字段的模式匹配，如果在非初始状态节点q0下无法获取到以状态节点和所述子关键字字段为索引的δ函数的表项，则设置所述初始状态节点q0为所述输入状态节点的δ函数的输入状态，根据所述新的输入状态和所述子关键字字段执行δ函数；如果在初始状态节点q0无法获取到所述子关键字字段的匹配，则设置所述q0为输出状态。

Images