馬 明

摘要:結(jié)合BM模式匹配算法和并行計(jì)算的思想,提出了一種快速的串匹配并行實(shí)現(xiàn)策略,該策略將文本串劃分成一定長(zhǎng)度的子串,將子串分配到不同的處理器中,在各個(gè)處理器中分別并行執(zhí)行BM模式匹配,即便是在最壞的情況下也能達(dá)到較好的時(shí)間復(fù)雜度。

關(guān)鍵詞:串匹配;BM算法;BF算法;并行

中圖分類號(hào):TP312 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2009)34-9795-02

Simple Parallel Implementation of String Matching Algorithm

MA Ming

(Dept of Mathematic and Computer, Hubei University, Wuhan 430062, China)

Abstract: In this paper, a parallel strategy to perform pattern was proposed, This strategy combines the advantages of BM pattern matching algorithms and parallel computing ideas. In this strategy, the text string will be divided into different substrings, the substring was sent to different processor respectively, and then each processor implements the BM pattern matching algorithms at the same time, even in the worst cases, it can achieve a better time complexity.

Key words: string matching; BM algorithm; BF algorithm; parallel

1 概述

1.1 串匹配概念

字符串是指由字符組成的有窮序列,字符串中包含的字符的個(gè)數(shù)稱為串的長(zhǎng)度,串匹配是指給定一個(gè)長(zhǎng)為n的文本串text[1..n]和長(zhǎng)為m的模式串p[1..m],找出串text中與串p相同的子串的起始位置,串匹配又稱為模式匹配。串匹配問(wèn)題是計(jì)算機(jī)科學(xué)中一個(gè)基本問(wèn)題,串匹配可用于數(shù)據(jù)處理、信息檢索、圖像處理、網(wǎng)絡(luò)入侵檢測(cè)等,在很多領(lǐng)域都有廣泛的應(yīng)用[1]。

1.2 并行算法

并行算法是一些可同時(shí)執(zhí)行的進(jìn)程的集合,進(jìn)程相互作用和協(xié)調(diào)作用達(dá)到問(wèn)題的求解。并行算法的實(shí)現(xiàn)依賴于并行算法的基本設(shè)計(jì)技術(shù),并行算法最基本的設(shè)計(jì)技術(shù)包括均勻劃分技術(shù)、方根劃分技術(shù)、對(duì)數(shù)劃分技術(shù)和功能劃分技術(shù)[1],該文采用了類似均勻劃分技術(shù)的思想,將文本串進(jìn)行劃分,將劃分后的字串發(fā)送到不同的處理器,利用增加處理的個(gè)數(shù)來(lái)實(shí)現(xiàn)模式匹配,在處理器中同時(shí)進(jìn)行匹配的策略節(jié)約了匹配的時(shí)間,是一種簡(jiǎn)單的并行計(jì)算思想。

2 串匹配的并行實(shí)現(xiàn)

2.1 BF算法及其并行實(shí)現(xiàn)

2.1.1 BF算法

Brute-Force算法簡(jiǎn)稱BF算法,是一種很古樸的算法,該算法的基本思想是[2],將模式串text中的第一個(gè)字符與文本串p的第一個(gè)字符進(jìn)行比較,若相同,則繼續(xù)逐個(gè)比較后面的字符。若不相同,則將從模式串的第一個(gè)字符開(kāi)始與文本串的第二個(gè)字符相比較(相當(dāng)于模式串p整體向后移動(dòng)一個(gè)字符),如此匹配下去,若模式串中的每個(gè)字符都和文本串中的對(duì)應(yīng)子串相等,則稱匹配成功,返回文本串中該子串的位置。否則稱匹配不成功。此算法是一種傳統(tǒng)的串行算法,最壞情況下的時(shí)間復(fù)雜度是O(m*n),效率較低。

2.1.2 BF算法的并行實(shí)現(xiàn)

BF算法是一種簡(jiǎn)單的模式匹配算法,在此算法的基礎(chǔ)上,引進(jìn)并行計(jì)算的思想,對(duì)BF算法進(jìn)行改進(jìn),利用增加處理器的個(gè)數(shù)來(lái)實(shí)現(xiàn)此算法的并行化 。將長(zhǎng)為n的文本串text劃分成n-m+1個(gè)長(zhǎng)度為m的子串。將n-m+1個(gè)長(zhǎng)度為m 的子串分別分配到n-m+1個(gè)處理器。則將text[1]～text[m]分配到處理器P1,將text[2]～text[m+1]分配到P2,將text[3]～text[m+2]分配到處理器P3...將text[n-m+1]～text[n]分配到Pn-m+1,然后將模式串發(fā)送到各個(gè)處理器,在各個(gè)處理器中同時(shí)進(jìn)行模式串與子串的匹配,若匹配成功則返回處理器的編號(hào)i,則i即為模式串在文本串的位置,此算法是在BF算法的基礎(chǔ)上實(shí)現(xiàn)的,但是在處理器中的比較是同時(shí)進(jìn)行的,所以其時(shí)間復(fù)雜度為O(m2),此種并行實(shí)現(xiàn)策略適合于文本串與模式串長(zhǎng)度差別不大的情況下的匹配,若m?塏n則不適合采用這種匹配策略。

2.2 一種基于BM算法的串匹配并行化策略

2.2.1 BM算法描述

BM算法是1977年Boyer和Moore提出的一個(gè)模式匹配的算法。該算法的基本思想是:在模式匹配中,模式串P從左向右移動(dòng),但字符的配配從右向左進(jìn)行。即P[m]P[m-1]…P[1], 在匹配中模式的滑動(dòng)距離由一個(gè)函數(shù)dist[x]給出,其中x為發(fā)生不匹配時(shí)正文串text中對(duì)應(yīng)的字符,dist[x]的計(jì)算如下:

1) 若p中不存在字符x即x≠p[j] (1≤j≤m);則dist[x]=m

2) 若p中存在字符x,j=max{j—p[j]=x, 1≤j≤m-1}; 則dist[x]=m-j

發(fā)生不匹配時(shí),模式串向右滑動(dòng)dist[x]個(gè)字符,重新開(kāi)始新一輪的 BM模式匹配[3-7]。

例如,文本串text="aabcdaababcadb",模式串為p="bcadb",具體的匹配過(guò)程如下:

aabcdaababcadb

第一次:bcadb x=d,dist[d]=1 模式向右滑動(dòng)1個(gè)字符

第二次: bcadbx=a,dist[a]=2 模式向右滑動(dòng)2個(gè)字符

第三次: bcadbx=a,dist[a]=2 模式向右滑動(dòng)2個(gè)字符

第四次: bcadbx=a,dist[a]=2 模式向右滑動(dòng)2個(gè)字符

第五次: bcadbx=a,dist[a]=2 模式向右滑動(dòng)2個(gè)字符

第六次: bcadb匹配成功

BM模式匹配算法跳過(guò)了不必要的模式比較,是一種比較高效的匹配算法。

2.2.2 基于BM算法的串匹配并行策略

根據(jù)串匹配的概念,無(wú)論哪一種匹配策略都是將模式串與文本串對(duì)齊比較,當(dāng)字符比較不匹配時(shí)要將模式往后移動(dòng),只是不同的匹配策略中,模式串的移動(dòng)所依據(jù)原則有所不同,在本文中,我們將長(zhǎng)度為n的文本串text的text[1]～text[n/2+m-1]分配給處理器P1,text[n/2+1]～text[n]分配給處理器P2,同時(shí)將模式串p發(fā)送給處理器P1和P2,然后在處理器P1和處理器P2中同時(shí)進(jìn)行BM模式匹配。

例如,文本串為"aaacdaab",模式串為"cda",則將模式串發(fā)給處理器P1和P2 ,將文本串中的子串"aaacda"發(fā)送到P1,將子串"daab"發(fā)送到P2,然后在兩個(gè)處理器中同時(shí)進(jìn)行BM模式匹配,即在處理器P1中進(jìn)行文本串"aaacda"和模式串"cda"的BM模式匹配;在處理器P2中進(jìn)行文本串"daab"和模式串"cda"的BM模式匹配。

這種模式匹配方法實(shí)際上是將正文串分成了兩個(gè)部分,對(duì)兩個(gè)部分同時(shí)進(jìn)行高效的BM模式匹配,兩個(gè)處理器中的文本串有部分重復(fù),重復(fù)的目的是為了有效避免由劃分點(diǎn)左右的字符組成的子串在匹配過(guò)程中被遺漏。這種匹配策略的時(shí)間復(fù)雜度比單處理器下的BM模式匹配時(shí)間復(fù)雜度減少了一半,提高了匹配效率,縮短了匹配時(shí)間。

3 結(jié)束語(yǔ)

結(jié)合BM模式匹配算法和并行計(jì)算的思想,在傳統(tǒng)的串行串匹配的思想的基礎(chǔ)上,通過(guò)增加處理器的個(gè)數(shù)來(lái)實(shí)現(xiàn)匹配過(guò)程的并行化,對(duì)于文本串和模式串長(zhǎng)度差別不太大的情況比較適用,節(jié)約了匹配時(shí)間。BM算法是一種比較經(jīng)典的模式匹配算法,其減少了了匹配過(guò)程中許多不必要的字符比較,文章中將文本串分成兩個(gè)部分在兩個(gè)處理器中分別采用BM算法策略來(lái)實(shí)現(xiàn)的模式匹配,比原有的BM算法節(jié)約了一半的時(shí)間,有一定的實(shí)用價(jià)值。

參考文獻(xiàn):

[1] 陳國(guó)良.并行算法實(shí)踐[M].北京:高等教育出版社,2004.

[2] 陳國(guó)良.并行計(jì)算[M].北京:高等教育出版社,2003.

[3] Boyer R S,Moore J S.A Fast String Searching Algorithm[J].Communications of the ACM,1977,20(10):762-772.

[4] 張永平,徐冬陽(yáng).一種新的字符串單模式匹配算法[J].電腦知識(shí)與技術(shù),2008,2(15).

[5] 羅大光,郝玉潔,劉乃琦.一種非?？焖俚淖址ヅ渌惴╗J].電子科技大學(xué)學(xué)報(bào),2005,34(6).

[6] 錢屹,候義斌.一種快速的字符串匹配算法[J].小微型計(jì)算機(jī)系統(tǒng),2004,25(3).

[7] 巫喜紅,凌捷.BM模式匹配算法剖析[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(3).