一种快速的多模式匹配算法

 一．摘要

本文将给出一个简单但非常有效率的多模式匹配算法，这个算法基于压缩编码的思想。该算法在自左向右扫描文本的过程中，根据出现在输入模式中的字符将文本中的字符进行编码。这个简单的扫描算法展示了同时处理大量的输入模式的能力。我们的实验表明，在大多数情况下，我们的算法比当前的多模式匹配算法(比如agrep, grep）有更快的执行速度。

二．介绍
字符串的多模式匹配问题是要在给定的文本T 中找出输入模式集合
P(1）……P(N）中所有出现了的模式。一种最直接的方法是将每一个模式都与文本T 进行一次匹配，但是这样的话，需要对文本T 进行N 次扫描和匹配。很显然，我们可以设计出更好的解决方案。如果能只对文本T 进行一次扫描和匹配就完成对所有模式的搜索过程，而不论有多少输入模式，这样的方法是非常令人满意的。在文献[1，5，6，13]中可以找到大量的对多模式匹配的研究。当前的一些算法能做到只对文本T 进行一次扫描就寻找到输入模式集合中所有在T 中出现了的模式，而不论输入模式集合的数量有多大。比如，Wu 和Manber 的算法[13]在Sun Sparc 10 工作站环境下，用大约10 秒的时间就能完成在15.8M 的文本中寻找10000 个输入模式的工作。
由于多模式匹配算法非常有效率，所以现在字符串的多模式匹配技术在许多应用领域都得到了应用。Wu 和Manber 在他们的字符串多模式匹配算法的基础上，给出了一个相当有效的对模式进行模糊匹配的软件AGREP 和一个文本搜索工具GLIMPSE。
我们将在下面给出一个非常有效率的字符串多模式匹配的算法，这个算法利用了压缩编码和散列的思想和技术。当我们在文本中查找一个模式的时候，最直接的想法就是将模式中的字符和文本中的字符进行比较。象非常有名的KMP 算法和BM 算法这样的字符串模式匹配算法就是基于字符比较的。然而，在比较字符的技术路线之外，还存在着另外一些寻找匹配的技术，比如说“半数值(seminumerical）”技术。之中类型的算法用一些位串分别表示模式和文本，通过对这些位串进行位操作，从而完成匹配的过程。
将文本和模式用位串表示，使我们同时将文本和许多模式进行匹配，并且快速有效地寻找到匹配的模式。我们利用压缩编码的思想和技术将模式和文本转化为位串，然后在这个基础上提出我们的字符串多模式匹配算法。
在下面的几小节中，我们将首先介绍压缩编码的思想，然后我们将在第四部分中介绍一个结合了压缩编码和散列的思想和技术的字符串的多模式匹配算法，在第五部分中我们将给出一些实验的数据，最后，在接下来的第六部分中，我们将对算法做一些深入的讨论。
三．对模式和文本压缩编码

在这一节，我们将介绍如何对模式和文本进行压缩编码。对文本和模式压缩编码的好处就是在我们进行一次位操作的同时，我们就可以完成许多字符的比较工作。
首先，我们从最简单的情况入手，考虑只含有四个字符A, T, G 和C 的
DNA 序列。因为只使用了四个字符的字符集，所以我们可以对每一个字符进行如下的编码 ：A——00， T——01， G——10， C——11。下面的例子说明了一个DNA 模式和一个DNA 序列是怎样按照这种编码规则被进行编码的。
例1 ． 考虑DNA 模式 P = GATCA 和DNA 序列S =GTACGATCAGAC。我们可以将P 编码为：10 00 01 11 00，将S 编码为：10 01 00 11 10 00 01 11 00 10 00 11，用这样的位串来表示P 和S。
现在我们将这个编码的思想推广到一般的情况。对于一个给顶的模式P
和文本T，我们首先对P 中出现的不同的字符进行记数。令D 为P 中不同的字符的个数，E 为一个整数，并且满足下面的条件：2∑ >= (D+1）。然后我们就可将P 和T 中的任一个符号编码为E 位的位串，对于T 中没有在P 中出现的字符，我们一律编码为E 个0。
例2．考虑模式P = encoding 和 文本T = “ Compact encoding can”。
因为在P 中共有7 个不同的字符，所以对每个字符我们可以用3 位位串进行编码(23 = 8 >= 7+1）。我们用一个函数ENCODE 对每一个字符进行编码。ENCODE(e）= 001，ENCODE(n）= 010， ENCODE(c）= 011，ENCODE(o）= 100， ENCODE(d）= 101， ENCODE(i）= 110，
ENCODE(g）= 111，再加上ENCODE(—）= 000，其中—表示没有在P
中出现的所有字符。于是，我们可以得到P 的编码为 ：001 010 011 100 101110 010 111，T 的编码为：000 100 000 000 000 011 000 000 001 010011 100 101 110 010 111 000 011 010。
压缩编码的思想可以总结如下：
1． 扫描模式P，确定将用于编码的位数E。
2． 为每一个在P 中出现的字符定义编码函数ENCODE，对没在P中出现的字符，ENCODE 的值为E 个0。
3． 利用ENCODE 函数对P 和T 中每一个字符进行编码。
四．一种新的字符串多模式匹配算法
由于模式和文本都被压缩成了位串，剩下的问题就是如何在寄存器或机器字中存放这些位串以及如何在文本中查找模式。考虑最简单的情况，我们假设模式压缩编码后的位串能够存放在一个机器字中寻找单模式：一个模式能够通过重复进行简单的移位运算和逻辑或运算
存储在一个机器字中。下面的例子展示了我们如何将一个模式存放在一个机器字中。
例3：为了将模式encoding 压缩编码后的位串存放在机器字中，我们先
将一个机器字长的long int 变量W 初始化为0。在例2 中我们看到，模式
中的每一个字符都可以编码为3 个位的位串。所以我们
1． 对W和ENCODE(e）= 001， 进行逻辑或运算。
2． 将W 左移3 位，然后将W 与ENCODE(n）= 010 进行逻辑或运算。
3． 重复执行第2 步，直到模式的最后一个字符被处理。
经过这个处理过程， 我们最后得到的W 为：
00000000001010011100101110010111，其中低24 位就是模式encoding 经压缩编码后的位串。
为了在文本的位串中进行扫描和匹配，我们利用另一个变量T，在从
左至右地扫描文本的过程中，通过上述的处理过程，将文本中的每一个字符编码。为了确定模式是否在文本T 中出现，对于每一个模式，我们还需要一个机器字长的掩码PMASK。如果模式P 编码后有p 位长，那么我们将PMASK 的低p 位每一位都设为1，而将其他的位都设为0。比如说，对于例3 中的模式P=encoding 来说， 它的掩码PMASK 为：00000000111111111111111111111111。PMASK 的作用是将T 中不和模式对应的部分的信息抹掉。对于代表文本的机器字变量T，表示模式的机器字变量P，和P 对应的掩码PMASK，通过两个简单的位操作就可以确定模式是否在文本中出现：
1． 对T 和PMASK 进行逻辑与操作。
2． 对第一步的结果和P 进行逻辑异或操作。
3． 检查第二步的结果是否为0，如果为0，那么可以确定模式在文本中出现了，如果不为0，那么模式没有出现。
下面的例子展示了怎样通过位操作确定模式是否在文本中出现。
例4：考虑例2 中模式的P = encoding 和文本T = Compact encodingcan… 。我们已经知道， P 经压缩编码后的位串为
00000000001010011100101110010111 ， 它的掩码为
00000000111111111111111111111111。在从左到右扫描文本的过程中，我们不断地更新变量T 并使用它来判断匹配情况。
情况1：开始扫描文本时，根据P 的长度，我们从第一个空白字符(t
后边的那个）的位置开始扫描。这时
T = 00000000000100000000000011000000
(T & PMASK）
= 00000000000100000000000011000000
((T & PMASK）^ P）
= 00000000001110011100101101010111
因为结果不是每一位都为0，所以我们可以确定，模式没有在当前位置
出现情况2：当文本中的字符g 被扫描到的时候，这时：
T = 11000000001010011100101110010111
(T & PMASK）
= 00000000001010011100101110010111
((T & PMASK） ^ P）
= 00000000000000000000000000000000
由于最后的结果为0，所以我们可以确定，模式在文本的当前位置出现
了。
寻找多模式：现在我们考虑输入模式为多模式P(1）…P(N）的情况。通过为每一个模式P(i）配置一个单独的掩码，我们可以很简单地将寻找单模式的算法扩展到寻找多模式的情况。为了寻找P(i）的所有可能的出现位置，我们应该对每一个P(i）都进行上面寻找单模式时的位操作。很显然，这样做的缺点是将会无谓地消耗大量的时间，尤其是模式的数量增加时，这种消耗也会随之增加。为了能避免不必要的位操作，我们建立一个大小位H 位所表示的整数的散列表。我们根据每一个模式的低H 位将模式放到散列表的适当的位置。这样，在实际的处理过程中，我们只需要对文本变量T 的低H 位所对应的散列表的入口中存放的模式进行位操作，以确定这个或这些模式是否在文本中出现。
假设S 位最短输入模式位串的长度。我们可以将H 设位任意小于S 的
数，当然，这还需要取决于我们系统的内存。需要注意的是，H 一定不能大于S。因为我们采用了压缩编码的技术，越大的H 值就可能越有效地避免不必要的位操作。举个例子，假设E(每一个字符的编码长度）为3，H 为15。那么我们将使用32K 内存( 15 2 ）。因为有五个字符(15 bits = 3 bits *5）被用来进行过滤以避免不必要的位操作，可以想象，大量不必要的位操作都将被避免。
为了利用散列技术，我们需要引入另一个掩码HMASK，这个掩码的低
H 位全部位1，而其余各位都位0。对于文本变量T，我们将THMASK
进行逻辑与运算，检验得到的结果所指示的HASH 表中位置是否为空，如果为空，我们就可以不进行任何的位操作了，如果不为空，位于HASH 表中这个位置的所有模式都将与T 进行位操作，以判断是否匹配。
多模式字符串的匹配算法可以总结如下，随后我们还给出了一段该算法的C 代码。
1． 扫描所有的输入模式，确定每个字符的编码位数E，并且定义编
码函数ENCODE。
2． 对每一个模式P(i）进行编码，同时设置与其相对应的掩码PMASK
(i）。
3． 根据散列表的大小设置HMASK 的位。
4． 将文本变量T 初始化为0。
5． 将T 左移E 位，开始对文本的扫描。每扫描一个字符后，对T 和
HMASK 进行逻辑与运算，得到的结果是散列表的入口，如果这个入口中内容为空，那么不进行比较，扫描下一个字符；如果不为空，将这个入口中的所有模式与T 进行前面所描述的位操作，以确定是否匹配。
五．实验测评
为了评测我们的算法，MULTI1，我们将我们的算法和grep 以及agrep
两个多模式匹配的工具进行对比实验，我们的工作环境是SUN Ultra 10 工作站(333MHz 处理器），内存大小为128M。MULTI1 使用了1M 内存作为其散列表的入口。所有测试得到的时间数据都是用Unix 的time 命令得到。
我们用两组不同的测试集做了两个不同的实验。一个测试集是从Gutenberg项目中获得的King James Bible(4441849 字符），而另一个测试集是一个巨大的DNA 序列文件(18617116 字符）。
英文模式匹配测试：我们准备了N 个模式，这N 个模式是从Unix 字典
中随机抽取出来的。分别用MULTI1，agrep 和grep 进行搜索和匹配。我们使用的实际文本是将King James Bible 拷贝两份和原来的文本连接起来获得的，所以字符数为13325547。这是因为这些字符串匹配算法的速度都非常的快，要测量对4M 文本进行搜索和匹配的可靠时间是很困难的。我们获得的结果如下：
对于grep，当模式的数量超过200 时，我们没有得到它的运行时间，
因为它将运行太长的时间。正如你所看见的，当模式的数量大于100 时，MULTI1 的运行速度将比agrep 快。但是，这个结果并不意味着我们的算法要比当前的算法(比如agrep）更快，因为对模式的搜索和匹配的速度受到哈尔滨工业大学毕业设计(论文）
49
模式结构和文本结构的限制。在分析算法执行速度的时候，另一个我们需要考虑的因素是模式集合中最短模式的长度。因为agrep 和grep 都采用了跳跃的技术(Boyer-Moore 跳跃技术），而MULTI1 却没有采用这种技术。当模式数量为10 而模式集合中最短模式的长度为6 时，agrep 只用了0.3 秒就完成了匹配，而MULTI1 却花了1.6 秒才完成了匹配，正如我们所预期的，当模式集合中最短模式的长度越大时，采用跳跃技术的算法将会更有效率。
除了最短关键词长外，还有很多其他因素能影响模式匹配的速度，比如说模式和文本的字符集大小等等。我们将在另一篇文章中给出对于不同结构的输入模式算法的执行效率。
DNA 序列模式测试：在这一节中，我们给出了对一个庞大的DNA 序
列文件的测试结果。DNA 字符和英文字符的最大的不同在于两者字符集的大小不同。DNA 序列的字符集的大小为4，而英文的字符集中包含了很多的文字和数字，比DNA 的字符集大了许多。这个实验展示了各种算法在面对不同大小的字符集时的表现。我们随机地产生了N 个DNA 序列模式，这些模式的长度从10 到32 不等，对于MULTI1，agrep 和grep 三种不同算法的测试结果如下：
当模式的数量超过500 时，象上一次测试一样，我们无法得到grep 的
结果了，因为它的处理时间实在是太长了。正如表中所展示的一样，
MULTI1 几乎在所有的情况下都比grep 的速度得更快。一个有趣的现象
是，MULTI1 对模式数量的增加并不敏感，对于100 个模式，MULTI1 的速度是3.4 秒，而对于10000 个模式，它的速度也才增加到了5.9 秒。另一个有趣的现象是当输入模式的数量增加时，MULTI1 的速度会比agrep 快很多。这是因为通过压缩编码的过程自动地使我们在散列的过程中充分利用DNA 字符集大小为4 这个有利的条件。这展示了我们的算法通过压缩编码和散列的技术同时处理多个模式的能力。
六．讨论
在本文中，我们介绍了一个新的字符串的多模式匹配算法，这个算法基于压缩编码和散列的技术。该算法能够同时处理多个模式，并且实验表明，在大多数情况下，它的运行速度都比grep 和agrep 要快。在别的字符串多模式匹配算法中同样也利用了散列技术来处理大量的模式。比如Wu 和Manber 的算法利用三个表SHIFT, HASH 和PREFIX 来避免不必要的匹配测试。在本文中，散列技术利用了压缩编码技术来自动适应不同的字符集大小，从而获得了更好的运行时效率。
因为我们的算法以来散列技术，减少散列冲突产生的次数可以从根本上改善算法的执行效率。事实上，我们可以根据输入模式的结构采用不同的字符编码技术从而减少散列冲突发生的机会。我们将这种技术称为“自适应字符串模式匹配”以强调字符串模式匹配算法能够适应不同的输入模式结构而优化自身的效率。这种自适应的字符串模式匹配技术已经被成功地用在了各种算法中。在另一篇即将发表的文章中，我们就将介绍一个通过文本切分而利用这种技术的新的字符串模式匹配算法。