匹配算法论文范文

匹配算法论文篇1

关键词串匹配，前缀函数，KMP算法

在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及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]傅清祥，王晓东.算法与数据结构[M].电子工业出版社，1998

[3]D.Wood，DataStructures，AlgorithmsAndPerfomance，Reading，MA:AddisonWesley，1993

匹配算法论文篇2

【关键词】藏文分词 匹配算法 哈希表 词典机制

1 引言

藏文信息处理存在着分词的问题，而藏文分词是对藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理的基础。藏文分词的效果会对进一步研究的藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理软件的性能和效果产生影响。

为了提高分词的准确率，需要有一个足够大的词库，面对足够大的词库，对词库中的词语的搜索技术就显得十分重要，对词库中词语的搜索速度直接关系到分词系统的性能。词库目前主要是采用索引的机制来实现的，一般用到的索引结构的包括线性索引、倒排表、Trie树、二叉树等。线性索引、倒排表都是静态的索引结构，不利于插入、删除等操作。

2 分词

2.1 词典机制算法

本系统采用的是基于Hash索引的分词词典。分词词典机制可以看作包含三个部分：首字Hash表、词索引表、词典正文。词典正文是以词为单位txt文件，匹配过程是一个全词匹配的过程。首先，通过首字Hash表确定该词在词典中的大概位置，然后根据词索引表进行定位，进而找到在词典正文中的具体位置。该系统是采用Myeclipse10平台，使用Java语言进行实现的，直接调用Java里的hashmap创建函数，找到该词之后，然后进行字符串匹配。

2.2 基于匹配算法分词

主流的分词方法有三种：分别为基于语言学规则的方法、基于大规模语料库的机器学习方法、基于规则与统计相结合的方法，鉴于目前藏文方面还没有超大型的句子语料库。该系统便采用了基于语言学规则的根据词典进行匹配的方法对藏文进行分词。

根据匹配的方向不同，分为正向和逆向两种匹配算法。本系统采用的是正逆向匹配算法相结合的减字匹配法对藏文进行分词的，因为藏文在每个字的结束时，都会以“”作为分界；每个句子会以“”或者“” 作为分界。因此，对藏文进行分词的减字算法首先以藏文的字符“”或者“”切分出句子，如此一来，原文就被分为相应的若干个句子了。接下来，再对每一个句子进行词典的匹配，如果没有匹配成功就根据藏文字符中“”从句末尾减去一个字符，然后再次进行匹配，直到匹配成功为止。对每个句子重复这些流程，直到每个句子全部分解为词为止。逆向最大匹配是从句子的末尾选择计算最大词的长度，从后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。

为了提高切分的精度，该系统使用的是正向最大匹配和逆向最大匹配相结合的方法进行分词，先分别采用两种方法分词，然后根据概率比较两种分词结果，选择概率较大的那种匹配算法作为分词结果。

本系统的逆向最大匹配和正向最大匹配均是采用减字匹配算法，减字算法实现简单，切分效果也比较理想，流程如图1所示。

正向最大匹配（MM） 对于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判别CD是否属于W，若是，则就切分为AB/CD，如果不是，则切分为AB/C/D。其中W 为分词的词典。逆向最大匹配对于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W为分词的词典，那么就取切分 AB/CD，根据藏文词组最长的为6个字符组成的，所以进行匹配算法的时候，初始化藏文最大字符串长度为6，流程图如图2所示。而逆向最大匹配算法是从句子的末尾开始进行匹配，其核心算法与正向最大匹配算法相同，只不过开始匹配的方向不同而已。

无论是正向匹配（MM）算法还是逆向匹配（RMM）算法都会产生大量的歧义字段。我们很容易举出这样的例子，如：（五十六个民族心连心）这一句藏语，采用正向匹配算法分词的结果为：，采用逆向匹配算法的分词结果为：，在采用逆向匹配的时候，将会被划分为，而（五十六）实际是一个词，不该划分，诸如此类的藏文句子还有很多，例如 等，无论使用正向最大匹配算法或者使用逆向最大匹配算法都会产生歧义，这种歧义称为组合歧义。为了减少这种歧义的影响，本系统使用两种分词方法相结合的方式。首先分别使用两种算法进行分词，然后通过统计的方法消除部分歧义。具体实现为：设正向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为；设逆向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为。如果，则选择正向最大匹配算法所切分的结果，反之，则选择逆向最大匹配算法所切分的结果。

3 结果和分析

结合26个大小不同的实验文本，对基于哈希表索引和匹配算法的分词系统的准确率进行了分析，准确率如图3所示。结果显示，该分词系统的准确率在92%以上。由此可得基于哈希表索引和匹配算法的分词系统在准确率上有不错的效果。

参考文献

[1]华却才让.基于树到串藏语机器翻译若干关键技术研究[D].陕西师范大学，2014.

[2]石方夏，邱瑞，张|，任帅.藏文信息隐藏技术综述[J].物联网技术，2014，12：28-32.

[3]王思力，张华平，王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报，2006，05：24-30.

[4]陈硕，桂腾叶，周张颖等.信息检索在论文写作和项目申报中的应用[J].科技展望，2015，13：274-275.

[5]黄昌宁，赵海.中文分词十年回顾[J]. 中文信息学报，2007，03：8-19.

[6]奉国和，郑伟.国内中文自动分词技术研究综述[J].图书情报工作，2011，02：41-45.

[7]贺艳艳.基于词表结构的中文分词算法研究[D].中国地质大学（北京），2007.

[8]戴上静，石春，吴刚.中文分词中的正向增字最大匹配算法研究[J].微型机与应用，2014，17：15-18.

[9]刘遥峰，王志良，王传经.中文分词和词性标注模型[J].计算机工程，2010，04：17-19.

作者简介

陈硕（1995-），男，西藏自治区拉萨市人。本科在读，主研领域为自然语言处理，数学建模及其应用。

周欢欢（1994-），女，湖南省衡阳市人。本科在读，研究方向为数学建模及其应用、交通运输规划与管理。

通讯作者简介

赵栋材（1976-），男，现为西藏大学藏文信息技术研究中心副教授。主要研究方向为藏文信息处理。

作者单位

1.西藏大学藏文信息技术研究中心 西藏自治区拉萨市 850000

匹配算法论文篇3

关键词：入侵检测；模式匹配；算法。

中图分类号：TP309.08 文献标识码：A 文章编号：1007-9416（2013）06-0135-02

1 引言

在基于主机入侵检测技术中，应用比较多的是误用检测技术，其核心多采用字符串搜索算法模式匹配技术。通过对目前广泛应用的BM算法[1]和AC_ BM算法[2]的分析，提出基于AC_ BM算法的改进的多模式匹配算法NAC_ BM算法。该算法综合了BM算法和AC_ BM算法的优点，改进了BM算法跳跃步长，使得每次匹配获得最大的步长，同时应用AC算法有限状态机模式匹配自动机构造模式树，匹配过程中移动模式树，减少了规则匹配次数，为基于主机的入侵检测模式匹配技术提供了一种优化方法。

2 多模式字符串匹配算法

由于BM算法是一种单模式字符串匹配算法，它每次只能完成对一个模式的匹配工作，效率较低。虽然研究者对BM改进算法很多，但是这些算法都没有改变BM算法的基本思想，因此不能解决效率问题。

为了提高效率，研究者提出了多模式匹配问题[3]，多模式匹配问题可以抽象描述为：设是一个模式集合，模式串Pi 中的字母来自于一个固定的字母表。多模式匹配问题是发现P中所有模式在文本T中的所有出现，。

3 AC_BM算法的改进—NAC_BM算法

4 仿真实验分析

为了对各个算法的性能、效率做具体的评测，在同一台计算机上分别对单模式匹配算法和多模式匹配算法进行了仿真测试。

在本测试中采用的搜索文件是来自麻省理工学院林肯实验室提供的“1999DARPA入侵检测测试数据集”[4]，长度为10000000Bytes的文本，而匹配的模式串是随机抽取的。

由于对于单模式和多模式而言，各有其不同的特点，比如对于单模式匹配算法，它的时

间开销与模式串的个数成正比，不能用它们解决多模式匹配的性能问题。而对于绝大多数多模式匹配算法都要在执行搜索操作前，对模式串集合进行预处理，构造某种数据结构，以便为搜索过程提供支持；相对于单模式匹配算法对空间需求可以根据模式串的长度而估算出来。本实验对匹配的模式个数对各种匹配算法性能的影响进行了仿真并给出对比分析。

图5中“*”号表示该项未测试。对于模式串为1（即单模式串）时，AC算法、AC_BM算法和NAC_BM算法没有必要测试它们对单模式匹配的性能。当模式个数大于1时，多模式匹配算法扫描对象文本一遍，而单模式匹配算法则要扫描对象文本多遍，即对每一个模式串扫描一遍对象文本。对于模式串个数为1000时，对单模式匹配算法是十分费时，且其耗费时间也可估算出来。

从图5的结果来看，多模式匹配算法比单模式匹配算法的匹配速度快得多。三种多模式匹配算法仍然比其他单模式匹配算法速度快，而且AC_ BM算法和NAC_ BM算法比AC算法快，这两个算法随着模式串数目的增加，所耗费的时间仅有很小的增加，而不是成比例地增长。从表中可以看出，NAC_ BM算法比AC_BM算法在效率上有一定程度的提高。

5 结语

本文提出了一种改进的AC_BM算法：NAC_BM算法。该算法一是在BM算法的基础上，改进了跳跃步长，使得每次匹配获得最大的步长，二是应用AC算法有限状态机模式匹配自动机构造模式树，匹配过程中移动模式树，减少了规则匹配次数。最后通过仿真实验对比得知：NAC_BM算法效率优于BM和AC_BM算法。

参考文献

[1]A Pattern Matching Model for Misuse Intrusion Detection[A]. Sandeep Kumar， Eugene Spafford. In Proceedings of the 17th National Computer Security Conference[C]，1995， 11-21.

[2]杨武，方滨兴，云晓春等.入侵检测系统中高效模式匹配算法的研究.计算机工程，2004，30（13）.92-94.

[3]李志清.基于模式匹配和协议分析的入侵检测系统研究.广东工业大学硕士学位论文，2007.4.20-26.

匹配算法论文篇4

关键词：毕业论文；KM算法；选题系统

中图分类号：TP311.52

1 引言

在现有的毕业论文选题系统中，一个学生只能选择一个题目作为自己最终的题目，同样，一个题目只能分配给一个学生。如果最后题目由学生自己确定，那就会出现先选的学生具有更大的选择余地，后选的学生由于不能再选已经选定的题目，所以其可选择的题目会越来越少，这对很多学生来说很不公平。如果学生选择自己的志愿，最终题目由老师来定，这不但加大了老师的工作量，而且还是不能保证每位同学的公平性。如何采用计算机智能辅助选题，设计最优匹配算法实现学生与题目的整体最优匹配，会大大提高选题的效率。

汤颖曾在《毕业设计立项与选题管理及其支持系统》中提出，采用模糊匹配技术进行学生-题目的自动匹配；潘志方在《一种改进的Ford-Fulkenson算法在选题系统中的应用研究》中将题目与学生的匹配抽象为二分图的匹配，并采用改进的Ford-Fulkenson算法实现题目与学生的自动匹配。以上两种方法只考虑了学生与题目之间的最大匹配值，并没有考虑学生的整体满意度最优的情况。

本文将通过采用最优匹配算法（KM）确定一种匹配方案，使得学生的整体满意度最高。具体方法概括如下：学生预选多个题目，并根据自己对题目的满意度由高到底排序，这样，满意度成为二分图的一分值，如图1所示：

2 系统功能模块设计

根据前期的可行性分析，本系统主要进行以下模块的设计：系统管理员模块、专业负责人管理模块、指导教师管理模块和学生选题模块。

系统管理员模块主要负责对系统参数的设置及用户的管理。主要实现以下功能：

（1）系统设置：对系统标题、毕业生、选题参数设置；

（2）学院及专业设置：完成学院、专业的添加、删除、修改操作；

（3）数据字典的维护：教师信息、选题难度、选题方向灯信息的维护；

（4）教师和学生的管理：完成教师、学生信息的添加、删除和修改操作；

（5）文件文化建设管理：日志文件查看、上传文件的管理。

专业负责人管理模块与系统管理员权限相似，但操作的数据只能针对于指定专业，无法浏览及操作整个学院的课题及学生信息。最重要的功能是实现题目的审核。

导师管理模块主要用于选题以及选择自己选题学生的审核确认。

（1）个人中心管理：如信息修改及密码重置；

（2）选题管理：选题的增加、修改、删除以及选题类型的设置；

（3）学生选题查询及审核。

学生模块主要实现学生选题的选择及确认。

（1）学生个人信息的修改；

（2）学生选题及确认信息查询；

（3）学生留言及咨询。

3 KM算法在系统中的实现

KM算法由Kuhn和Munkras分别提出来，这是一种问题。经典的算法。该算法由通过每个顶点一个顶标（A[i][j]）来求最大权匹配的问题转化为不断寻找增广道路以使二分图的匹配数达到最大的完备匹配。KM算法的关键在于不断寻找二分图中的可增广道路。如果找到一条可增广道路，就可以额将属于和不属于相等子图的边取相反，从而相等子图里就是增加一条边，一直到所有的顶点都进入相等子图为止。

KM算法可以很好地解决选题系统中，题目与学生最优匹配的问题。下面以国际商学院09级本科学生选题为例。

在匹配过程中，设学生的集合为X={X1，X2，X3……Xn}，选题的集合设置为Y={Y1，Y2，Y3……Yn}，学生对自己选题的满意度为二维矩阵Z[m][n]，其他题目规定权值为0。系统规定学生最多可预选3个题目，并按照满意度分别设置0.9，0.7，0.5。以下表1是对国际经济与贸易专业使用不同算法得出的学生满意程度。

下面对以上数据进行说明。如采用手工分配的方式，使得681名学生中414名同学分的了题目，满意度为60.82%；如果采用最大匹配算法进行分配，可以使分配数达到最大，有517名学生分得题目，满意度上升为79.99%；最有用最有匹配算法进行分配，使总体满意度达到78.24%，533人。需要说明的一点是，KM算法只是找到了整体最优匹配而不是最大数匹配，如果整体最优情况下匹配数和最大匹配数相差得太大的话，那么整体最优方案显得不太可取。所以，最好的情况就是同时考虑最优匹配和最大匹配来同时控制两者的大小。

4 结语

本系统实现了毕业论文选系统工作的各个管理功能，通过实现教师与学生的双向选择，使用KM算法，提高选题的质量和效率，为学院充分利用网络完成毕业论文选题工作提供了便利的平台。

参考文献：

[1]汤颖.毕业设计立项与选题管理及支持系统[J].合肥工业大学学报，2006，29（5）.

[2]潘志方.一种改进的ford算法在选题系统中应用研究[J].计算机应用与软件，2007，24（9）.

[3]杨凌云.基于.net的毕业论文选题系统的设计与实现[J].计算机时代，2010（03）.

匹配算法论文篇5

关键词：文献检索；快速排序；分治；字符串匹配；时间复杂度

中图分类号：TP391.9 文献标识码：A 文章编号：1009-3044（2014）02-0305-03

伴随网络技术的发展，网络信息大量增加，涵盖期刊、会议纪要、论文、学术成果、学术会议论文的大型网络数据库应运而生，如万方数据库、百度文库、维普数据库等，文献存储容量近百万篇。如何有效搜集发现信息，并对信息提取、组织、处理，就需要寻找出高效算法，降低计算复杂度，提高运算效率，以适应文献资源的迅速扩充[[1]]。

1 文献资料搜索引擎技术特点

当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到与用户要求内容相符的信息，便采用特殊的算法，根据文献中关键词的匹配程度，如出现的次数、频率等计算出各文献的排名等级，然后根据关联度高低，按顺序将这些资源接返回给用户。

与网络搜索引擎不同，因用户需求为数据资料而非网络资源，因此文献检索主要依据为相关关键词、内容的相关度等，对域名、外链等因素考虑较少。可利用关键词匹配算法，计算出各文献特征值，以特征值作为依据，对检索文献排序删选，满足用户需求。为便于理解，该文利用词频和位置加权算法计算特征值，采用快速排序算法进行整理输出，数据库可高效检索出与用户需求匹配程度较高的文献[[2]]。

2 快速排序算法规则及性能分析

快速排序是由托尼·霍尔于1962年（Tony Hoare）所发展的一种递归排序算法，采用分治的思想。在平均状况下，排序 n 个项目需要Ο（n log n）次比较。

其算法规则可表述为：

3 算法设计与仿真

首先建立包含十五篇文献的资料库，根据用户需求，随机输入关键词，在此可将关键词视为子串，对各文献进行字符串匹配操作。文献为A串，即目标串，关键词为B串，即模式串。若A串中存在和B相等的子串（ 若干连续的字符组成的子序列） ，则匹配成功，，否则，称匹配不成功[[3]]。

匹配过程如图2所示，将模式串设置为滑动窗口。在第一次匹配过程中，第三个字符出现不相同情况，此时根据KMP算法原则，利用已经得到的部分匹配的结果，将模式串窗口向后滑动一段距离后，继续进行比较[[4]]。

参考文献：

[1] 张兴华.搜索引擎技术及研究[J].现代情报，2002（2）：142.

[2] 黄知义，周宁.几类搜索引擎的原理剖析、比较研究及发展趋势探讨[J].图书馆学研究，2005（3）：61-62.

[3] 李静.字符串的模式匹配算法[J].青岛化工学院学报，2002（2）：80.

[4] 俞文洋，张连堂，段淑敏.KM P模式匹配算法的研究[J].郑州轻工业学院报，2007（5）：65.

[5] 黄德才，戚华春.PageRank算法研究[J].计算机工程，2006（2）：145-146.

[6] 王奇才，宋国新才，邵志清.信息检索中基于链接的网页排序算法[J].华东理工大学学报，2000（5）：456.

[7] 王海源.分治算法的两种思路和形式[J].上海师范大学学报：自然科学版，2003（1）：40-41.

匹配算法论文篇6

关键词：框架；智能预案；相似度；匹配算法

中图分类号：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.

[7]魏元凤，骆洪青，辛崇波.属性相似案例的检索模型比较研究[J].华东船舶工业学院学报，1999，13（4）：41-44.

[8]Satoshi S， Francis B， Yamato T. A hybrid rule and example based method for machine translation[C]. Proceedings of the 4th Natural Language Processing Pacific Rim Symposium，Puket，1997.

匹配算法论文篇7

关键词：KMP；改进；模式匹配算法；字符；分析；算法

中图分类号：TP309

随着计算机技术的不断发展，需要处理的数据内容不断呈现出大量化的特点。近年来，在计算机研究领域内模式匹配问题受到了极大的关注。在串处理系统中，子串在主串中的定位操作是一种重要的过程中，称之为串的模式匹配。随着计算机网络搜索引擎技术的发展、病毒技术的进步以及数据压缩方面的不断发展，模式匹配算法在计算机应用系统中得到了广泛的应用。目前主要的匹配算法有BF算法、KMP算法与一些改进的算法，从方式上，可以分为精确匹配、模糊匹配、并行匹配等。本文重点对KMP算法进行分析，另外对于改进的KMP算法进行研究与展望。

1 简单的模式匹配算法

现代计算机技术不断发展，人们的工作、生活与互联网有着密切的联系，同时网络内容也不断丰富，每一个终端几乎都有可能会上传与下载数据，造成网络上的类似相信也非常多，如何能够从大量的信息中进行查找同样的信息，则需要经过一定的算法。[1]这种典型的应用系统将会使用到匹配算法。简单的模式匹配算法主要是一种查找过程，给出一个特定的字符串P，在一大型的文本中进行查找，从而确定出P是否在大型文本中出现过，如果存在，同时给出相应的出现位置。在以上的算法定义中，为了对数学模式进行简单描述，进行以下符号定义。模式串为P，需要匹配的大型文本主串为T，模式串的长度为m，需要匹配的大型文本主串长度为n，在模式串中首字符与末字符分别为P1与Pm，而需要匹配的主串文本首字符与末字符分别为T1与Tn。文本字符串T与模式字符串P分别是由字符组成的一种集合，强行搜索模式实质上就是把模式P与文本T进行自左向右的挨个搜索，如果模式字符串P在某一点的匹配失败，则立即将T向右移动一个字符的位置，继续从模式字符串P的第一位向右来搜索。[2]这种算法基本上是最符合原理的，但同时它的工作量十分巨大，体现出的效率并不高，需要进行m（n-m+1）次的字母匹配运算，往往给过程浪费大量的时间。现代社会是高效社会，一旦在网络搜索中速度过慢，用户将会失去耐心。目前更多的手持设备在应用搜索时一般是即时搜索，对时间的要求较高，运算量太大的低效搜索模式已经不再满足现代需求。每个网站的用户数量都在不断增大，形成的用户名与密码都需要进行数据储存，利用模式匹配法可以对账户与密码进行匹配，从而判断是否可以登入，否则就进行拒绝，有效提高时间，保护网站利用与用户隐私。这是模式算法的典型应用，随着算法的不断进步，将会在多个网络领域内得以广泛应用。[3]

2 KMP算法

KMP算法目前已经经过了多年的发展，最早是由克努特、莫里斯与普照拉特同时发现，是一种改进的字符串匹配算法，在这种算法中，对主串指针回溯进行了消除，利用已经得到的部分匹配结果把模式串右行一段较远的距离，再次进行比较与匹配，从而使算法的效率得到大幅地提升。这主要是因为在前期的匹配过程经验总结中，一旦某字符不符合模式串的匹配要求，在附近的一段文本中也将不会出现匹配的对象。[4]

KMP的算法思想是当Ti与Pj匹配完成时，主串的指针i与模式的串指针j将会分别加1，不断向后面进行再次匹配，如果Ti与Pj匹配不成功时，主串的指针i保持不动，模式的串指针j将不会回到第一个位置，而是回到一个合适的位置，一旦j回到了第一个位置，将有可能会对需要匹配的文本字符进行错过。主串的指针i保持不动时，算法的关键就在于模式的串指针j指回到了哪一个位置。模式的串指针j不可右移太大的距离，避免错过有效匹配，同时也要右移尽可能地大，以提高匹配效率。在某次字符匹配时，一旦不匹配，模式的前j-1个字符能够匹配，则在下一次匹配时，可以把模式串向右移动j-s-1个字符位置，从而使P1与Tj-s对齐，需要从P3+1开始进行匹配情况检查。为了避免遗漏问题，在以上的首字串必须是最长的，自匹配的部分字串是唯一的，与模式自身结构有关。当模式的第j个字条与主串里的该字符进行比较位置时，它的值主要是取决于模式本身，与主串无关。这时关键是要选择模式的适当位置。

3 改进的KMP算法

模式匹配的KMP算法有效地避免了BM算法中频繁回溯的问题，极大地提高了模式匹配的效率，但这种算法并不是最优秀的。经过长时间的探索与分析，KMP算法中的扫描部分仍然可以进一步改进。[5]

在改进的KMP算法中，当某一次匹配失败时，i指针不需要进行回溯，而是使用已经匹配到的结果，查看是否对i的调整进行必要性评估，之后再决定与向右滑动的位置模式进行比较。主串指针i的有效变化可以有效提高匹配的效率。在进行第一次匹配结束时，j=6处，无法进行匹配时，i指针将会定为6，j指针为6，当模式串向右移动三个位置时，开始进行第二次的匹配，i的指针为9，而j的指针值为3，也就是说从主串的第九位开始进行比较，i值的不断增加也就加快了模式匹配的进度，提高了工作效率。

4 利用改进算法进行多次模式匹配

与单模式匹配算法相比，多模式匹配算法的优势在于一趟遍历可以对多个模式进行匹配，从而大大提高了匹配效率。对于单模式匹配算法，如果要匹配多个模式，那么有几个模式就需要几趟遍历。当然多模式匹配算法也适用于单模式的情况。在入侵检测系统中，一条入侵特征可能匹配或部分匹配很多条规则，如果采用单模式匹配，在匹配每条规则时都需要重新运行匹配算法，效率很低。然而，日益增多的网络攻击使得入侵检测的规则数目仍在不断增长。

在实际的应用中，模式串与主串一般需要多次的匹配，才能找到主串中是否有多次存在相同的子串，如在数据库中进行查找。[6]通过多次模式的匹配可以实现多个子串在文本中的位置，同时可以进行标记，有利于现代计算机庞大数据量的数理与分析。我国人口众多，网民数量庞大，姓名与用户名很可能会出现重复的情况，所以需要提前在数据库中进行查找，以确定是否可用，另外对匹配但其他特性不符的对象进行排除。

5 结束语

随着现代计算机技术的不断发展，越来越多的新技术得以应用与改进。网络安全发展形势也要求提高网络入侵检测系统的性能。模式匹配的效率问题引起了足够的重视。通过对传统的KMP模式匹配算法与其发展状况进行分析，明确未来发展思路，为其实践应用奠定理论基础。

参考文献：

[1]李桂玲.一种改进的KMP模式匹配算法[J].吉林工程技术师范学院学报，2009（10）：75-77.

[2]杨战海.KMP模式匹配算法的研究分析[J].计算机与数字工程，2010（05）：38-41.

[3]陈冬文，张帆，王斌，周启海.模式匹配算法――KMP算法的改进[A].2008中国信息技术与应用学术论坛论文集（一）[C].成都：西南财经大学信息技术应用研究所，2008.

[4]明廷堂.BF与KMP模式匹配算法的实现与应用[J].电脑编程技巧与维护，2013（23）：24-28+34.

[5]范洪博.快速精确字符串匹配算法研究[D].哈尔滨：哈尔滨工程大学，2011.

[6]赵森严，黄伟，李阳铭.一种改进的KMP入侵检测的模式匹配算法[J].井冈山大学学报（自然科学版），2013（01）：55-57.

作者简介：张燕飞（1992-），男，江苏泰兴人，本科，计算机科学与技术专业；李亚琼（1992-），女，贵州凯里人，本科，计算机科学与技术专业。

匹配算法论文篇8

Shang Peini；Wang Jianqiang

（School of Information Engineering，Yulin University，Yulin 719000，China）

摘要：分析了毕业论文选题系统的特点，引入了学生及指导教师对选题结果的满意度，建立了一个以总体满意度最大为目标的毕业论文选题系统模型，并在此基础上设计实现了基于web的本科毕业论文选题系统。实际应用表明，该系统可以有效的提高毕业论文选题的总体满意度及选题质量。

Abstract: The thesis analyzed the characteristics of graduation projects' selection system, introduced the satisfaction of student and instructor with the results on the topics, established a model of graduation projects' selection system which took the overall satisfaction as the goal, and on this basis, designed and implemented graduation projects' selection system for undergraduates based on web. The application showed that this system could effectively improve the overall satisfaction of thesis topics and the quality.

关键词：满意度 毕业设计 选题系统 web

Key words: satisfaction；graduation project；selection systems；web

中图分类号：TP39 文献标识码：A文章编号：1006-4311（2011）29-0147-02

0引言

毕业设计（论文）是高校培养学生的重要环节，随着高校的扩招，毕业论文选题的工作量也越来越大，以往的手工选题的方式已经远远不能满足高校毕业论文选题的需求。一个有效的方法是采用计算机智能选题系统，在毕业论文选题系统中，一个学生只能选择一个题目作为自己的最终论文题目；同样，一个题目也只能分配给一个学生。如果最终题目由学生自己确定，那么就会出现这样的情况：先选的学生具有更大的选择余地，后选的学生由于不能再选已经选定的题目，所以其可选择的题目会越来越少，这对很多学生来说是很不公平的。如果学生选择自己的志愿，而最终题目由老师来定，这不但加大了老师的工作量，而且还是不能保证每位同学的公平性。如果采用计算机智能辅助选题，设计最优匹配算法实现学生与题目的整体最优匹配，无疑将大大提高选题的效率。

一些学者曾对题目的智能化匹配作过比较深入的研究，如汤颖采用模糊匹配技术进行学生一题目的自动匹配[1]；潘志方将题目与学生的匹配抽象为二分图的匹配，并采用改进的Ford-Fulkenson算法实现了题目与学生的自动匹配[2]；杨胜超等将学生的满意度引入到了毕业论文选题中[3]。但是，他们只是考虑了题目与学生的最大匹配数，并没有同时考虑学生和教师整体满意度最优的情况，而教师的满意度往往对选题质量的控制起着关键作用。

本文在毕业论文选题系统中引入了学生和教师的满意度，建立了在最有匹配基础上的以满意度最大为目标的选题系统模型，给出了算法实现并将其应用到了本科毕业论文选题系统的设计中，最后给出了毕业论文选题系统的具体实现，并进行了实际测试。测试结果表明，该选题的应用可以提高选题的总体满意度和选题质量。

1选题系统最大满意度模型

设S为学生的集合，有sm属于S，m属于[1，M]，其中M为学生数。设T为题目的集合，有tn属于T，n属于[1，N]，其中N为论文题目总数。那么对于所有的选题情况有集合Anm，对于某一具体选题，学生满意度Xnm，教师满意度Ynm，那么Xnm+Ynm有最大值，max(Xnm+Ynm)。因此，该问题变成了求解满意度最大值问题，并能确定在取得最大值情况下Anm的集合，也就是具体的每一个学生的对应的唯一的选题。

2毕业论文选题系统的设计实现

2.1 系统用例该系统的用户主要有三类，分别是系统管理员、普通教师和学生，系统用例说明如表1所示。

2.2系统流程设计基于最大满意度的毕业设计选题系统，充分考虑了学生确定自己论文题目的自由性：学生可以自主命题由老师来审核，如果审核通过则可作为自己的最终论文题目，如果未通过审核还可以反过来参加预选或者再次自主命题（有最大自主命题数限制）。同时将教师对选题情况的评价引入，更加合理。同时还优化了题目预选的匹配：通过管理员启动最大满意度匹配算法，确定出学生与题目的最优匹配方案，这样便大大减轻了老师的工作量，提高了选题的效率。最后，如果通过以上两个步骤还有学生没有定题，就只有通过老师手动确定学生的最终题目。

2.3 系统数据库设计基于前边的分析设计，我们需要设计到下列各表，这些表之间相互关联，共同存储着系统所需要的数据。在设计数据库表的过程中，应遵循以下几条原则，数据库设计一个表最好值存储一个实体或对象的相关信息，不同的实体最好存储在不同的数据表中，如果实体还可以再分，实体的划分原则是最好能够比当前系统要开发的实体的颗粒度要小，数据表的信息结构一定要合适的，表的字段的数量一定不要过多，扩充信息和动态变化的信息一定要分开在不同的表里，对于多对多这样的表关系系统尽量不出现。该系统中主要的数据表如表2-表5。

普通教师参数表保存的是用户参数，UserID是用户注册时输入的，作为该表的主键，表中记录的用户编号是不会相同的，这要求在用户注册时检查欲注册的用户名是否已经被注册过，这是必要的一步。（故部分系统在注册时要求用个人Email地址作为用户ID，这样重复的几率非常低，但也是需要检查的。）且UserID在其他表中也会用到。（表2）

学生参数表保存的是用户参数，StID是用户注册时输入的，作为该表的主键，表中记录的用户编号是不会相同的，这要求在用户注册时检查欲注册的用户名是否已经被注册过，这是必要的一步。（表3）管理员参数表是管理员的一些注册信息，其中Adminid是管理员编号，是该表的主键。其余各字段与普通教师参数表中的字段意义相同。（表4）

题目信息参数表是信息的各种参数，包括题目的编号（系统自动生成），是该表的主键。题目的详细内容是对该题目的简单介绍，题目类别根据需要进行设置。（表5）

2.4 系统实现最后，系统采用asp+access进行了实现，具体实现过程由于篇幅所限，不再赘述。

3系统测试

该系统设计完成后，在榆林学院信息工程学院2010届本科毕业生的毕业论文选题过程中进行了实际的测试，测试数据如表6。

在此次测试中，共有学生96人，题目107个，从表中可以看出，采用手工分配方案，只有74个学生可以分得选题，而采用智能最大满意度方案，有91人分得了选题（其余学生采用手工分配）；在满意度方面，采用最大满意度方案后，学生的整体满意度和教师的整体满意度均有较大提高。

4结束语

按照以上描述的设计思路和算法，采用Asp技术+Access后台数据库实现了毕业论文选题系统。该系统将选题结果学生和教师整体满意度最大作为目标，不但大大降低了整个选题过程的工作量，而且大大提高了学生及教师对选题结果的整体满意度，从而提高了选题质量。该系统在榆林学院信息工程学院2010届计算机科学与技术专业本科毕业生的毕业论文选题中进行了应用，取得了良好的效果。

参考文献：

[1]汤颖.毕业设计立项与选题管理及其支持系统.合肥工业大学学报(自然科学版)，2006,29(5):613-616.

[2]潘志方.一种改进的Ford一Fulke~算法在选题系统中的应用研究.计算机应用与软件，2007,24(9):120-121.