匹配算法论文范文1
关键词：毕业论文；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）.
匹配算法论文范文2
关键词：图检索；图匹配；遗传算法；图数据
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）01-0088-04
1 概述
信息技术地不断发展出现了越来越多的以图作为逻辑表达的数据，例如城市规划中的建筑模型、化学分子结构式，生物网络，社会网络图中的实体关系和图像检索等等。从图数据中发现有用的知识已成为图数据查询领域一项重要的研究课题。图查询是其中最重要的一个研究分支，因为与图有关的绝大部分应用（例如：图查询、图分类、图聚类等）都需要利用图来管理、查询和分析图数据。
对于在大量累积的图数据（即图数据库）上进行查询处理的问题，已有的对图数据库查询处理的研究工作主要包括两大类：一类是在小尺寸图的大规模集合（简称为集合类图数据库）上处理查询，其中包括子图查询处理、超图查询处理和相关子图查询处理等；一类是在一个或为数不多的大尺寸图（简称为大图类图数据库）上处理查询，如子图匹配查询处理、可达查询和最短路径/距离查询等。然而，这些方法全部针对确定图数据，无法应用到不确定图数据的查询处理中。对不确定图数据库中多种查询类型（如子图匹配查询）的高效处理是一项具有挑战性的工作.因此对图数据的查询处理方法的研究具有现实意义和理论价值，有待探索.
虽然遗传算法是非常优秀的智能优化算法，但是目前大多数应用都可以归纳为解决路径问题，比如TSP问题，而将其与计算机数据的图数据匹配的研究还很少[6]。
本文针对不同的拓扑结构图，对两个图是否相似的过程采用遗传算法进行讨论，对于种群进化的过程思路进行拓展研究，在算法复杂度上对比现有的深度优先搜索、宽度优先搜索等算法得出遗传算法应用于图匹配问题的新解。
2 问题的定义
匹配算法论文范文3
关键词 中文分词 哈希查找 二分查找
中图分类号：TP391 文献标识码：A
一、解决问题的思路
在高效字典中，在同样首字下的词条，在内存中是按照汉字内码大小排列的。在词典中匹配成功某个字串后，会在其后面增加一个字即得一个新的字串，如果新字串在词典中出现了，那么新字串一定在原字串后面，且相隔的位置不会太远。近邻匹配算法基于这一特点设计的，使用这种算法避免了每增加一个字就要重新在字典中从头开始匹配的冗余操作，是一种高效的分词算法。该算法的分词过程如下：
1、将词库读入内存。这是读入词库切词的第一步，为了提高整个切词的速度，可将整个词库一次性读入内存，并常驻内存。
2、读入要切分的中文文本数据。对于待切分的文本数据按行进行处理，每处理一行，就要先将字符数据读入缓冲区，并进行相应的字符集转换。
3、从缓冲区中读取搜索字串P=C0C1C2……CL-1。（L为字串长度），根据待搜索字符串P的首字C0，可以根据计算出的C0相应的索引项Ii的地址，并得到以C0为词首字的词数n及指向所有词条：W0W1……Wn-1的指针Pi。如果说，这个字不能成词，那么就退出。
4、在词表中查询中，前两个字形成的子串CoCl，得到索引index，然后在index之后寻找最长且完全匹配的词条。
5、如果当前匹配长度小于最大匹配长度或词表中的词条比字串大，结束寻找过程，然后用同样方法切分下一词条。
算法实现如下：
Neighborhood Matching
{
int totalOffset=0；
int strLen=strlen（P）；
while（totalOffset
int
result=-O；
//计算索引项的地址
Unsigned char q=*P；
unsigned char w=*（P+1）：
q-=0xB0；
W-=0x A1：
Char**Pi=ptrArray[q][w]；
int n；//词条数；
int index=FindWord（4，（char*）C0C1，&result）；
if（index==-1）{
/*没找到）C0C1，还不能确定它是某个词条的前缀还是应分开*/
start=result+l；
}else{
start=index+l：
matchMax=l；
}
int offset=2；∥跳过首字
int bContinued=l；∥是否继续查找标志
while（start0）{
bContinued=l；
Char *wordPtr=Pi[start]；
int wordLen=strlen（wordPtr）-2；
if（*（P+offset）！=*wordPtr ||*（P+offset+1）！=*（wordPtr+1））
break；
i=2；
while（i
if（*（P+offset+i）==*（wordPtr+i））
i++；
else{//如果字串比词条小，退出当前循环
bContinued=*（textPtr+offset+i）-*（wordPtr+i）；
break；
}
}
//完全匹配
if（i==wordLen）{
i>>=l；
if（i
break；
else matchMax=i；
start++；//准备匹配下一词条
//处理下一个词
offset+=matchMax
P+=offset；
TotalOffset+=offset）
}
}
}在上述算法实现的切分情况，在切分“中国人民成功守住了大堤”时，词表中以“中一开头的词有100多个，以“中国"开头的词有“中国人民”、“中国青年”、“中国银行"、“中国政府”，找到“中国”后，在其后找“中国人民”一词，只需两次词条匹配操作即可。
由于本文采用的是词表结构支持首字Hash和标准的二分查找方法，避开了词表访问过程中的I/O操作，并且在分词过程中采用近邻匹配算法，大大降低了时间复杂度，根据表3-1的统计数据，单字词的出现频率约为56.75%，二字词的出现频率约为39.65%，二字词以上的词的出现频率为3.6%，每个首字下的平均词数为12.35，该算法时间复杂度计算如下：
查找单字词无需匹配。
查找一个两字词的平均匹配次数为：
0.3965 ？log2n = 0.3965 ？log212.35 ≈ 1.44
查找一个三字词或高于三字的词平均匹配次数：
（1-0.5675-0.3965） ？n / 2 = 0.036 ？13.35 / 2 ≈ 0.22
利用这种算法，假设有12万条词库的基础上，在P42.0GHz的电脑，lG内存的平台下，1.2MB的文本在最大匹配算法的状态下，所需时间约为1.0 ～1.1s，在同类算法中是比较优秀的。
二、分词算法准确性测试
为了检验本论文采用的分词算法的准确性，本论文采用了两段文字进行测试：
源文件：中文信息和英文信息相比，有一个明显的差别，英文单词之间用空格分隔；而在中文文本中，单词之间没有天然的分隔符，中文单词大多是两个或两个以上的汉字组成的，并且，语句是连续的，这就要求在对中文文本进行自动分析前，先将整句切割成单词单元，即中文分词。
分词结果：中文/信息/和/英文/信息/相比/有/一个/明显/的/差别/英语/单词/之间/用/空格/分隔/而/在/中文/文本/中/单词/之间/没有/天然/的/分隔符/中文/单词/大多/是/由/两/个/或/两/个/以上/的/汉字/组成/的/并且/语句/是/连续/的/这就/要求/在/对/中文/文本/进行/自动/分析/前/先将/整/句/切割/成/单词/单元/即/中文/分词
三、结论
通过试验得知，本论文采用的分词算法分词精确率达到95%，分词速率快，基本满足了一个中大型搜索引擎的需要。
（作者：桂林电子科技大学工程硕士在读，本科学士学位，研究方向：垂直搜索引擎，中文分词）
参考文献：
[1]刘开瑛，吴伟民.中文文本自动分词和标注.商务印书馆，2000.
匹配算法论文范文4
关键词：入侵检测；模式匹配；算法。
中图分类号：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.
匹配算法论文范文5
关键词：堆栈；最大匹配法；分词算法
中图分类号：TP393.03 文献标识码：A文章编号：1007-9599 (2011) 08-0000-01
Network Information Retrieval Stack,Maximum Matching Automatic Segmentation Algorithm Study
Zhang Haiying
(Xiangfan University,Xiangfan441053,China)
Abstract:This paper analyses the shortcoming of segmentation algorithm.Designs a new algorithm for Chinese phrase segmentation based on stack.And also introduces the framework of the model,describes the detailed procedures.
Keywords:Stack;Maximum match method;Segmentation algorithm
自动分词问题是搜索引擎的核心问题，本文针对该问题，在对现有的分词算法分析研究的基础上，结合最大匹配分词法（MM法）和堆栈技术理论，提出了堆栈－最大匹配自动分词模型，该分词算法在对文章中的词进行自动切分时，具有良好的效果，实现了对MM分词算法的进一步改进。
一、机械分词方法和堆栈技术理论
机械分词方法的思路是先查词库进行匹配，然后再适当利用部分词法规则进行歧义校正。机械分词法之所以称之为“机械”，是因为它的切分过程是依赖于词库进行。词库中词条的数目、词条的选择直接影响到最后的分词效果。机械分词法加歧义校正属于机械分词法的一种改进，它主要利用词法规则对歧义进行校正，以提高切分精度，事实证明这种改进是有效的，而且这种改进最终导致了知识分词方法的出现。目前属于机械分词领域的分词方法主要有：最大匹配法、高频优先分词法、双向扫描法等。其中最大匹配分词法是机械分词方法的典型代表。
二、堆栈－最大匹配自动分词模型构建
堆栈-最大匹配自动分词技术主要是结合最大匹配分词法和堆栈技术对文章中的词进行自动切分，是对最大匹配法的改进。基于最大匹配自动分词的思想，结合堆栈技术理论，我们可以得出：最大匹配法重视的是字符长度，如果遇到在分词过程中后面字符串出现不可分的情况，能自动弹栈回退，并且重新检索出另一个成功匹配的词作为分词结果，就有可能解决后面字符串不可分的窘境。所以堆栈－最大匹配自动分词模型构建基本设计思想是：
首先按照文章中的标点符号将文章内容切分成语义块，每个语义块就是一个字符串，针对每一个字符串作循环。每次只处理一个汉字，将该汉字假设为词首，并且在词库中检索以该汉字为词首，检索该汉字后的字符匹配。根据检索出来的词作为分词结果的备选项，按长度排列，首先取出长度最长的那个词，即最大匹配，假设这个词就是以该汉字为首的分词结果，加入到这个语义块的分词结果栈中，然后继续该词语位置之后的下一个汉字的处理。在该方法实现的过程中，笔者将语义块中已经分词成功的那部分字符串在压栈的同时，从语义块中去掉。如果分词结果栈中出现分词歧义需要弹栈时，将弹出的结果加在原来语义块字符串的首部。这样就不需要在每得到一个分词结果后计算下一个即将处理的汉字的位置了。
三、堆栈－最大匹配自动分词算法
根据堆栈－最大匹配自动分词方法的基本思想和模型，形成了相应的堆栈最大匹配自动分词算法。堆栈－最大匹配自动分词的核心算法如下：
①在现有的句子中以标点符号为标界，且分成多个语义块block，存为字符串数组；设置另一个字符串数组result，存放单个block的分词结果；设整型数组undone，用来记录不可分的汉字的出现位置。②循环字符串数组，对数组中每个语义块block进行步骤③，直到整个字符串数组被处理完毕。③对单个的语义块每次都是从block的首个汉字开始进行分析，执行下一步；④如果result的总长度与原语义块的长度相等，或者是block的长度为零，说明该语义块分词完毕，执行步骤⑩；当分词过程遇到该汉字时，将该汉字暂时略过；执行步骤③；⑤取singleword=block.SubString（0，1），继续；⑥在词语表中查找以singleword为首词语，存为一个字符串数组temp，作为分词的备选项，继续以下判断；⑦如果temp的长度为零，即if（temp.Length==0），则说明不存在以该字为首的词语；比较该汉字的位置是否在不可分数组undone中有记录，如果有则略过该汉字，执行步骤③；⑧如果temp的长度为1，即if（temp.Length=1），只有一个分词结果备选项，那么该结果就是所要的分词结果，该词语压入分词结果栈中result数组中，执行步骤③；则说明在词语表中从block首部取出；⑨如果temp的长度大于1，即if（temp.Length>1），则说明分词结果备选项中存在多个结果，按照temp数组中的字符串长度的次序由小到大排列，取数组最后一个元素的字符串，在block首部去掉该词，压入分词结果栈result中，执行步骤③。⑩如果不可分数组undone不为空，则对数组中的元素和分词结果中的元素进行人为干预，将新词录入词库，执行下一步；⑪开始下一个语义块的分词，将上一个语义块的分词结果输出，并且将分词结果栈result清空，执行步骤②。
四、自动分词举例
假设在文章的句子中，已经有了切分好的语义块。例如，有一句话“这些学生会员都来了”。词库中已经有以下的词语了：这些、学生、学生会、会员、都、来、了
那么，应用上述的自动分词算法，依次对该句的汉字进行分析，其详细过程如下：①检索“这”，发现“这些”在词库中并且与原文匹配；②检索“学”，发现有两个匹配，分别是“学生”和“学生会”，取字符长度最长的那个匹配项“学生会”；③检索“员”，发现词库中没有以“员都”或“员”这样的词语，因此不存在匹配，于是将先前的栈顶元素弹出，压入第二长的分词备选项“学生”：④检索“都”，这是一个副词，在词库中；⑤同理，“来”和“了”依次被分出来。
实践证明，利用该分词算法进行自动分词，其分词复杂度得以大的改善，该分词算法在对文章中的词进行自动切分时，可以大大降低分词过程中的匹配次数，提高了分词的响应速度，尤其适合大量中文信息的分析与处理。
参考文献：
[1]揭春雨,刘源,梁南元.论汉语自动分词方法[J].中文信息学报,1989,3(1):101-108
[2]孙巍.一种面向中文信息检索的汉语自动分词方法[J].现代图书情报技术,2006,139(7):733-736
[3]吴绍根.汉语自动分词模式自动机构造研究[J].现代图书情报技术,2006,136(5):551-553+565
匹配算法论文范文6
关键词：P-集合；概率分布；模式匹配
中图分类号：TP301.6
1 背景
在网络中，网络安全设备，需要对网络中海量的、复杂的数据包进行匹配分析，如何快速的从海量数据中提取出需要的特征信息，已经成为目前信息安全的重要课题。体现到实际网络环境中海量数据包中的入侵行为的显现，是多种特征数据包动态变化的过程。同时网络数据包集本身的基本属性是不变的，只是增加或减少了部分具有特征恶意的数据包，随着时间的推移各种可能入侵行为的产生，数据集本身的状态也在动态迁移中，对数据包的匹配检测而言，并不关心数据包集本身，其最想了解的而是数据动态迁移的过程。综上所诉我们发现数据包集生产过程是动态的过程且具有可描述性、随机性等特征。本文希望通过对P-数据包集合的特征分析，对海量数据包集进行过滤预处理筛选出可能存在特征模式串的文本区域，以提升模式匹配速率和匹配命中率。
2 基于P-集合的筛选过滤多模式匹配算法设计
不妨设发生异常入侵情况数据包集的具有的特征集：
其中α1α2α3……αn分别对应的具体的异常属性有出口设备流量突然增大，核心交换CPU突然增大，核心交换内存使用突然增大，出现大量异常小数据包，出现长时间的端口扫描行为等症状属性，针对这些症状和现象在我们的入侵检测系统有对应的匹配检测手段，即通过模式匹配进行检测，其特征模式串及字符串中的字符集：
通过对不同特征模式串的尝试可以使特征集α中的相关现象得以缓解。
当我们α=>0则我们找到了最优的解决方案，但是在发现最优解决方案的之前我们并不知道使用哪种特征模式串组合是我们需要的，即初始状态下元素迁移的概率s1的情况下：
，
为最优筛选-过滤数据集。
通过上面的实验及讨论，分析了整个模式串ρ与算法效率的关系，显然存在当ρ则有ρ（pi）。参考P-集合最优数据筛选-过滤数据集思路：在精确多模式匹配的时候先对数据集进行筛选-过滤，通过最优数据筛选-过滤定理选择最优模式串及字符串组合对数据集进行筛选-过滤，然后在精确匹配的算法设计思路。
又因为：
也就说ρ是由ρ（pi）与其条件概率共同决定的。
ρ（pi）对算法又有什么影响呢？结合AC和WM算法的分析，做如下工作：
以AC算法为例，不妨设状态机及其模式串字符间的概率如下图所示：
所以选择条件概率最小的那个作为特征点，可以减少匹配查找的时间。
由上图可得可以选择A距离为2的C作为共同作为特征点先查找匹配。则根据以上条件设计如下算法：
第一步：
初始化：根据特征字符集的特征字符选择K个有限的字符组合组成新的特征模式串。
第二步：
参考Pi条件概率选取K个Pn…作为模式串的查找序列；如果存在有限状态机存在分支且存在较小的Pn…；则分别且至少每分支上选取上一个Pn…组成新状态机的分支。
第三步：
参考最优数据筛选-过滤定理，对数据集进行筛选-过滤，记录数据集筛选-过滤后的属性集： ，得到最优模式串及字符串组合。如上图最优的字符串组合为A和C。
第四步：
记录Pn…与Pi的间隔字符数n-i=d；即A与C的间隔为2。
第五步：
通过Pi与Pn…组成新的序列通过AC算法比较若成功跳到第四步即AC组成新的有限状态机如图
第六步：
分解原状态机后精确匹配；
3 实验分析
实验条件：
设当字符集大小|Σ|=256，模式串长度m=8字节，模式串个数r=500，文本长度n=1M字节时，在完全随机生成数据。
设分别ρ以{0，0.01，0.02，0.03，0.04，0.05，0.06，0.07，0.08，0.09，0.1}取出模式串以随机的方式分散替换到文本串中。
字符间固定存在如下的ρi{0.1，0.001，0.04，0.03，0.02，0.008}作为字符间的条件概率分布。根据选择与Pi条件概率较小K个Pn…作为模式串的查找序列；如果存在有限状态机存在分支且存在较小的Pn…；则分别且至少每分支上选取上一个Pn…组成新状态机的分支，生成新的模式串查找序列。
本实验从特征模式串及字符串中的字符集中 ，固定只选取2个字符组合作为筛选-过滤参考条件。
实验1：
当选择ρi=0.1的两个字符组合则有得到如下表的实验结果：
通过上表分析：
（1）在ρ较小的情况下WM可以更快的发现随机分布的模式特征串。
（2）随着ρ，AC模式匹配算法匹配过程中性能稳定。
（3）改进模式匹配算法在ρ较小的情况下可以较快发现随机分布的模式特征串；同时随着ρ，算法匹配过程中改进算法性能更加稳定。
实验2：
当选择ρi=0.001的两个字符组合时则有得到如下表的实验结果：
通过上表分析：
（1）在ρ较小的情况下改进算法可以更快的发现随机分布的模式特征串。
（2）随着ρ，改进算法和AC算法模式匹配算法匹配过程中性能稳定。
（3）改进模式匹配算法在ρ较小的情况下可以较快发现随机分布的模式特征串；同时随着ρ，改进算法匹配过程中性能更加稳定。
（4）实验2与实验1在不同ρi的条件概率下，在ρi=0.001是可以的更快的发现随机分布的模式特征串。
实验3：
通过上表分析：
（1）随着ρ，改进算法在整个匹配过程中性能稳定。
（2）改进模式匹配算法在ρ较小的情况下可以较快发现随机分布的模式特征串；同时随着ρ，模式匹配算法匹配过程中性能更加稳定。
（3）通过实验1实验2实验3针对ρi{0.1，0.001，0.04，0.03，0.02，0.008}字符间不同的条件概率我们发现当选取ρi较小时可以更快的发现随机分布的模式特征。
4 结论
当发生异常数据包入侵事件时，大部分入侵事件都具有目的性、趋利性、因果性；为了达到入侵的目的，所采用的手段都是有针对性；从数据包的角度来看也是有特征可循的。所以从这个思路出发，设计了模式串以不同概率随机分布到文本串中的试验环境，分析了AC、WM多模式匹配算法，统计了各种算法在文本串中找出所有特征数据包所需要的时间，分析其在不同概率分布条件下的性能指标；证明了WM概率分布较小时表现最为优秀；但是AC算法在匹配过程中比较稳定；最后提出了一种新的改进的模式匹配算法，通过最优数据筛选-过滤定理选择最优模式串及字符串组合对数据集进行筛选-过滤，找出模式串中的特征字符组成新的匹配模式串，对文本串进行分层匹配。具有较快的匹配速度及更稳定的匹配命中率。
参考文献：
[1]史开泉.P-集合[J].山东大学学报：理学版，2008，43（11）：77-84.
[2]史开泉.函数P-集合[J].山东大学学报：理学版，2011，46（2）：62-69.
[3]郭志林.P-集合的随机特征[J].模糊系统与数学，2011，25（2）：170-174.
[4]郭志林.随机P-集合的数据筛选过滤[J].河南科技大学学报自然科学版，2012，33（2）：83-86.
[5]孙德才.基于匹配区域特征的相似字符串匹配过滤算法[J].计算机研究与发展，2010，47（4）：663-670.
