BM模式匹配算法的研究和改进

揣锦华，郑 景，关 锐

（长安大学 信息工程学院，陕西 西安 710064）

串的模式匹配是串的一种很重要的运算，它一直都是计算机科学领域研究的焦点问题之一。串的模式匹配在众多领域被广泛的应用，如：拼写检查、搜索引擎、计算机病毒特征码匹配、入侵检测、数据压缩以及DNA序列匹配等，都离不开模式匹配算法。

所谓模式匹配就是在大量的文本串中查找模式串（一个给定的字符串）的一个或者多个匹配的过程。对于文本串为T=T0T1…Tn－1，长度为 n；模式串 P=P0P1…Pm－1，长度为 m。 如果在T中找到P的出现则表示匹配成功，否则匹配失败。

关于模式匹配的算法有很多，比较著名的有2个：KMP算法和Boyer－Moore算法[1]（简称BM算法）。其中 KMP算法实现较为复杂，且效率有限。相比之下，Boyer－Moore算法实现更为简单，且在英文文本及模式较长的情况下，其效率一般是KMP算法的3～5倍，因此其应用更为广泛。

目前对于BM算法的改进算法有很多，但大体上改进都很有限，且稳定性并不尽如人意。下面将会对经典BM算法，以及目前比较流行的两种改进的BM算法进行简单的介绍，然后提出2点改进意见。旨在提升其效率的同时极大的提高其稳定性，最后通过具体的实验进行比较、验证。

1 现有的BM系列算法简介

1.1 经典BM算法

经典 BM（Boyer－Moore）算法[1]的基本思想是：开始时，将文本串T（长度为n）与模式串P（长度为m）左对齐，然后从模式串的最后一个字符Pm－1开始，从右至左依此与文本串的相应字符 Tm－1Tm－2…T0进行比较；当某次比较 Ti与 Pi不匹配时，模式串向右滑动一段距离后 k，开始执行由 Pm－1与 Ti+k－1起，从右至左的匹配检查，依此类推直到找到一个完整匹配或者全文搜索完毕为止。……