(华北电力大学 北京 102206)

一、引言

伴随着网络的快速发展，服务数量得到显著性的增长。Internet已经成为一个Web服务存储巨大的Web服务库，提供了许多领域的服务，目前进行服务发现主要是通过基于语义的服务匹配，当语义匹配结果为零时，我们可以采用BM算法即一种模式匹配算法[2]进行匹配，这样可以弥补单纯语义服务发现不足的缺点。本文阐述了BM算法的基本原理并提出了一种改进算法，提高匹配效率，优化了服务发现的过程。

二、BM算法

(一)算法思想

BM算法是1975年由Boyer和Moore提出的,它是一种后匹配算法，我们普通的字符串匹配算法是从左向右的，BM算法是从右向左匹配，即先判断模式串最后一个字符是否匹配，最后判断模式串第一个字符是否匹配。BM算法基本思想是从右向左的把模式串同文本串做比较。开始时模式串P的最左边与文本串T的最左边对齐，当在某一趟比较中出现不匹配时，计算模式串右移的距离，把模式串向右移动该距离，再进行从右至左的匹配；当与最右的模式符号做比较的文本符号在模式中根本就没有出现，则模式可以在这个文本符号之后移位m(模式串字符个数)个位置[3-6]。

(二)BM算法具体描述

模式匹配问题可以描述如下：

正文T=t1,t2,…,tn

模式p=p1,p2,…,pm

(n>=m)要求在T中寻找等于P的子串。如果T中匹配到和P相等的子串，匹配成功，此时返回模式串在文本串中的位置，否则称为匹配失败,返回0。本算法定义了好后缀和坏字符，模式串与字符串匹配的的部分称为好后缀，在匹配的过程中，如果文本串中的字符与模式串中的字符无法匹配成功，我们称之为坏字符。接下来介绍一下匹配过程中用到的两个规则。

1.好后缀规则(GoodSuffix)若发现某个字符不匹配的同时，已有部分字符匹配成功，我们称之为好后缀记为P′，所在位置记为t1，接下来按如下两种情况讨论：

①如果同时在P中的另一位置也出现P′，此处位置记为t2，且两个位置前的字符并不相同，则将P右移使t2处对应t1方才的所在的位置。

② 如果在P中任何位置都没有再出现和P′相同的字符串，则找到与P′的后缀相同的P的最长前缀s，向右移动P，使s对应P′后缀所在的位置。

2.坏字符规则(BadChar)

在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：

①如果字符x在模式串P中没有出现，那么从字符x开始的m个字符显然不可能与P匹配成功，直接全部跳过该区域即可。

②如果x在模式串P中出现，则以该字符进行对齐。

BM算法使用上述好后缀规则和坏字符规则计算得到的移动值中的较大者来向右移动模式P到新的比较位置。实践证明在大字母表情况下，BM算法效率非常高。

三、改进的BM算法介绍

(一)改进算法思想

(二)改进算法应用举例

假设有文本串T和模式串P分别为，P:service，T:Buildthewebservicedescriptionvectors，分析在改进的BM 算法中，模式串P与文本串T的过程。

T:Buildthewebservicedescriptionvectors

P:service

第一次匹配：模式串的最右边的字符“e”和文本串中的字符“h”比较，第一次字符比较失败，根据坏字符原则，可知坏字符“x”=h,将h与模式串中字符比较，发现没有匹配的字符，根据移动原则，需要向右移动m个字符，即dest(x)=m=7。

T:Buildthewebservicedescriptionvectors

P:service

第二次匹配：模式串的最右边的字符“e”和文本串中的字符“r”比较，匹配失败，继续自右向左匹配，发现与P[3]匹配成功，根据坏字符原则，模式串向右移动m-k个字符，即dest(x)=4。

第三次匹配：从模式串的尾字符“e”开始自右向左和文本串的相应字符依次比较，设置value值为60%，当P[m,m-1,m-2,m-3]分别匹配成功时，此时不需要完全匹配，直接匹配P[1]与T[t-m+1]，如果匹配,则字符串匹配成功,否则，匹配失败。

模式串长度文本串长度比较次数(改进前/改进后)移动次数(改进前/改进后)73619/1711/11

小结

Web服务在很多领域发挥着重要作用，越来越多的企业将应用程序转换为Web服务，以提高应用程序之间的互操作。面对网络中海量的服务，增加服务发现的质量和减少服务发现的时间成为一个关键问题。我们在实际应用中,当使用语义服务匹配失败时，采用字符串匹配的方式，提高了匹配效率，使得服务发现的效率增加。