KMP算法的理论研究

KMP算法是经典的串匹配算法之一.本文首先引入刻划模式串前缀特征的集合K_j及其划分,讨论了其若干性质.然后定义函数f与next,利用f刻划了K_j的构造,由此得到了f的迭代计算方法;证明了next与f之间的关系,从而给出了KMP算法原理的形式表述和数学证明.最后,基于f的迭代计算方法以及next与f之间的关系,给出了算法描述,分析了时间复杂度.

基于投影与KMP简约算法的一维快速模板匹配算法

传统的模板匹配算法(如NC和SSDA)虽然具有匹配精度高的优点,但由于其计算量大,使得匹配时间过长。本研究提出了一种新的基于投影与KMP简约算法的一维快速模板匹配算法,首先将图像进行降维处理,得到特征字符串,通过对特征字符串的匹配,实现粗匹配,可大幅度地减少图像匹配时间;然后利用NC匹配算法,对粗匹配的结果进行验证,以达到快速匹配的目的。通过实验证明了本算法的快速性和准确性。

专家分配问题的KMP优化求解方法研究

专家分配问题是项目申报系统中评审环节（盲审）重点解决的问题．根据系统模型，针对项目和专家的多因素匹配问题，对专家分配问题进行研究，建立了专家分配问题的模型．应用KM P方法和索引顺序查找的求解方法，提出了基于多信息因素的专家分配优化求解方法．通过测试与应用表明，该系统的专家分配算法能实现专家与申请书的匹配，结果有较高的准确性和合理性，该方法将评审工作的效率提高了8～12倍，同时将传统人工操作过程中的出错概率降至0．15％～0％．

字符串的模式匹配算法——基于KMP算法的讨论

重点对基本的串匹配算法和 KMP算法进行了探讨。通过对这两种算法的比较分析提出了一个新算法 ,此算法具有比基本的串匹配算法更优越的时间复杂性 。

KMP算法研究与实现

文字是传播信息的关键载体之一,是表达人类情感的重要方式,更是传承文化的最关键最基本的手段。理所当然,文本编辑程序是计算机中最重要的应用之一。自从计算机被发明以来,字符,字符串,文本,就一直于人类打着交道。在文本编辑程序中,经常会出现要搜索一段特定文字以及对其位置定位的情况,当文本内容庞大,或者要搜索的内容出现相当频繁时,良好的搜索算法对效率的提高就相当可观了。该文研究了效率极高的KMP字符串匹配算法,并使用C语言对算法进行了实现。

改进的KMP算法在舰船图像匹配中的应用

在研究KMP经典算法的基础上,针对KMP算法中存在的重复字符较多或极少、失配现象严重等缺陷,给出不同的改进方法,加快匹配速度,减少复杂度。针对目前图像匹配技术的研究,结合改进后的算法,建立图像数据库,对原始图像进行增强和小波变换,并就匹配过程给出了具体的操作流程。实验表明该做法能有效地缩短匹配时间,识别率高,可适用于对时间要求较高的识别系统。

一种改进的KMP模式匹配算法

通过对KMP模式匹配算法的分析,给出了一种改进算法,提出了新的next函数的求值方法,并用VC++程序实现了改进后的KMP模式匹配算法。

KMP算法的并行研究

本文在分析了常见的字符串匹配算法(BF、KMP)的基础上,将两种算法结合,应用到并行串匹配中,以达到并行串的高效模式匹配。该算法将KMP算法应用到了并行串匹配中,充分利用每一次匹配比较的信息,以跳过尽可能多的不匹配子串,进行下次匹配。当子串前几个字符在母串中出现频率较低时,该算法性能提高显著。

浅析KMP算法中next数组值计算

本文以实例出发分析了模式匹配kmp算法以及算法中next函数的含义即形成过程,由定义出发,给出详实的参数来判定k的情况来计算next数组的值,从另一个角度更好的帮助学生理解该算法。

分布式存储的并行串匹配算法的设计与分析

并行串匹配算法的研究大都集中在 PRAM(parallel random access machine)模型上 ,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多 .该文采用将最优串行算法并行化的技术 ,利用模式串的周期性质 ,巧妙地将改进的 KMP(Knuth- Morris- Pratt)算法并行化 ,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法 ,其计算复杂度为 O(n/ p+m) ,通信复杂度为 O(ulogp) ,其中 n为文本串长 ,m为模式串长 ,u为模式串最小周期长 ,p为处理器数 .

对BM串匹配算法的一个改进

在对著名的Boyer -Moore串匹配算法进行分析后 ,对BM算法中的尝试位置移动处理部分进行改进 ,提出了IBM算法。该算法将好后缀移动与坏字符移动合并进行处理 ,从而尽量利用已有信息进行更大的尝试位置移动 ,使算法具有更高的效率。对IBM算法进行复杂度分析 ,对BM算法、KMP算法和IBM算法进行实际性能比较 ,结果表明IBM算法的平均运行时间明显优于BM算法与KMP算法。

模式匹配算法的效率分析与改进

模式匹配是一种重要的非数值运算,本文在分析了当前几种主要的匹配算法思想的基础上,提出了一种新的改进算法,降低了匹配算法的时间复杂度,提高了算法效率。

字符串模式匹配算法性能测试

本文详细分析几种字符串模式匹配算法如BF、KMP、BM。通过上机实验对这些算法的平均查找时间和匹配次数进行测试,结果表明在这些字符串模式匹配算法中BM算法是最快的算法。

邻间关系匹配算法研究

对于26个字母的全排,它们的邻间关系是唯一的。文中根据这个特性,针对子串长度较长的(大于26)字符串匹配问题,提出了一种基于邻间关系的匹配算法。该算法把字符串的邻间关系转化为十进制的数值,并利用这一数值实现字符串的快速匹配。该算法时间复杂度为О(m-n),且算法简便,容易实现。

基于GPU的KMP串匹配并行算法研究

KMP(Knuth-Morris-Pratt)串匹配算法在面对大规模数据集时,运算时间将随着数据集的增大而迅速增长。为了提升算法的计算性能,设计了一种基于图像处理器(graphic processing unit,GPU)的KMP串匹配并行算法。针对KMP串匹配算法进行并行特征分析,提出了一种粗粒度和细粒度相结合的并行优化方法,从任务划分、GPU访存和内核配置3方面加以优化。通过数据不重叠划分的方法,在字符串匹配阶段,采用在2个邻接子正文串中搜索匹配位置的策略;在统计匹配数量阶段,采用统一计算设备架构(compute unified device architecture,CUDA)原生的原子加法操作,克服了全局存储器未合并访问的问题,提高了整体性能。结果表明,基于GPU加速的KMP串匹配并行算法提高了计算速度,相比中央处理器(central processing unit,CPU)串行算法和开放多处理(open multiprocessing,OpenMP)并行算法分别获得了39.29倍和29.47倍的加速比,满足了KMP串匹配算法处理大数据集的实时性需求。

字符串匹配算法探讨

分析了BM和KMP算法特点,阐述了字符串匹配算法在文本处理领域、信息检索、语义学、分子生物学等学科中应用的意义,对字符串中最有影响的KMP算法、BM算法、RK随机算法和SUANDAY算法以及由此而产生的一些改进算法进行研究,实现了实验分析及功能对比,并指明各算法的适用性。

KMP算法的一种新的简化算法

通过对字符串模式匹配算法BF与KMP的分析,提出了一种简化KMP算法的方法,构造了一种新的计算next函数的方法,简化后的算法比KMP更清晰直观.经过复杂性分析和上机实验,得出当模式串的长度不大时,简化算法是一种高效的模式匹配算法.

字符串匹配算法和钩子程序对上网内容筛选的应用

上网内容筛选运用的主要的理论知识是字符串匹配算法和钩子程序。首先由钩子程序截获网页内容,然后根据一定的字符串匹配算法统计出网页内容中的关键字,最后根据关键字来分析判断网页是否可以显示。本文主要对以上理论知识进行介绍,并讨论其在现实生活中的实际应用。