串匹配算法的簡單并行實現

馬 明

摘要:結合BM模式匹配算法和并行計算的思想,提出了一種快速的串匹配并行實現策略,該策略將文本串劃分成一定長度的子串,將子串分配到不同的處理器中,在各個處理器中分別并行執行BM模式匹配,即便是在最壞的情況下也能達到較好的時間復雜度。

關鍵詞:串匹配;BM算法;BF算法;并行

中圖分類號:TP312 文獻標識碼:A 文章編號: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 串匹配概念

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

1.2 并行算法

并行算法是一些可同時執行的進程的集合,進程相互作用和協調作用達到問題的求解。并行算法的實現依賴于并行算法的基本設計技術,并行算法最基本的設計技術包括均勻劃分技術、方根劃分技術、對數劃分技術和功能劃分技術[1],該文采用了類似均勻劃分技術的思想,將文本串進行劃分,將劃分后的字串發送到不同的處理器,利用增加處理的個數來實現模式匹配,在處理器中同時進行匹配的策略節約了匹配的時間,是一種簡單的并行計算思想。

2 串匹配的并行實現

2.1 BF算法及其并行實現

2.1.1 BF算法

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

2.1.2 BF算法的并行實現

BF算法是一種簡單的模式匹配算法,在此算法的基礎上,引進并行計算的思想,對BF算法進行改進,利用增加處理器的個數來實現此算法的并行化 。將長為n的文本串text劃分成n-m+1個長度為m的子串。將n-m+1個長度為m 的子串分別分配到n-m+1個處理器。則將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,然后將模式串發送到各個處理器,在各個處理器中同時進行模式串與子串的匹配,若匹配成功則返回處理器的編號i,則i即為模式串在文本串的位置,此算法是在BF算法的基礎上實現的,但是在處理器中的比較是同時進行的,所以其時間復雜度為O(m2),此種并行實現策略適合于文本串與模式串長度差別不大的情況下的匹配,若m?塏n則不適合采用這種匹配策略。

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

2.2.1 BM算法描述

BM算法是1977年Boyer和Moore提出的一個模式匹配的算法。該算法的基本思想是:在模式匹配中,模式串P從左向右移動,但字符的配配從右向左進行。即P[m]P[m-1]…P[1], 在匹配中模式的滑動距離由一個函數dist[x]給出,其中x為發生不匹配時正文串text中對應的字符,dist[x]的計算如下:

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

發生不匹配時,模式串向右滑動dist[x]個字符,重新開始新一輪的 BM模式匹配[3-7]。

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

aabcdaababcadb

第一次:bcadb x=d,dist[d]=1 模式向右滑動1個字符

第二次: bcadbx=a,dist[a]=2 模式向右滑動2個字符

第三次: bcadbx=a,dist[a]=2 模式向右滑動2個字符

第四次: bcadbx=a,dist[a]=2 模式向右滑動2個字符

第五次: bcadbx=a,dist[a]=2 模式向右滑動2個字符

第六次: bcadb匹配成功

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

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

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

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

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

3 結束語

結合BM模式匹配算法和并行計算的思想,在傳統的串行串匹配的思想的基礎上,通過增加處理器的個數來實現匹配過程的并行化,對于文本串和模式串長度差別不太大的情況比較適用,節約了匹配時間。BM算法是一種比較經典的模式匹配算法,其減少了了匹配過程中許多不必要的字符比較,文章中將文本串分成兩個部分在兩個處理器中分別采用BM算法策略來實現的模式匹配,比原有的BM算法節約了一半的時間,有一定的實用價值。

參考文獻:

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

[2] 陳國良.并行計算[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] 張永平,徐冬陽.一種新的字符串單模式匹配算法[J].電腦知識與技術,2008,2(15).

[5] 羅大光,郝玉潔,劉乃琦.一種非常快速的字符串匹配算法[J].電子科技大學學報,2005,34(6).

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

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