匹配算法论文范文

引言：寻求写作上的突破？我们特意为您精选了4篇匹配算法论文范文，希望这些范文能够成为您写作时的参考，帮助您的文章更加丰富和深入。

篇1

在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3…sn，模式串表示为T=t1t2…tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。

1KMP算法

最简单的朴素串匹配算法(BF算法)是从主串的第一个字符和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式串的第一个字符进行比较。依次类推，直至模式串和主串中的一个子串相等，此时称为匹配成功，否则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移一个字符，若主串中存在和模式串只有部分匹配的多个子串，匹配指针将多次回溯，而回溯次数越多算法的效率越低，它的时间复杂度一般情况下为O((n-m+1)m)（注：n和m分别为主串和模式串的长度），最坏的情况下为O(m*n)，最好的情况下为O(m+n)。KMP模式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中出现失配时，不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符，过滤掉那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配的效率，该算法的时间复杂度为O(m+n)。

那么如何确定哪些是多余的比较？在KMP算法中通过引入前缀函数f(x)来确定每次匹配不需要比较的字符，保证了匹配始终向前进行，无须回溯。假设主串为s1s2，sn.，模式串为t1t2，tm.，其中m≦n，从si+1开始的子串遇到一个不完全的匹配，使得：

(1.1)

如果我们能确定一个最小的整数，使得：

(1.2)

其中，所以确定i''''等价于确定k，这里的k值就是我们要求的前缀函数f(x)。由式1.1和1.2中K值与主串s无关，只与给定的模式串t中与主串匹配的q有关，即k=f(q)，

f(q)=max{i|0iq且t[1..i]是t[1..q]的后缀}(1.3)

确定KMP前缀函数的算法如下：

#defineMAXSIZE100

Typedefunsignedcharstring[MAXSIZE+1];//0号单元用来存放串的长度

voidf(sstringt,int*array)

{

m=t[0];//m为当前模式串的长度

array=(int*)malloc((m+1)*sizeof(int));//0号元不用

array[1]=0;k=0;

for(q=2;q<=m;q++)

{while(k>0&&t[k+1]!=t[q])k=array[k];

if(t[k+1]==t[q])k=k+1;

array[q]=k;

}

}

关于KMP算法的前缀函数f(x)的示例见表1。

当模式串中有i个字符串匹配成功，第i+1个字符不匹配时，则从i-f(i)个字符重新开始比较，这样不仅无须回溯，而且一次可以向前滑动i-f(i)个字符，大大提高了模式匹配的效率。下面给出朴素匹配算法和KMP匹配算法的比较，见表2。

表2朴素匹配算法和KMP匹配算法比较表

朴素算法KMP算法

时间复杂度O((n-m+1)m)O(m+n)

向前移动字符个数1q-f(q)

回溯次数q-1无

其中：n为主串长度，m为模式串长度，q为匹配成功的字符个数

2KMP算法的改进

在KMP算法的实际应用中，发现该算法也存在着不足，结合下面的表一来论述KMP模式匹配算法的改进。假设模式串前4个字符与主串的第i+1..i+4匹配成功，第5个字符匹配失败，此时前缀函数f(4)=1，下一次匹配将从第i+4开始，并直接将模式串中的第2个字符与主串中的第i+5个字符进行比较，从表1中可知，匹配必将失败，此次比较是多余的。这说明此时的前缀函数f(x)并不是最优，需要对前缀函数进行改进。实质上，所谓对KMP算法的改进就是对其前缀函数的改进。

4结语

本文给出的算法较朴素匹配算法在效率上有了较大的提高，尤其是对重复字符出现较少的数据段进行模式匹配可取得较高的查找效率。应用于大型数据库的数据查询，会更加有效地缩短查找时间。

参考文献

[1]严蔚敏，吴伟民.数据结构[M].清华大学出版社，2001

篇2

[4]

ZAKI T， ESSAADY Y， MAMMASS D， et al. A hybrid method ngramsTFIDF with radial basis for indexing and classification of Arabic document [J]. International Journal of Software Engineering and Its Applications， 2014， 8（2）： 127-144.

[5]

SIDOROV G， VELASQUEZ F， STAMATATOS E， et al. Syntactic dependencybased ngrams as classification features [C]// MICAI 2012： Proceedings of the 11th Mexican International Conference on Artificial Intelligence， LNCS 7630. Berlin： Springer， 2013： 1-11.

[6]

YI Y， GUAN J， ZHOU S. Effective clustering of microRNA sequences by ngrams and feature weighting [C] // Proceedings of the 2012 IEEE 6th International Conference on Systems Biology. Piscataway： IEEE， 2012： 203-210.

[7]

BOURAS C， TSOGKAS V. Enhancing news articles clustering using word ngrams [C] // DATA 2013： Proceedings of the 2nd International Conference on Data Technologies and Applications. London： dblp Computer Science Bibliography， 2013： 53-60.

[8]

GHANNAY S， BARRAULT L. Using hypothesis selection based features for confusion network MT system combination [C] // EACL 2014： Proceedings of the 3rd Workshop on Hybrid Approaches to Translation （HyTra）. Stroudsburg： Association for Computational Linguistics， 2014： 2-6.

[9]

SIDOROV G， VELASQUEZ F， STAMATAOS E， et al. Syntactic ngrams as machine learning features for natural language processing [J]. Expert Systems with Applications， 2014， 41（3）： 853-860.

[10]

HAN Q， GUO J， SCHTZE H. CodeX： combining an SVM classifier and character ngram language models for sentiment analysis on Twitter text [C]// SemEval 2013： Proceedings of the Second Joint Conference on Lexical and Computational Semantics （*SEM）， Volume 2： Proceedings of the Seventh International Workshop on Semantic Evaluation. Stroudsburg： Association for Computational Linguistics， 2013： 520-524.

http：//p.nus.edu.sg/～antho/S/S13/S13-2086.pdf

[11]

BESPALOY D， BAI B， QI Y， et al. Sentiment classification based on supervised latent ngram analysis [C] // CIKM 11： Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 375-382.

[12]

MILLER Z， DICKINSON B， HU W. Gender prediction on Twitter using stream algorithms with ngram character features [J]. International Journal of Intelligence Science， 2012， 2（4A）： 143-148.

[13]

WRIGHT J， LLOYDTHOMAS H. A robust language model incorporating a substring parser and extended ngrams [C] // ICASSP 1994： Proceedings of the 1994 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 1994： 361-364.

[14]

HACIOGLU K， WARD W. Dialogcontext dependent language modeling combining ngrams and stochastic contextfree grammars [C] // ICASSP 2001： Proceedings of the 2001 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 2001， 1： 537-540.

[15]

SIU M， OSTENDORF M. Variable ngrams and extensions for conversational speech language modeling [J]. Speech and Audio Processing， 2000， 1（8）： 63-75.

[16]

ZHOU S， GUAN J， HU Y， et al. A Chinese document categorization system without dictionary support and segmentation processing [J]. Journal of Computer Research and Development， 2001， 38（7）： 839-844. （周水庚，关佶红，胡运发，等.一个无需词典支持和切词处理的中文文档分类系统[J].计算机研究与发展，2001，38（7）：839-844）

[17]

GAO Z， LI X. Feature extraction method based on sliding window application in text classification[J]. Science & Technology Information， 2008（34）： 23-24. （高振峰，李锡祚.基于滑动窗口的特征提取方法在文本分类中的应用[J].科技信息：学术版，2008（34）：23-24.）

[18]

篇3

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2015）01-08-04

An improved pattern matching algorithm of BMHS

Zhang Huan， Hu Yong

（School of Electronic and Information Engineering， Sichuan University， Chengdu， Sichuan 610065， China）

Abstract： Pattern matching plays an important role in computer application. By analyzing BM， BMH， BMHS algorithm and their corresponding improved algorithms， a new improved algorithm（called DBMHS） based on BMHS is proposed. DBMHS takes full advantages of two ends string characters of pattern string， through comparing two ends character jump distance of pattern matching， jump distance is increased. The experiment results show that the improved algorithm significantly increases the jump distance of matching window， effectively improving the matching efficiency.

Key words： pattern matching; jump distance; BM algorithm; BMH algorithms; BMHS algorithm; DBMHS algorithm

0 引言

随着网络技术的高速发展，网络资源呈爆炸式增长。如何在网络数据中找到需要的信息，已经成为人们研究的热点问题。模式匹配算法在很多领域得到了较为广泛的应用，如入侵检测、计算机病毒特征匹配[1]、搜索引擎、文本挖掘等。目前关于模式匹配的算法有很多，其中最著名的是BM算法[2]。BM算法发展的过程中，1980年Horspol发表了改进与简化BM算法的论文，即Boyer Moore Horspoo（BMH）算法[3]，随后Sunday在1990年在BMH算法的基础上又进行了改进，提出了BMHS算法[4]。本文对现有几种典型模式算法进行分析，在BMHS算法的基础上进行改进，并进行试验和结果分析。

1 典型算法

1.1 BM算法

BM算法是由Boyer和Moore在1977提出的单模式匹配算法。它是目前实际应用中效率较高的单模式匹配算法之一。BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。BM 算法中坏字符跳跃表和好后缀跳跃表的设计对提高BM算法效率有至关重要的作用。设文本T（长度为n），模式串P（长度为m）。

⑴ 坏字符跳跃表：当Pk≠Ti，即不匹配情况发生时，若此时Pk是P的末字符且Ti在模式串P中不出现，则下一次比较可以将匹配窗口直接移动m个位置后继续匹配;若Ti在模式串P中出现，则找到Ti在模式串P中出现的最右边的位置j（1≤j≤m-1），匹配窗口移动的距离为m-j（如图1所示）。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图1.tif>

图1 坏字符规则

⑵ 好后缀跳跃表： 当Pk≠Ti（k<m）时，子串Pk+1Pk+2…Pm与Ti+1Ti+2…Ti+m-k是匹配的。若在模式串P的k位置左边有与Pk+1Pk+2…Pm相同的子串P1P2…Pm-s或Pk+1Pk+2…Pm的某个后缀Ps+1Ps+2…Pm与P的某前缀P1P2…Pm-s相同，即移动匹配窗口s位使Ti位置与该子串对应位置对齐，算法继续匹配（如图2所示）。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图2.tif>

图2 好后缀规则

在匹配过程中，模式串P与文本T从右向左开始匹配，一旦发现不匹配，取好字符跳转和坏字符跳转之间较大的值作为模式串P的向右跳转距离。最理想的情况是每次匹配时文本T中第一个匹配的字符不存在于模式串P中，此时BM的算法的时间复杂度为O（n/m）;最坏的情况是文本T中有多个重复的字符，并且模式串P由m-1个相同的字符前加一个不同的字符组成，在这种情况下，BM算法的时间复杂度为O（mn）。

1.2 BMH算法

Horspool提出的BMH算法相对于BM算法更容易实现。BMH算法在预处理阶段只使用了坏字符跳跃表，无论文本中哪个字符造成了匹配失败，都将依据坏字符跳转表向右移动。BMH算法的基本思想是：①搜索文本时，从头到尾搜索，匹配时从右向左匹配。首先比较文本指针所指字符和模式串的最后一个字符，如果相等，再比较其余m-1个字符，无论文本中哪个字符造成了匹配失败，都将由文本中和模式串最后一个位置对应的字符来启发模式串向右移动，即当匹配开始比较TiTi+1…Ti+m-1和P0P1…Pm-1时，一旦发生不匹配，计算跳转距离skip（Ti+m-1），跳转后将模式串和文本对齐后重新匹配。②如果与P完全匹配，返回在T中对应的位置;③如果搜索完T仍然找不到完全匹配的位置，则查找失败[3]（如图3所示）。坏字符跳转计算公式：

<E：＼方正创艺5.1＼Fit201412＼图＼zh图3.tif>

图3 BMH算法

如图3所示，当文本中的与T2（‘d’）与模式串P中的P2（‘c’）发生不匹配时，计算跳转距离skip（T4），可以看出P1与T4相等，模式串P向右移动3个字符，即skip（T4）等于3，然后将P1与T4对齐后重新匹配。

BMH算法简化了初始化过程，匹配过程中的判断过程也作了简化，因为BMH算法只采用了BM算法的坏字符移动规则，并且将失配情况与偏移量的计算独立，不关心文本串中哪个字符造成了失配，只考虑用于模式串最右端对齐的文本字符来决定偏移量。该算法的理论时间复杂度与BM算法一致，但实际使用情况下较BM算法效率高。

1.3 BMHS算法

BMHS算法在BMH算法的基础上作了进一步改进，该算法的主要思想是：当开始匹配TiTi+1…Ti+m-1和P0P1…Pm-1时，若发生不匹配，考虑下一个字节的情况，即利用下一个字符Ti+m决定右移量。当下一个字符Ti+m不在模式串P中出现时，它的右移量比BMH算法的右移量大，跳过m+1个字符。通常情况下，BMHS算法比BMH算法快，但当Ti+m-1不在模式中出现，而Ti+m出现在模式串中时， BMHS算法[4]的效果就不如BMH算法[3]。匹配过程如图4。BMHS算法的跳转距离计算公式为：

<E：＼方正创艺5.1＼Fit201412＼图＼zh图4.tif>

图4 BMHS算法

如图4所示，当Ti+m出现在模式串P中时，如图4（a），将模式串P中的字符‘e’与Ti+m对齐;当Ti+m不存在于模式串P中时，如图4（b）所示，模式串P向右移动m+1个字符;而图4（c）中当Ti+m存在于模式串P中，而Ti+m-1不存在于模式串P中时，skip（Ti+m-1）等于5，而skip（Ti+m）等于1，Ti+m-1的跳转距离大于Ti+m的跳转距离，若还使用Ti+m为标准，则会降低匹配效率。在BMHS算法中最理想的时间复杂度为O（n/m+1）。

1.4 对各算法的已有改进

在模式匹配中存在两个基本定理：任何字符串匹配算法的最坏情况下必须检查至少n-m+1个文本中的字符;任何字符串匹配算法至少检查n/m个字符[5]。因此，没有一个算法比BM算法有更好的计算复杂度，但是我们可以通过改进来减少比较次数，提高匹配的平均性能。

基于以上三种模式匹配算法，近些年已经有多种改进算法。例如，利用统计字符在模式串中出现的频率来实现跳转[6];利用双字节计算偏移量[7-9];通过模式串P和文本T之间的关系来实现跳转[10];利用已匹配成功的字符串来进行跳转[11]，以及从模式串两端向中间匹配的方式[12]来改进模式匹配算法等。以上算法虽然减小了匹配次数，但相应增加了匹配的时间。接下来详细介绍一种通过双字节来计算偏移量的模式匹配改进算法。

2012年袁静波提出了一种改进的BMHS模式匹配算法[8]。该算法在BMHS算法的基础上利用文本T中与模式串P最后一个字符对应的字符Ti+m-1，以及Ti+m和Ti+m+1来实现跳转，模式串P和文本T从右向左匹配。以下是具体匹配过程。

第一步：当文本T和模式串P发生失配时，首先判断Ti+m是否在模式串中，若不存在直接跳过m+1的距离，如图5所示，文本T中的T4（‘d’）不在模式串P中，则模式串P向右移动m+1个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图5.tif>

图5 Ti+m不在模式串P中

第二步：当Ti+m在模式串中时，判断子串Ti+m Ti+m+1是否在模式串P中，若不存在，则跳过m+2的距离，如图6，子串“be”不在模式串P中，则模式串向右跳转m+2个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图6.tif>

图6 Ti+m Ti+m+1不在模式串P中

第三步：若模式串包含Ti+m Ti+m+1，则比较子串Ti+m-1Ti+m是否存在于模式串P中，不存在的话跳转m+1个字符，如图7，子串Ti+m Ti+m+1（“be”）存在与模式串P中，而子串Ti+m-1 Ti+m（“gb”）不存在与模式串P中，则模式串P向右跳转m+1个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图7.tif>

图7 Ti+m-1 Ti+m不在模式串P中

第四步：若Ti+m Ti+m+1和Ti+m-1 Ti+m都存在于模式串中，则取两者之间匹配的最大值进行跳转，如图8，可以看出，子串Ti+m Ti+m+1（“ea”）的跳转距离为2，子串Ti+m-1 Ti+m（“ae”）的跳转距离为3，取跳转距离较大的值，则模式串P应向右跳转3个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图8.tif>

图8 比较得到较大值进行跳转

在该改进算法中，模式串P最大的跳转距离为m+2，在理想的情况下该算法的时间复杂度为O（n/m+2）。

2 DBMHS算法

2.1 基本思想

通过观察BM，BMH和BMHS算法的匹配过程可以发现，这些算法在匹配窗口的首字符匹配均失败时效率最优。本文提出的DBMHS算法通过比较模式串P的第一个字符P0的跳转距离jump（P1）和在T中与模式串P最后一个字符对应的后一个字符Ti+m的跳转距离jump（Ti+m）来移动模式串P。跳转距离公式如下：

jump（P1）={k|Ti+k=P1，1≤k≤m}

jump（Ti+m+1）=m-k+1 k=Max{k|Pk=Ti+m+1，1≤k≤m}

2.2 匹配算法

显然，提高首字符匹配失败的概率是提高算法效率的关键之一。改进的DBMHS算法结合了BMHS算法特点，首先模式串P与文本T左端对齐，从右向左开始匹配，先检测T中与模式串最后一个字符相对应的字符Ti+m-1是否在模式串P中，若Ti+m-1不在模式串P中出现，则检测后一个字节Ti+m是否存在于模式串P中，若Ti+m不在模式串P中出现，则模式串P可以向右移动最大的距离m+1，否则移动距离为m。如图9、图10所示。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图9.tif>

图9 Ti+m不存在于模式串P中

<E：＼方正创艺5.1＼Fit201412＼图＼zh图10.tif>

图10 Ti+m存在于模式串P中

若Ti+m-1与模式串P中对应的字符相匹配，则接着匹配余下的字符，一旦发生不匹配的情况，则检测Ti+m是否存在于模式串P中，若不存在，则模式串P直接向右移动m+1的距离，若存在则计算Ti+m的跳转距离，然后计算模式串P中第一个字符P0的跳转距离，比较这两个跳转距离，选择较大的跳转距离作为模式串P的实际跳转距离。从图11可以看出，若使用Ti+m进行跳转，则模式串P的跳转距离为1，若使用模式串P的第一个字符P0进行跳转，则模式串的跳转距离为2，通过比较，使用P0的跳转距离可以使模式串P尽量的向右移动。需要注意的是，若模式串P或文本T中同一个字符出现多次，在计算跳转距离时，需分情况处理，例如，若匹配Ti+m时，P中出现多个与Ti+m相同的字符，则选择最右端的字符与Ti+m对齐;若是在匹配P0时出现这种情况，则选择T中靠左的字符进行对齐。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图11.tif>

图11 P1跳转距离大于Ti+m

若算法在匹配时自右向左均匹配成功，则此时找到一次完全匹配，算法结束。DBMHS匹配算法伪代码描述如表1。

表1 DBMHS匹配算法伪代码

[输入：文本串T，模式串P

输出：文本串T中是否存在子串P＼&While i≤T

Do If Ti+m-1 Pm

If Ti+m-1P

If Ti+mP Then MOVE m;

Else MOVE m+1;

Else

If Ti+mP Then MOVE m+1;

Else MOVE max（jump（P0），jump（Ti+m））;

Else If Ti+kPk

If Ti+mP Then MOVE m+1;

Else MOVE max（jump（P0），jump（Ti+m））;

Else If Ti。。。i+m-1= P0。。。m-1 Then Return true;

Return false;＼&]

2.3 算法分析

从BMHS算法的匹配算法可以看出，BMHS算法在比较时利用下一个字符Ti+m决定右移量，当Ti+m不在模式串P中出现时会跳转最大的距离m+1，但当Ti+m出现在模式串P中时，由于多进行了一次匹配，BMHS匹配算法的效果就不如BMH算法。因此，DBMHS匹配算法通过模式串两端的字符来充分利用Ti+m。当Ti+m出现在模式串P中时，计算Ti+m的跳转距离，并计算第一个字符P0的跳转距离，通过比较这两个字符的跳转距离来实现更大的跳转，这样不仅提高了Ti+m的利用率，而且获得了更高的匹配效率。

3 算法性能测试

本实验使用的计算机硬件平台为IntelPentium G2020处理器，4G内存，软件平台为Windows 7操作系统，Microsoft Visual Studio 2010集成开发环境。在此环境下分别对BMHS算法、IBMHS算法和DBMHS算法进行测试，IBMHS匹配算法为文献[8]中提出的对BMHS匹配算法的改进算法。

实验随机选取4个不同长度的文本串，实验文本字符集由大小写字母，数字和空格组成。模式串从文本串中随机提取。分别执行BMHS算法、IBMHS算法和DBMHS算法程序，统计不同长度文本串，不同模式串的情况下，算法的执行时间和匹配窗口的移动次数。每个算法分别执行10000次，运行时间取平均值。得到的数据如表2和表3。

表2 匹配窗口移动次数

[文本长度＼&模式串长度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配次数＼&匹配次数＼&匹配次数＼&2481＼&12＼&259＼&183＼&202＼&1138＼&10＼&114＼&90＼&95＼&555＼&14＼&44＼&32＼&35＼&225＼&12＼&16＼&13＼&14＼&]

表3 匹配时间

[文本长度＼&模式串长度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配时间＼&匹配时间＼&匹配时间＼&2481＼&12＼&0.218＼&1.482＼&0.218＼&1138＼&10＼&0.094＼&0.671＼&0.094＼&555＼&14＼&0.031＼&0.218＼&0.031＼&225＼&12＼&0.016＼&0.094＼&0.016＼&]

由表2和表3可以看出，本文提出的算法相比传统的BMHS算法有较大的改进。例如第一次匹配，DBMHS匹配次数较BMHS减少了约28%，并且文本长度越长，减少的匹配次数就会越多。此外，DBMHS在匹配用时上与传统的BMHS算法比较接近。虽然IBMHS算法的匹配次数少于DBMHS算法，但是匹配时间几乎是DBMHS算法的7倍。从效率上来说，DBMHS算法要优于其他算法。

4 结束语

本文通过分析BM，BMH和BMHS模式匹配算法，提出了一种改进的算法DBMHS。由于DBMHS算法充分利用了模式串两端字符，通过实验可以证明，该算法的匹配效率得到了显著提升。下一步的研究将考虑该算法应用在多模式匹配中，并利用语言学中的知识，如模式串与文本结构，使其性能更加优越。

参考文献：

[1] Yang Wang and Hidetsune Kobayashi. High Performance Pattern

Matching Algorithm for Network Security. IJCSNS International Journal of Computer Science and Network Security，2006.6（10）：83-87

[2] Boyer R S，Moore J S.A Fast String Searching Algorithm[J].

Communications of the ACM，1977.20：762-772

[3] Horspool N R. Practical Fast Searching in Strings[J]. Software

Practice and Experience，1980.10（6）：5012506

[4] Sunday D M. A very fast substring search algorithm[J].

Communication of the ACM，1990.33（8）：132-142

[5] 李雪莹，刘宝旭等.字符串匹配技术研究[J].计算机工程，2004.30

（22）：24226

[6] 刘胜飞，张云泉.一种改进的BMH模式匹配算法[J].计算机科学，

2008.35（11）：164-165

[7] 姚保峰，王磊.一种改进的BMH模式匹配算法[J].湖南工程学院学报：

自然科学版，2011.3：40-42

[8] Yuan J， Yang J， Ding S. An Improved Pattern Matching Algorithm

Based on BMHS[C]//Distributed Computing and Applications to Business， Engineering & Science （DCABES）， 2012 11th International Symposium on. IEEE，2012：441-445

[9] 王浩，张霖.基于坏字符序检测的快速模式匹配算法[J].计算机应用

与软件，2012.29（5）：114-116

[10] Shrivastava G， Jain A. A Review of Intrusion Detection Method

Based On Automatic Pattern Matching[J]. Computer Engineering，2012.1（1）：88-90

[11] Chen Q， Niu Y， Wang Z， et al. Improved BM Pattern Matching

篇4

中图分类号：TP391.1 文献标识码：A 文章编号：1007-9599 （2013） 02-0000-03

1 引言

突发公共卫生事件应急系统的建立对于保障公共安全，建设社会主义和谐社会具有特殊重要的现实意义。目前国内外在应急响应领域已经取得了很大的进步，但对应急预案系统的研究才刚刚处于起步阶段。作为整个系统中最为基础和根本的一环，应急预案对于应急响应的实施具有重要作用。

本文通过对现有应急预案和应急响应过程的分析，通过框架技术对应急预案的知识进行表示，研究了预案的匹配算法，给出了预案相似度以及价值评估的计算方法。

2 智能预案匹配

应急预案是应急事件处置的领域知识来源。应急预案管理系统可以在对处置预案、资源分布转台、事件处置状态自动初步生成事件处置方案。再经过处置人员对初步方案进行调整，经过认可后即可作为高效地应急响应处理的指导方案。

2.1 基于框架的匹配

预案采用框架的智能化存储结构表示，预案的智能匹配自然和框架体系的匹配息息相关。基于框架体系的匹配系统一般由两大部分组成：

（1）由框架及其相互关联构成的知识库。提供求解问题所需要的知识；

（2）由一组解释程序构成的框架推理机。针对用户提出的问题，通过运用知识库中的相关知识完成求解问题的任务，给出问题的解；

2.2 匹配过程及算法

3.2 数据相似度研究

预案是介于数据与知识之间的一种知识存在形式，存储预案的框架结构具有不同数据类型的槽和侧面属性。计算不同数据类型属性的相似度，首先要讨论属性即槽值和侧面值的数据类型。一般来说，属性的数据类型分为以下三个大类。针对以上三大类型，分别来讨论其相似度算法。

4 结论

本文主要论述了智能预案框架表示与预案知识匹配机制。通过对现有应急预案和应急响应过程的分析，提出一个对应急预案的描述方法。利用框架结构完整的描述预案实体单元，依据各框架间的纵向联系和横向联系，从而形成框架网络。利用框架知识表示，研究了预案的智能匹配与相似度比对。最后讨论了预案相似度算法，给出了预案相似度以及价值评估的计算方法，讨论了预案框架中不同数据类型属性的相似度算法，重点研究了数值类型和文本类型的属性相似度算法。

参考文献

[1]Nilsson NJ. Artificial Intelligence： A New Synthesis[M].Copyrighted Matenal，2000.

[2]Sui YF，Gro Y， Cao CG.Ontologies， Frames and Logical Theories in NKI[J].Journal of Software，2005，16（12）.

[3]李晨阳，曹忠升，冯玉才.一种基于框架和中间件模型的知识库系统[J].计算机应用，2000（12）：1298-1300.

[4]张荣梅.基于CBR与MAS的智能决策支持系统研究及应用[D]：[硕士学位论文].北京：北京科技大学，2001.

[5]刘义刚.基于预案库的快速智能决策支持系统的研究[D]：[硕士学位论文].北京：北京理工大学，2001.

[6]杨健，赵秦怡.基于案例的推理技术研究进展及应用[J].计算机工程与设计，2008，29（3）：710.