导读:本文包含了字符串模式匹配论文开题报告文献综述及选题提纲参考文献，主要关键词:众包,MongoDB,MySQL,模式映射
字符串模式匹配论文文献综述
赵志力[1]（2018）在《众包数据的数据库模式映射方案和近似多字符串匹配研究》一文中研究指出随着众包模式作为一种新型的经济模式,国内外不同类型的众包平台也如同雨后春笋般的涌现。基于NoSQL数据库的轻量级众包平台是目前使用的最为广泛的众包模式,其高效的读写性能以及支持分布式存储的特点能应对大数据量下的存储问题。但是其弱结构化的存储方式,也带了通用性较差等和对数据本身的事物操作支持较弱等不足。因此,如何高效且能通过事物操作处理大数据量众包数据成为了目前研究的主要热点。基于NoSQL数据库对事物性操作的不敏感性,目前已经有大量的工作旨在通过研究数据结构之间的转换来优化该问题,但是系统的针对由NoSQL数据库向关系型数据库的模式映射方案的研究较少。另外,在某些众包数据的提取中存在着多字符串匹配的问题,目前国内外的主要研究是还未将字符串匹配技术应用到该领域,基于现有的算法无法实现对众包数据中的多个字符串进行匹配提取。本文以Recital众包平台及其数据为研究基础,主要对数据库间的模式映射和多字符串模糊匹配进行研究,具体的研究内容和研究结果如下:(1)首先分析了众包系统的设计原理,着重对轻量级众包平台所使用的MongoDB数据库与关系型数据库进行框架和数据结构上的对比分析,为模式映射方案做理论准备。(2)研究字符串比较的算法,详细介绍编辑距离(Edit Distance)与Needleman-Wunsch算法的基本原理,为多字符串的模糊匹配算法提供理论支持和对比研究。(3)针对MongoDB中数据向MySQL应用迁移需求,本文通过数据迁移与数据映射两模块提出对应的模式映射方案,根据不同环境下的数据类型与数据库结构间的差异比较完成了对MySQL的迁移方案。并使用伪代码的形式对映射过程进行详尽的解析。(4)针对多字符串的提取问题,提出了基于编辑距离的多字符串模糊匹配算法,使用卷积的思想,逐位使用编辑距离计算相似程度,并且根据相应输出准则进行匹配结果筛选。在输出的阈值参数选取中,阈值越高时匹配结果准确度越高,但是匹配耗时也随之增加,统筹考虑到匹配的准确率选取最佳阈值。实验表明,在多字符串的模糊匹配与单字符串的提取过程中,本文提出的基于编辑距离的算法都在准确率上优于Needleman-Wunsch算法并且耗时更短。(本文来源于《广东工业大学》期刊2018-05-01）
张建莉[2]（2016）在《字符串单模式匹配算法研究》一文中研究指出字符串匹配问题是计算机科学的基础问题之一,被广泛应用于涉及文字和符号处理的各个领域中。本文主要解说了BF算法、KMP算法、BM算法等单模式匹配算法,并且对诸算法进行了对比分析。(本文来源于《农业网络信息》期刊2016年04期）
王春雨[3]（2015）在《基于编辑距离的字符串模式匹配算法研究》一文中研究指出编辑距离是模式匹配的重要组成方面,是模式匹配中相似度的一种度量指标。它在模式匹配中具有重要的基础作用,有着不可替代的意义。由于现有的模式匹配的匹配速度并不是很好,编辑距离值的准确性也不是很高。因此,编辑距离逐渐成为模式匹配问题中的研究热点。本文针对已有的编辑距离定义和模式匹配速度不佳的问题,详细了解了编辑距离的定义和各种模式匹配算法以及不同模式匹配的相似度的计算方法,同时对编辑距离的定义和编辑距离算法进行了深入的研究和分析。首先,对模式匹配中已有的编辑距离定义和编辑距离算法的优缺点进行了详尽的分析,针对模式配中编辑距离的准确性,提出了一种新的编辑距离定义,使用新的编辑距离定义,可以使得计算出来的编辑距离的值具有更好的准确性。其次,本文综合、详细的分析了几种编辑距离的计算算法,针对已有的模式匹配速度效率不佳的问题,提出了基于编辑距离的模式匹配算法,即在新的编辑距离定义的基础上,增加了一个字符串快速扫描算法,在大规模数据集中使用该模式匹配算法,能够有效的减少反复执行操作的时间,从而获得了更高的时间效率。最后,分别通过数学方法和实验进行理论证明和实验验证,通过与已有的编辑距离算法进行对比,分别验证了基于编辑距离的模式匹配算法的匹配速度和有效性。(本文来源于《燕山大学》期刊2015-05-01）
蔡恒,张帅[4]（2014）在《基于BF算法改进的字符串模式匹配算法》一文中研究指出基于人在字符串匹配过程中常用的思维,提出一种从模式串中提取特殊字符和具有特殊结构的字符组成字符串,用数组或链表来表示这种字符串的结构,使得提取出来的字符能与目标串中相应位置的字符比较的算法。用以减少比较次数,提高匹配效率。(本文来源于《电脑编程技巧与维护》期刊2014年22期）
黎慧,李燕[5]（2014）在《一种字符串压缩全模式匹配的主机入侵防御算法》一文中研究指出针对现有名单匹配算法由于对名单中文件路径使用明文保存方式存在安全隐患,提出一种基于字符串压缩的用于全模式匹配的名单匹配算法。首先对保存有文件全路径的字符串进行MD5运算,然后将MD5值与压缩处理成16个字节的二进制路径数据合并进行求模运算,最终将名单元素转化成一个32字节结构体。通过仿真实验对朴素匹配算法、BM、压缩叁种算法在内存使用、遍历时间、查找时间以及重复数上进行比较,实验结果表明,所提出的算法在性能以及安全性上优于其他算法。(本文来源于《计算机应用与软件》期刊2014年09期）
刘建荣,喻涛[6]（2014）在《浅谈字符串模式匹配的常用算法》一文中研究指出简要叙述了字符串的定位操作即字符串模式匹配的基本概念和算法,探讨了字符串模式匹配操作的最基本的BF匹配算法以及改进以后的模式匹配的KMP算法。(本文来源于《信息通信》期刊2014年05期）
许家铭,李晓东,金键,马盈[7]（2014）在《一种高效的多模式字符串匹配算法》一文中研究指出在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%,ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。(本文来源于《计算机工程》期刊2014年03期）
毕智超[8]（2013）在《字符串模式匹配算法的研究及改进》一文中研究指出串的模式匹配是一种重要的串运算。本文首先对朴素的模式匹配BF算法与KMP算法进行了分析,在此基础上寻求出一种简单实用、易于理解的字符串模式匹配改进算法。结果表明改进算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率。(本文来源于《电子测试》期刊2013年20期）
巫喜红,凌捷[9]（2013）在《基于字符频率的字符串模式匹配算法的研究》一文中研究指出本文分析了经典的BM算法和Sunday算法,根据字符频率的特点提出了一种新的模式匹配算法CFPM。CFPM算法确定模式串中字符频率最低的关键字符后,扫描文本串中该关键字符的位置并存储,最后根据这些位置信息进行快速地匹配,匹配方式是以关键字符为始点先匹配左部分再匹配右部分。为了验证CFPM算法的性能,在相同的文本串和模式串情况下,从匹配移动次数和匹配的字符个数两方面对CFPM算法进行实验。实验结果证明,由于CFPM算法能够很大限度地跳过坏字符,大大减少了匹配次数和字符比较个数,有效地加快了匹配速度,其效率优于BM、Sunday等算法。(本文来源于《制造业自动化》期刊2013年17期）
潘冠桦[10]（2013）在《单模式字符串匹配算法效率的研究》一文中研究指出字符串匹配的应用范围非常广泛,包括文档编辑、入侵检测、病毒特征码查找、防火墙技术、基因序列匹配等多个领域。Sunday算法是当前应用广泛并且比较高效的单模式匹配算法。但是当模式串和文本串均存在大量的重复字符时,Sunday算法的匹配次数将随着首字符的重复次数快速增加,在这种情况下,算法的执行效率将大大低于KMP算法。为了扩大Sunday算法的适用范围,提高其平均执行效率。本文提出了一种基于Sunday算法的改进算法,在算法匹配工作开始前进行预处理,将重复的首字符压缩为一个字符,然后使用压缩后的字符串和正文进行匹配,如果匹配成功,返回成功匹配的位置信息,然后开始进行回溯,即对成功匹配的位置信息前的字符和首字符进行循环匹配,如果匹配位数和模式串相同,则返回成功,否则返回失败。可以减少大量无意义的匹配次数,提高算法的执行速度。最后,分析改进后算法的性能,并通过实验进一步证明了改进算法的有效性。由于直接对字符串匹配算法构造状态转化图进行效率分析时的计算过程过于复杂。本文提出了一种以穷举算法为基准,根据算法匹配差值计算算法效率的方法,并以Sunday算法为例进行了效率分析。因为Barth对穷举算法的估计结果偏差较大,但穷举算法起着非常重要的基准作用。因此首先对穷举算法进行效率分析。在对穷举算法的匹配过程进行了详细分析的基础上,构建马尔可夫链的状态转换图描述其匹配过程,并对状态转换图进行简化。最终的状态图没有吸收态,且当n较大时每个状态的转换概率都会收敛为一个稳定值。根据以上特点可求得每个状态的转换概率,得到穷举算法比较精确的平均效率估计公式。其次,Sunday算法是最新的对BM算法进行了大幅改进的算法,和BM算法相比效率有了较大的提高,在实践中得到了广泛使用,具有新颖性和代表性。因此选择Sunday算法进行效率分析。对Sunday算法的匹配过程比较复杂、使用坏字符启发跳转、难以构建马尔可夫链的特点,采用间接的方法得到算法效率。即在得到穷举算法精确的匹配效率后,对Sunday算法和穷举算法的匹配过程进行详细的分析,得出两者的区别。将两种算法按照模式串尾字符所对应文本字符的下一个字符是否属于模式串分类讨论,通过概率论相关知识计算出Sunday算法和穷举算法平均匹配次数的差值。最后将穷举算法的匹配效率与两种算法的差值相减,得出Sunday算法平均效率估计公式。为使实验文本串的大小和字母表容量严格相同,并在最差情况下匹配成功。我们将文本串的字符随机交换位置后形成新的文本,将新文本和模式串进行匹配。如此不断循环,直到不产生新的匹配次数。最后删去匹配次数相同和不在最差情况下匹配的文本串。实验结果表明,由理论计算的估计值确实是算法实际匹配次数的平均值。(本文来源于《太原理工大学》期刊2013-05-01）
字符串模式匹配论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
字符串匹配问题是计算机科学的基础问题之一,被广泛应用于涉及文字和符号处理的各个领域中。本文主要解说了BF算法、KMP算法、BM算法等单模式匹配算法,并且对诸算法进行了对比分析。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
字符串模式匹配论文参考文献
[1].赵志力.众包数据的数据库模式映射方案和近似多字符串匹配研究[D].广东工业大学.2018
[2].张建莉.字符串单模式匹配算法研究[J].农业网络信息.2016
[3].王春雨.基于编辑距离的字符串模式匹配算法研究[D].燕山大学.2015
[4].蔡恒,张帅.基于BF算法改进的字符串模式匹配算法[J].电脑编程技巧与维护.2014
[5].黎慧,李燕.一种字符串压缩全模式匹配的主机入侵防御算法[J].计算机应用与软件.2014
[6].刘建荣,喻涛.浅谈字符串模式匹配的常用算法[J].信息通信.2014
[7].许家铭,李晓东,金键,马盈.一种高效的多模式字符串匹配算法[J].计算机工程.2014
[8].毕智超.字符串模式匹配算法的研究及改进[J].电子测试.2013
[9].巫喜红,凌捷.基于字符频率的字符串模式匹配算法的研究[J].制造业自动化.2013
[10].潘冠桦.单模式字符串匹配算法效率的研究[D].太原理工大学.2013