(華北電力大學(xué) 北京 102206)

一、引言

伴隨著網(wǎng)絡(luò)的快速發(fā)展，服務(wù)數(shù)量得到顯著性的增長。Internet已經(jīng)成為一個Web服務(wù)存儲巨大的Web服務(wù)庫，提供了許多領(lǐng)域的服務(wù)，目前進(jìn)行服務(wù)發(fā)現(xiàn)主要是通過基于語義的服務(wù)匹配，當(dāng)語義匹配結(jié)果為零時(shí)，我們可以采用BM算法即一種模式匹配算法[2]進(jìn)行匹配，這樣可以彌補(bǔ)單純語義服務(wù)發(fā)現(xiàn)不足的缺點(diǎn)。本文闡述了BM算法的基本原理并提出了一種改進(jìn)算法，提高匹配效率，優(yōu)化了服務(wù)發(fā)現(xiàn)的過程。

二、BM算法

(一)算法思想

BM算法是1975年由Boyer和Moore提出的,它是一種后匹配算法，我們普通的字符串匹配算法是從左向右的，BM算法是從右向左匹配，即先判斷模式串最后一個字符是否匹配，最后判斷模式串第一個字符是否匹配。BM算法基本思想是從右向左的把模式串同文本串做比較。開始時(shí)模式串P的最左邊與文本串T的最左邊對齊，當(dāng)在某一趟比較中出現(xiàn)不匹配時(shí)，計(jì)算模式串右移的距離，把模式串向右移動該距離，再進(jìn)行從右至左的匹配；當(dāng)與最右的模式符號做比較的文本符號在模式中根本就沒有出現(xiàn)，則模式可以在這個文本符號之后移位m(模式串字符個數(shù))個位置[3-6]。

(二)BM算法具體描述

模式匹配問題可以描述如下：

正文T=t1,t2,…,tn

模式p=p1,p2,…,pm

(n>=m)要求在T中尋找等于P的子串。如果T中匹配到和P相等的子串，匹配成功，此時(shí)返回模式串在文本串中的位置，否則稱為匹配失敗,返回0。本算法定義了好后綴和壞字符，模式串與字符串匹配的的部分稱為好后綴，在匹配的過程中，如果文本串中的字符與模式串中的字符無法匹配成功，我們稱之為壞字符。接下來介紹一下匹配過程中用到的兩個規(guī)則。

1.好后綴規(guī)則(GoodSuffix)若發(fā)現(xiàn)某個字符不匹配的同時(shí)，已有部分字符匹配成功，我們稱之為好后綴記為P′，所在位置記為t1，接下來按如下兩種情況討論：

①如果同時(shí)在P中的另一位置也出現(xiàn)P′，此處位置記為t2，且兩個位置前的字符并不相同，則將P右移使t2處對應(yīng)t1方才的所在的位置。

② 如果在P中任何位置都沒有再出現(xiàn)和P′相同的字符串，則找到與P′的后綴相同的P的最長前綴s，向右移動P，使s對應(yīng)P′后綴所在的位置。

2.壞字符規(guī)則(BadChar)

在BM算法從右向左掃描的過程中，若發(fā)現(xiàn)某個字符x不匹配，則按如下兩種情況討論：

①如果字符x在模式串P中沒有出現(xiàn)，那么從字符x開始的m個字符顯然不可能與P匹配成功，直接全部跳過該區(qū)域即可。

②如果x在模式串P中出現(xiàn)，則以該字符進(jìn)行對齊。

BM算法使用上述好后綴規(guī)則和壞字符規(guī)則計(jì)算得到的移動值中的較大者來向右移動模式P到新的比較位置。實(shí)踐證明在大字母表情況下，BM算法效率非常高。

三、改進(jìn)的BM算法介紹

(一)改進(jìn)算法思想

(二)改進(jìn)算法應(yīng)用舉例

假設(shè)有文本串T和模式串P分別為，P:service，T:Buildthewebservicedescriptionvectors，分析在改進(jìn)的BM 算法中，模式串P與文本串T的過程。

T:Buildthewebservicedescriptionvectors

P:service

第一次匹配：模式串的最右邊的字符“e”和文本串中的字符“h”比較，第一次字符比較失敗，根據(jù)壞字符原則，可知壞字符“x”=h,將h與模式串中字符比較，發(fā)現(xiàn)沒有匹配的字符，根據(jù)移動原則，需要向右移動m個字符，即dest(x)=m=7。

T:Buildthewebservicedescriptionvectors

P:service

第二次匹配：模式串的最右邊的字符“e”和文本串中的字符“r”比較，匹配失敗，繼續(xù)自右向左匹配，發(fā)現(xiàn)與P[3]匹配成功，根據(jù)壞字符原則，模式串向右移動m-k個字符，即dest(x)=4。

第三次匹配：從模式串的尾字符“e”開始自右向左和文本串的相應(yīng)字符依次比較，設(shè)置value值為60%，當(dāng)P[m,m-1,m-2,m-3]分別匹配成功時(shí)，此時(shí)不需要完全匹配，直接匹配P[1]與T[t-m+1]，如果匹配,則字符串匹配成功,否則，匹配失敗。

模式串長度文本串長度比較次數(shù)(改進(jìn)前/改進(jìn)后)移動次數(shù)(改進(jìn)前/改進(jìn)后)73619/1711/11

小結(jié)

Web服務(wù)在很多領(lǐng)域發(fā)揮著重要作用，越來越多的企業(yè)將應(yīng)用程序轉(zhuǎn)換為Web服務(wù)，以提高應(yīng)用程序之間的互操作。面對網(wǎng)絡(luò)中海量的服務(wù)，增加服務(wù)發(fā)現(xiàn)的質(zhì)量和減少服務(wù)發(fā)現(xiàn)的時(shí)間成為一個關(guān)鍵問題。我們在實(shí)際應(yīng)用中,當(dāng)使用語義服務(wù)匹配失敗時(shí)，采用字符串匹配的方式，提高了匹配效率，使得服務(wù)發(fā)現(xiàn)的效率增加。