基于改進BM算法的語義Web服務發(fā)現(xiàn)研究

(華北電力大學 北京 102206)

一、引言

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

二、BM算法

(一)算法思想

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

(二)BM算法具體描述

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

正文T=t1,t2,…,tn

模式p=p1,p2,…,pm

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

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

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

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

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

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

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

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

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

三、改進的BM算法介紹

(一)改進算法思想

(二)改進算法應用舉例

假設有文本串T和模式串P分別為，P:service，T:Buildthewebservicedescriptionvectors，分析在改進的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”開始自右向左和文本串的相應字符依次比較，設置value值為60%，當P[m,m-1,m-2,m-3]分別匹配成功時，此時不需要完全匹配，直接匹配P[1]與T[t-m+1]，如果匹配,則字符串匹配成功,否則，匹配失敗。

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

小結(jié)

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