利用改进的Wu－Manber算法进行多模式串匹配的方法

摘要

本发明提供一种利用改进的Wu－Manber算法进行多模式串匹配的方法，包括以下步骤：1)预处理模式串：依照某个方式对每个模式串进行HASH处理，计算每个HASH值对应的移动距离；对于HASH到同一个值的多个模式串，采用AVL树存储，以加快匹配速度；2)搜索：每次读取一块字符，并计算其HASH值，取该HASH值对应的移动距离，如果距离大于0，则直接移动比较窗口继续搜索，否则在该HASH值对应的AVL树中搜索，在AVL树中搜索完成后移动比较窗口继续搜索。由此，本发明增大了移动距离，显著加快了匹配过程。

说明书

技术领域

本发明涉及一种多模式串匹配算法的改进，尤其涉及利用改进的Wu-Manber算法进行多模式串匹配的方法，属于算法技术领域。

背景技术

模式串匹配从来都是一个热门话题，从编辑器到生物科学，再到网络内容分析，应用领域非常广泛。这些应用领域的共同特点是需要处理的数据量巨大，需要匹配的关键词条目多而且可能很长，但对性能要求较高。为此相应的模式串匹配算法层出不穷，应用于单模式串匹配的有KMP、BM等等，应用于多模式串匹配的有AC、Wu-Manber等等。

先明确下模式串匹配问题的数学定义：字符，抽象的实体，匹配的最小单位，字母和数字均可为符号；字母表，若干个字符的有穷集合；字符串，取自某个字母表中的并置起来的有穷符号序列。串匹配问题可以精确叙述如下：字母表∑，令其上的n(n＞＝1)个字符串p₁，p₂，...，p_n作为模式串，给定一个字符串T，查找T中是否包含有p_i(1＜＝i＜＝n)。

由于Wu-Manber算法为BM算法的多模式扩展，以下均简单介绍：

BM(Boyer-Moore)：单模式串匹配算法，采用从右到左的方法扫描模式串，是应用中最有效的单模式串匹配算法。该算法思想为，将模式串和被比较字符串沿左侧对齐，从模式串的最后一个字符开始比较，当比较到某个字符不相等时，将比较窗口向右移动；移动的距离在预处理模式串时生成，包括良好后缀转移和不良字符转移。

Wu-Manber：多模式串匹配算法，为BM的多模式扩展，同样采用从右到左的方法扫描模式串，计算移动距离时仅利用BM中的不良字符转移，同时该算法又利用了hash的思想减小匹配范围。由于模式串众多，在读取被比较字符串时，采取读入多个字符的方法，即一次读入一块字符。

发明内容

本发明的目的是克服现有技术存在的不足，提供一种利用改进的Wu-Manber算法进行多模式串匹配的方法，旨在有效加速Wu-Manber算法的匹配过程。

利用改进的Wu-Manber算法进行多模式串匹配的方法，包含以下步骤：

1)预处理模式串：计算每个模式串对应的SHIFT数组，并将该串插入对应的链表或AVL树；

a)计算SHIFT数组：模式串P，只考虑P的前lmin个字符，每B个字符为一块，计算HASH值，设该HASH值对应的移动距离s1，该字符块到模式串末端的距离为s2，则该HASH值对应的移动距离重新置为s1和s2的最小值；计算P末端的B个字符的HASH值，将该HASH值对应的移动距离最高位置1；

b)模式串插入：模式串P，只考虑前lmin个字符，计算P的后B个字符的HASH值，若其对应的模式串个数小于给定值N，则插入模式串链表，否则计算P的前B个字符的HASH值，以此为关键字插入对应的AVL树；

2)搜索：比较窗口长度为lmin个字符，在当前比较窗口下，计算后B个字符块的HASH值，取对应的移动距离shift，若最高位不为1，则直接将比较窗口向右移动shift，否则取该HASH值对应的链表或AVL树，在其中搜索，然后将比较窗口向右移动，移动距离为将最高位清0的shift。

进一步地，上述的利用改进的Wu-Manber算法进行多模式串匹配的方法，利用专门的变量存储移动距离为0的hash值，即重新定义一个数组ZERO，当ZERO为1时，表示该hash值对应的块字符为某个模式串的后缀，而SHIFT数组定义为下一次的移动距离，绝对大于0；在搜索过程中，先判断ZERO[hash]是否为1，如果是则进行深层次的匹配，下一次移动距离始终为SHIFT[hash]。

更进一步地，上述的利用改进的Wu-Manber算法进行多模式串匹配的方法，利用模式串的前缀产生hash值，同时以该hash值为关键字构造一个AVL树，将模式串作为数据插入到AVL树的相应结点中；搜索时，首先在AVL树中查找，是否有相应的hash值存在，如果没有直接移动比较窗口，否则在该AVL结点中搜索。

本发明技术方案突出的实质性特点和显著的进步主要体现在：

①在原始的Wu-Manber算法中，如果当前字符块的移动距离为0，则下一次移动距离始终为1，本发明显著增大了此处的移动距离，加快了匹配速度，而且没有增加算法的时间和空间开销；

②将HASH到同一个值的多个模式串以AVL树方式存储，由于AVL树的搜索时间复杂度为O(log_n)，n为结点个数，因此本发明采用AVL树大大加快了匹配过程。

附图说明

下面结合附图对本发明技术方案作进一步说明：

图1：预处理流程图；

图2：模式串计算shift数组的示意图；

图3：模式串插入到AVL树或链表的示意图；

图4：搜索流程图。

具体实施方式

本发明为Wu-Manber算法的改进，因此先说明原始的Wu-Manber算法，以下是一些术语和匹配流程：

lmin：模式串的最小长度，实际上移动距离及相应HASH值只和模式串的前lmin个字符相关；

B：一次读入的字符个数；

h1，h2：所用的HASH函数，输入为一块字符，输出为一个整数值；

SHIFT：移动数组，HASH所对应的移动距离；

HASH：链表数组，表示后缀hash值相同的模式串链表；

T＝t₁t₂...t_n：被比较字符串；

P＝{p¹，p²，...，p^r}：模式串；

(一)原始的Wu-Manber算法：

Wu-Manber算法在计算hash值时，只考虑前lmin个字符，即认为所有模式串都是等长的(lmin)。在扫描被比较字符串时，读入一块字符，计算其hash值，得到相应的移动距离shift，如果shift＞0，则直接将比较窗口向右移动shift；如果shift＝0，则表明该后缀有可能存在于某个模式串中，找到对应的链表(该链表包含所有后缀hash值相同的模式串)，遍历其中所有模式串，并提前比较前B个字符的hash值，防止过多的比较运算。

移动数组SHIFT如下生成：

一块字符B_i，如果在所有模式串中都不出现，则该B_i对应的hash值的移动距离为lmin-B+1；如果这块字符存在于某个(或多个)模式串，则找到B_i在模式串中最靠右的位置j及对应的模式串P_i，则移动距离为lmin-B+1-j

以下是Wu-Manber的伪码表示：

Wu-Manber(P＝{p¹，p²，...，p^r}，T＝t₁t₂...t_n)

1.  Preprocessing

2.       用lmin-B+1初始化SHIFT数组

3.       For每个模式串P Do

4.                  pos←lmin-B+1

5.                  Whilepos≤lmin-1 Do

6.                  h←h1(P_pos为后缀的B个字符)

7.                  SHIFT[h]←SHIFT[h]和lmin-pos的最小值

8.                  将P加入到链表HASH[h]中；pos←pos+1

9.                  End of while

10.                 End of for

11.

12.  Searching

13.      pos←lmin

14.      While pos≤n Do

15.            i←h₁(t_pos为后缀的B个字符)

16.            If SHIFT[i]＝0 Then

17.             list←HASH[i]

18.             h←h₂(t_pos-lmin+1为前缀的B个字符)

19.                foreach pattern in list Do

20.             If h＝h₂(pattern的前B个字符)Then

21.                            Compare T with this pattern.

22.               End of if

23.            End of foreach

24.              pos←pos+1

25.       Else pos←pos+SHIFT[i]

26.       End of if

27.   End of while

(二)改进的Wu-Manber算法：

伪码的17行和24行，本发明对该算法的改进主要体现在这两行：

1)如果当前shift为0，则下一次的移动距离都为1，此处没有充分利用模式串的有用信息；

2)后缀hash值相同的模式串可能有很多，成百上千个，而此处仅仅是遍历所有的模式串，时间消耗很长。

第一个问题，利用专门的变量来存储移动距离为0的hash值，即重新定义一个数组ZERO，当ZERO(hash)为1时，表示该hash值对应的块字符可能为某个模式串的后缀，而SHIFT数组定义为下一次的移动距离(绝对大于0)。其构造过程如下：

1.  Preprocessing

2.       用lmin-B+1初始化SHIFT数组，用0初始化ZERO数组

3.       For每个模式串P Do

4.            pos←lmin-B+1

5.            While pos≤lmin-2Do

6.            h←h1(P_pos为后缀的B个字符)

7.            SHIFT[h]←SHIFT[h]和lmin-pos的最小值

8.            将P加入到链表HASH[h]中；pos←pos+1

9.            End of while

10.           h←h1(P_pos为后缀的B个字符)

11.           ZERO[h]←l

10.           End of for

在搜索过程中，先判断ZERO[hash]是否为1，如果是则进行深层次的匹配，下一次移动距离始终为SHIFT[hash]。

第二个问题，利用模式串的前缀(前B个字符)产生hash值，同时以该hash值为关键字构造一个AVL树，将模式串作为数据插入到AVL树的相应结点中；搜索时，不需要遍历所有后缀hash值相同的模式串了，首先在AVL树中查找，是否有相应的hash值存在，如果没有直接移动比较窗口，否则在该AVL结点中搜索。

对于预处理模式串：依照某个方式对每个模式串进行HASH处理，计算每个HASH值对应的移动距离；对于HASH到同一个值的多个模式串，采用AVL树存储，以加快匹配速度。

对于搜索：每次读取一块字符，并计算其HASH值，取该HASH值对应的移动距离，如果距离大于0，则直接移动比较窗口继续搜索，否则在该HASH值对应的AVL树中搜索，在AVL树中搜索完成后移动比较窗口继续搜索。

本发明完整过程如下：

1)预处理模式串：计算每个模式串对应的SHIFT数组，并将该串插入对应的链表或AVL树，参见图1；

a)计算SHIFT数组：模式串P，只考虑P的前lmin个字符，每B个字符为一块(先不考虑最后的一块)，计算HASH值，设该HASH值对应的移动距离(不考虑最高位)s1，该字符块到模式串末端(仅lmin个字符长)的距离为s2(s2＞0)，则该HASH值对应的移动距离重新置为s1和s2的最小值；计算P末端的B个字符的HASH值，将该HASH值对应的移动距离最高位置1，参见图2；

b)模式串插入：模式串P(只考虑前lmin个字符)，计算P的后B个字符的HASH值，若其对应的模式串个数小于给定值N，则插入模式串链表，否则计算P的前B个字符的HASH值，以此为关键字插入对应的AVL树，参见图3；

2)搜索：比较窗口长度为lmin个字符，在当前比较窗口下，计算后B个字符块的HASH值，取对应的移动距离shift，若最高位不为1，则直接将比较窗口向右移动shift，否则取该HASH值对应的链表或AVL树，在其中搜索，然后将比较窗口向右移动，移动距离为将最高位清0的shift，参见图4。

由上可见，本发明方法相当于以空间换取时间，多定义了一个ZERO数组来达到加速匹配的目的。但事实上，ZERO数组只用到0和1两个值，完全可以用一个bit来表示，为此将ZERO数组并入SHIFT数组，当shift＝SHIFT[hash]时，shift的最高位存储的是ZERO的信息，即如果最高位为0，则直接移动比较窗口，否则进行深层次的比较。

将后缀对应hash值相同的模式串，依据前缀对应的hash值为关键字创建一个AVL树，由于AVL树的搜索时间复杂度为O(log_n)，因此可以大大加快匹配速度。但是由于AVL树同样占用空间，需要在时间和空间上作权衡，做法是，当如此的模式串个数小于某个给定值(比如为2)时，不生成AVL树，直接用链表存储，只有个数大于等于给定值时才构造AVL树。

综上所述，利用专门的变量表示某个HASH值对应的移动距离是否为0，而移动距离则重新定义为下一次比较窗口的移动距离，该数值绝对大于0；对比Wu-Manber算法，它在移动距离为0时，下一次的移动距离始终为1，因此本发明增大了移动距离，显著加快了匹配过程。将HASH到同一个值的多个模式串以AVL树方式存储，由于AVL树的搜索时间复杂度为O(log_n)，n为结点个数，因此本发明采用AVL树大大加快了匹配过程。

以上仅是本发明的具体应用范例，对本发明的保护范围不构成任何限制。凡采用等同变换或者等效替换而形成的技术方案，均落在本发明权利保护范围之内。