徐政超

摘 要：研究了BM字符串匹配的算法，并提出了改进算法。借助这些算法的优点，可以判断结束字符、相邻字符的存在和唯一性，或者字符串不合理的字符。这些判断结果增加了新的移动距离，减少了匹配的次数，并提高了字符串匹配的效率，对模式识别的高效发展具有深远的意义和价值。

关键词：BM算法；模式匹配；字符匹配；字符串

中图分类号：G354 文献标识码：A DOI：10.15913/j.cnki.kjycx.2017.06.059

1 BM算法概述

在计算机科学中，Boyer-Moore字符串搜索算法是一种高效的字符串搜索算法，是实际字符串搜索文献的标准基准，它是由Robert S. Boyer和J Strother Moore在1977年开发的。算法预处理搜索字符串，但不处理正在搜索的字符，因此，它非常适合于其中模式比文本短得多或在多个搜索中持续存在的应用程序。Boyer-Moore算法使用在预处理步骤期间收集的信息来跳过文本的部分，导致比许多其他字符串搜索算法具有更低的常数因子。

2 BM算法的原理

Boyer-Moore算法通过在不同比对中执行显式字符比较来搜索P在T中的出现，而不是对所有对齐的暴力搜索。Boyer-Moore使用通过预处理P获得的信息跳过尽可能多的对齐。在引入这个算法之前，在文本内搜索的常用方式是检查文本每个字符模式的第一个字符。一旦发现相同，文本的后续字符将与模式的字符进行比较。如果没有匹配，则再次逐个字符检查文本，以便找到匹配。因此，文本中几乎每个字符都需要检查。该算法的关键点是，如果将模式的结束与文本相比较，则可以沿着文本跳跃而不是检查文本的每个字符。这样做的原因是，在将模式与文本对齐时，将模式的最后一个字符与文本中的字符进行比较。如果字符不匹配，则无需继续沿着模式向后搜索。如果文本中的字符与模式中的任何字符不匹配，则要检查的文本中的下一个字符沿着文本位于更远的n个字符，其中，n是模式的长度。如果文本中的字符在模式中，则沿着文本进行模式的部分移位，以沿匹配字符排列，并且重复该过程。沿着文本跳跃以进行比较而不是检查文本中的每个字符，减少了必须比较的数量。这是算法效率的关键。更正式地，算法从对齐{k＝n}开始，因此P的开始与T的开始对齐。然后，P和T中的字符从P中的索引n和T中的k开始，向后移动。字符串从P的结尾到P的开始匹配。比较继续，直到达到P的开始或者发生不匹配，其中对齐向前移动（向右）根据多个规则允许的最大值。在新对准时再次执行比较，并且重复该过程，直到对准被移位经过T的结束。这意味着找不到进一步的匹配。移位规则被实现为使用在P预处理期间生成的表进行常数查找。

一个简单但重要的优化Boyer-Moore是由Galil在1979年提出的。与移位相反，Galil规则通过跳过已知匹配的部分来加速在每个对齐处进行的实际比较。假设对齐k1、P与T下降到T的字符c，如果P被移位到k2，使得其左端在c和k1之间，则在下一比较阶段中，P的前缀必须匹配子串T[（k2－n）…k1]。因此，如果比较向下到达T的位置k1，则可以记录P的发生而不明确比较过去的k1。除了提高Boyer-Moore的效率之外，Galil规则可以在最差的情况下利用线性时间执行。

3 BM算法的改进

3.1 末字符不匹配

模式串字符与正文串字符从右向左匹配时，如果串末字符与正文串对应字符不匹配，不是查看模式串串末字符对应正文串字符的后继字符是否在模式串中，而是查看与模式串串末字符对应的正文串中字符的后继字符是否为模式串串首字符。

3.2 后缀匹配

当模式串字符与正文串字符从右向左匹配时，有部分匹配后，匹配如下：查看模式串的末字符对应正文串中字符的后继字符是否在模式串中，查看后缀是否存在仅出现一次的字符。

算法实现中包括以下2个步骤。

3.2.1 预处理

计算字符集中每个字符在模式串P中首次出现的位置，如果不存在，则为-1；如果存在，则记录其位置。计算模式串P＝{P[0]，P[1]，…，P[m]}中每个字符首次出现的位置first[P[i]]（i为0～m），计算模式串中每个字符在模式串中出现的次数。

3.2.2 匹配过程

匹配过程如下：①初始化。定义变量tlen、plen表示模式串和正文串的长度，定义变量num用于统计在模式串中出现不只一次的字符个数，定义循环变量i则用于进行正文串与模式串的起始位置对齐，定义循环变量j用于模式串字符的匹配。②判断i的值。如果i＞tlen－plen＋1，则失败退出；否则，初始化j＝m，max＝0，onlyOne＝0.③循环②，直到T[i＋j]与P[j]不相等。④判断j的值。如果j＝-1，则匹配成功，返回i值。⑤如果onlyOne≥1，即已匹配好的字符仅出现一次的个数存在。如果有，则i＝i＋max＋1，返回②；否则，继续⑥。⑥判断num－onlyOne是否大于0，即判断还未进行比较的模式串前部分是否存在模式串中仅出现一次的字符。⑦判断坏字符T[i＋j]的前驱后继字符以及T[i＋m]的前驱是否在P[j]与P[m]的相应位置上，并根据其位置移动，返回②。

4 总结与展望

古典字符串匹配算法的本质是顺序字符匹配，它总是从左到右或从右到左。在主字符串中，如果有许多子串具有与模式字符串相同的前缀或后缀，则算法效率低。移位的最大长度是模式字符串的长度。改进后的算法使用两串分离比较方法，有效地节省了由于子串和模式串的相同前缀或后缀的无意义的比较时间。在改进的版本中，不执行前缀移位，改善坏字符移位功能，还修改Goto过程，其不保持好的前綴移位和坏字符移位的参数。由于算法根据改进的不良字符规则计算模式串的移动距离，因此增加了模式串的移动距离。实验结果表明，改进的字符串匹配算法可以有效地减少字符串匹配次数和移动次数来改进算法，有利于提高模式识别的效率。

参考文献

［1］王天聪，侯整风，何玲.基于BM的模式匹配改进算法［J］.合肥工业大学学报（自然科学版），2011（03）.