串匹配算法的简单并行实现

马 明

摘要:结合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).