对Boyer-Moore模式匹配算法的优化研究

庄 彦 王 勇



对Boyer-Moore模式匹配算法的优化研究

庄 彦 王 勇

（安徽工商职业学院电子信息系，安徽合肥 231131）

在大数据时代，如何运用模式匹配方法加强对相关信息的搜索是当前自然科学和社会科学界都面临的重要问题．通过对经典的模式匹配算法BM算法、BMH算法和BMHS算法的分析和研究，并在此基础上提出了加快匹配速度，缩短比较次数和匹配的时间的改进方法——OBM模式匹配算法．

模式匹配；BM算法；OBM算法

1 引 言

就目前研究开发的情况而言，关于模式匹配的算法有很多，不但有最基本的Boyer-Moore模式匹配算法（简称BM算法），还有在此基础上进行的较多的改进算法，比较著名的有BMH算法和BMHS算法，这两个算法分别是由Horspol（1980）和Sunday（1990）提出和改进的．但是，就这两种算法都存在一定的局限性，不能很好地适用于大数据时代对模式匹配算法的要求．本文在对以上几种经典算法的分析基础上，结合BM模式匹配算法中的坏字符规则以及模式串末字符对应的文本字符与文本字符下一个字符的独特性和组合性，对BM模式匹配算法作了进一步的优化和改进，提出了OBM算法．

2 Boyer-Moore模式匹配算法及其相应的改进算法

2.1 Boyer-Moore模式匹配算法及其主要思想

在众多的查找字符串的算法之中，由美国工程院院士鲍勃·博伊尔和斯特罗瑟·摩尔于1977年提出的被称之为Boyer-Moore模式匹配算法是公认的最为高效的精确字符串匹配算法（有别于模糊字符串匹配算法）之一．由于BM算法的时间复杂度低于线性，所以它当之无愧地成为现今使用最多的一种匹配算法．BM匹配算法主要采用了三种巧妙而有效的方法，包括从右到左扫描、坏字符规则，以及好后缀规则．在解释两种规则之前，先定义文本，其长度为，定义模式字符串，其长度为，且≤．

2.1.1 坏字符规则（Bad Character）

所谓坏字符规则就是指，在从右到左的扫描过程中，如果发现字符T≠P，即T与P不相匹配的时候，如果P是的末字符且T在模式字符串中没有相同字符串，那么下一次的比较就可以将匹配窗口直接移动个位置后继续匹配；如果T在模式字符串中存在相同字符串，那么就可以找到T在模式字符串中存在的相同字符串的最右边的位置（且1≤≤－1），然后下一次比较就可以直接将匹配串口移动到－的位置后继续匹配（见图1）．由此可见，使用从右到左扫描和坏字符规则可以跳跃过中的很多位置不去检查，从而使时间复杂度低于线性．上述两种情况的移动距离，即跳跃函数skip()可以用式子（1）表示．

文本串Tabcecabeabc 字符串Pabcab

（a）发生不相匹配的情形

文本串Tabcecabeabc 字符串Pabcab

（b）坏字符跳跃

图1 坏字符规则的两种定义

2.1.2 好后缀规则（Good Suffix）

所谓好后缀规则就是，指在从右到左的扫描过程中，利用已经匹配好的模式字符串P+1,P+2，…,P-2,P-1,P是否出现在P,P,…P-1,P中，来决定向右移动（shift）的量（见图2），其移动函数shift()可以用式（2）表示，其中表示当前所匹配的字符的位置，为与之间的距离，或与之间的距离．

文本串Tabcecabeabc 字符串Pabcab

（a）已经匹配部分（加粗）没有在中其他地方出现

文本串Tabcecabeabc 字符串Pabcab

文本串Tabcecabeabc 字符串Pabcab

（b）后缀（加粗）与中前缀（加粗）匹配

图2 好后缀规则的两种定义

运用BM模式匹配算法，可以实现文本与模式字符串之间的从右到左的匹配，一旦发现不相匹配的情况，就取好字符跳跃和坏字符跳跃之间的较大值为模式字符串的向右跳跃的距离．BM模式匹配算法完成搜索的时间复杂度为（+）（其中，是模式字符串在文本串中出现的次数），最理想的情况是每次匹配时，模式字符串中，不存在与文本中第一个匹配的字符，这时的时间复杂度为（/）；最不理想的情况是文本中有多个重复的字符，并且模式字符串由－1个相同的字符前加一个不同的字符组成，这时的时间复杂度为（）．

2.2 Boyer-Moore模式匹配算法的改进算法

为了加快BM模式匹配的速度，一些学者对其进行了方法上的改进，使得每次匹配失败后，在保证不丢失匹配成功可能性的前提下，尽可能地向后跳跃．类似的改进有BMH匹配算法和BMHS匹配算法．

2.2.1 BMH匹配算法及其主要思想

1980年，加拿大维多利亚大学计算机科学教授奈吉尔·霍斯普尔（R. Nigel Horspool）在BM算法的基础上提出了一种改良和简化的模式匹配算法，称之为Boyer-Moore-Horspool模式匹配算法（简称BMH算法），它较之于BM算法在匹配时更加容易，只需要使用坏字符跳跃函数skip，并将字符失配与计算模式串右移量独立，无论文本中哪个字符造成了匹配失败，都将依据换字符跳转函数向右移动．

BMH匹配算法的基本思想是：首先，对文本按照从头到尾的顺序和从右到左的匹配顺序进行搜索和匹配（即比较T,T+1,…,T+m-1和0,1,…,P-1），如果发现失配，则哪个字符造成了失配，都将由文本中和模式字符串最后一个位置对应的字符来计算模式字符串向右跳转的距离skip（T+m-1）（跳转函数见式（3）），跳转后再对齐重新匹配；其次，如果文本与模式字符串完全匹配，那么就返回在文本中对应的位置；再次，若是搜索完文本都没有找到完全匹配的位置，那就说明查找失败（见图3）．

文本串Tabdabebeabc 字符串Pabcab 字符串Pabcab

作为BM算法的改进方法，BMH确实对匹配过程进行了优化和简化，并不考虑造成失配的文本串中的某个字符，而是沿用BM算法的坏字符规则，用模式字符串最右端对其的文本字符来计算跳跃的距离，因此，在实际应用中较BM的效率更高了．

2.2.2 BMHS匹配算法及其主要思想

1990年，美国计算机科学教授丹尼尔·桑迪（Daniel M.Sunday）在BMH算法的基础上提出了搜索速度更快的Boyer-Moore-Horspool-Sunday模式匹配算法（简称BMHS算法）．BMHS算法其思想跟BM算法很相似，只不过BMHS算法是从前往后匹配，当开始匹配T,T+1,…,T+m-1和0,1,…,P-1时，若匹配失败，关注的是文本串中参加匹配的最末位字符的下一位字符T+m．如果该字符没有在匹配模式字符串中出现，则直接跳过，即移动步长=匹配串长度+1（跳转函数见式（4））；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1（见图4）．虽然说BMHS算法的搜索速度要快于BMH算法，但是如果T+m-1没有出现在模式中，而T+m又在模式中出现时，其速度就没有BMH算法快了．

文本串Tabdabegeabc 字符串Pabace 字符串Pabace

（a）模式串中有T+m

文本串Tabdabegeabcb 字符串Pabace

（b）模式串中没有T+m

文本串Tabdakegeabcb 字符串Pabace

（b）模式串中有+m，但没有+m-1

图4 BMHS模式匹配算法

3 对BM模式匹配算法的改进

当前，在学界对BM模式匹配算法的改进方法已有不少，除了基本的BMH和BMHS算法外，还存在一些改进方法，比如赵一瑾（1998）提出了改进的BM匹配算法，通过子模式各自的性质及相互间的关系，控制模式匹配过程，以减少字符重复比较次数，从而提高算法匹配效率；闵联营和赵婷婷（2006）提出了改进的BM算法，并将其应用于入侵检测系统的检测引擎中；袁静波（2012）针对BMHS算法的不足，提出了一种改进的BMHS算法；张欢（2015）基于BMHS算法提出了DBMHS算法；等等．本文在结合经典的BM、BMH和BMHS算法，在其他学者的研究基础上，提出了一种新的改进方法，姑且称之为Optimizing Boyer-Moore Algorithm，即OBM算法．

3.1 OBM匹配算法的主要思想

通过对以上三种匹配方法的分析我们可以发现，三种匹配方法在对匹配窗口的首字符匹配都失配的情况下，效率最优．本文做出的优化方法是在借鉴BMHS算法的基本思想的基础上，当存在失配情形时，运用坏字符规则，来计算跳跃函数skip（T+m）的大小．之后，利用坏字符表来寻找与文本串字符相对应的模式字符串的更远字符T（其中，0≤≤），同时结合模式字符串的首字符串1计算出向右移动的距离，由此可以大大缩短比较次数和匹配的时间．

3.2 OBM匹配算法的匹配方法和匹配过程

按照BM匹配算法的基本思路，在预处理阶段同样设置两个备用函数：即用于保存记录模式字符串中上一个相同支付位置的位置函数location，以及用于记录文本串中出现的支付在模式字符串中的最右位置的坏字符数组函数skip，其预处理过程演示如下：

while （模式字符串长度m！=0）

skip [（unsigned char）*pattern++]=m--；

return skip；

函数location实现方法如下：

Temp=skip[p[i]]；

skip[p[i]]=i；//location数组中保存相同字符的前一skip值；

location[i]=temp；

i++；

Ⅰ．考察模式字符串的末字符P与之相对的文本字符T的匹配问题．如果失配，就考察T的下一文本字符T，并在坏字符规则的基础上计算出跳跃函数skip(T)的值1．

Ⅲ．考察模式支付串与文本串自右向左的完全匹配问题，若完全匹配，就结束匹配过程；否则，跳转至（ⅰ）．

3.3 OBM匹配的算法分析

根据以上的分析，我们可以发现，在算法上，OBM模式匹配算法确有由于BM算法的地方，比如右移的次数、最大移动距离的获取概率以及平均时间复杂度和空间复杂度上，都存在明显优于BM算法的成分．

3.3.1 右移的次数上

从上面的对比分析可见，BM和OBM算法的最大移动量分别为，2+2，而且随着模式字符串的不断增长，其最大移动量的差距也会不断扩大，而OBM模式匹配算法的右移次数和字符比较的次数都会明显少于BM算法．

3.3.2 最大移动距离的获取概率上

在OBM算法匹配过程中，我们考虑了两个字符，即模式字符串的末字符对应的文本字符与文本字符下一个字符，显而易见的是，两个字符的组合串的出现概率要比一个高．所以说OBM算法的最大移动距离获取概率要高于BM算法．

3.3.3 平均时间复杂度和空间复杂度上

据前所述，BM算法在最理想的情况下，时间复杂度为（/），而OBM算法最理想情况下的时间复杂度为（n/（2+2）），这是因为在进行预处理的时候，我们增加了一个位置函数location，生成了一个大小为模式字符串长度m的数组location，用来记录字符所处的位置，于是，OBM算法就在预处理阶段增加了一个额外的辅助空间，从而使该算法的时间复杂度为（），最理想的情况下为（/（2+2））．显然，OBM算法的平均时间复杂度和空间复杂度要小于BM算法．

[1] Boyer RS.Moore JS.AFast String Searching Algorithm[J].Communications of the ACM，1977，10:762-772.

[2] Horspool N R. Practical Fast Searching in Strings[J]. SoftwarePractice and Experience, 1980(6):50-56

[3] Sunday D M.A very fast substring search algorithm[J].Communications of the ACM，1990，33(8):132-142.

[4] Yang Weiwei，Liao Xiang. Improved pattern matching algorithm of BM[J].Computer Applications，2006(2):318-319.

[5] 赵一瑾.一个改进的BM串匹配算法[J].计算机研究与发展，1998（1）：46-49.

[6] 张明会，高婷婷.数学分析中几类基本概念逻辑结构分析（续）[J].重庆三峡学院学报，2014（3）：29-31.

（责任编辑：于开红）

Research on the Optimization of Boyer-Moore Pattern Matching Algorithm

ZHUANG Yan WANG Yong

In the era of big data, both natural science and social science are facing with how to use pattern matching method to strengthen the search of information. Through comparative analysis of the classic pattern matching algorithm BM algorithm, BMH algorithm and BMHS algorithm, this paper proposes an improved algorithm, i.e., OBM pattern matching algorithm, which can speed up the matching, deduct the times of comparison and shorten the matching process.

pattern matching; BM algorithm; OBM algorithm

TP301.6

A

1009-8135（2016）03-0038-05

2016-01-18

庄 彦（1981-），女，安徽淮北人，安徽工商职业学院讲师，硕士，主要研究系统开发、模式识别．王 勇（1963-），男，湖北孝感人，安徽工商职业学院副教授，主要研究程序设计开发．

2016安徽高校自然科学研究重点项目 “基于Android的C2C交易平台关键技术研究”（项目编号：KJ2016A083）；2015安徽高校自然科学研究重点项目“基于分级特征值算法的重复信息过滤研究”（项目编号：KJ2015A419）阶段性成果