支持交换的近似串匹配算法的研究与实现
发布时间：2021-10-24 16:57
随着网络设备软硬件技术的提高和网络用户的日益增加,网络上的数据流量正在以爆发式的趋势增长。随着大数据相关科技的发展,大数据的处理算法面临着更加严峻的挑战,模式匹配作为许多前沿技术的基础而被广泛研究,而模式匹配的一个分支——字符串近似匹配往往用于信息搜索、安全检测、生物计算等。提高解决大数据应用问题的高性能近似模式匹配算法之性能是当前一个极具探索价值的问题。本文引入了一类新型近似模式匹配问题——允许文本中相邻两字符交换的近似匹配算法,并提出了相应算法以及理论分析和实验。首先定义了交换的概念,交换是文本中相邻的互不相同的两字符的交换。字符串的交换版本是该字符串经过几次交换操作而转换成的字符串。本文提出了一种允许文本中相邻两字符交换的近似匹配算法,该算法首先采用过滤的思想将文本串划分为两个文本段集合:不匹配集合与候选段集合。我们改进以往的近似串匹配算法,将算法的适用范围扩展到额外允许出现交换的情况。与已有的相关算法不同,该算法能够更加符合现实应用的要求,具有一定的实用性。另外为了提高匹配效率,我们在上述过滤思想的基础上,直接过滤掉不可能发生匹配的匹配集合,将改进的近似匹配算法应用到候选段集合...
【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校
【文章页数】：64 页
【学位级别】：硕士
【部分图文】：
有限模式匹配自动机如图2.1所示自动机，自动机的第i行代表进行到当前行中状态时已经出现
图 2.2 变量打包字节具体计算过程如下：1. 将四个数字如上述打包到一个机器字 V 中。2. addone ← 00000001 00000001 00000001 000000013. V += addone4. return V由此可见位并行算法的效率要比串行方法高数倍，另外如果存储一个单位所需的字节数越少，一个机器字所能容纳的元素数量就越多，效率就越高。一个种常见的字符串匹配算法的位并行实现首先是运用在精确模式匹配算法上，随后对精确模式匹配算法进行改进，形成了一种近似串模式匹配算法的位并行实现。精确串模式匹配位并行实现：定义一个数组 R 来表示文本串当前位置与模式串的匹配情况，该数组的取值
因此 L[ d][e]> i，这与假设相矛盾，证同样为 O (mn)，但是空间复杂度相较于Morris 和 V.R.Pratt 三人根据暴力匹配想，该算法使用三人姓名的缩写被称为 K效快速的算法之一[18]。配字符串的算法中模式串首先从文本串不匹配则从文本串第二位重新匹配，以此结束。
【参考文献】：
期刊论文
[1]网络入侵检测系统中的模式匹配算法设计优化[J]. 陈卓民. 电子设计工程. 2018(15)
[2]模式匹配算法的研究与实现[J]. 李萍,赵润林. 电脑知识与技术. 2017(18)
[3]氨基酸序列特征向量提取方法的探讨[J]. 谭生龙. 电脑知识与技术. 2016(22)
[4]应用Q-gram命中特征优化的近似串匹配算法[J]. 王晓霞,孙德才. 电子设计工程. 2016(15)
[5]一种改进的BM模式匹配算法[J]. 蒋亚平,田月霞,赵军伟. 科技通报. 2015(09)
[6]近似串匹配过滤算法研究[J]. 孙德才,王晓霞. 计算机技术与发展. 2015(04)
[7]基于WM算法改进的多模式匹配算法[J]. 董迎亮,玄雪花,王德民. 吉林大学学报(信息科学版). 2011(04)
[8]改进的近似模式匹配算法[J]. 张丽霞,宋鸿陟. 计算机工程与设计. 2011(05)
[9]一种改进的模式匹配算法[J]. 田宏,李君秋. 大连交通大学学报. 2010(04)
[10]一种基于有限自动机的快速串匹配算法[J]. 陈倩. 计算机技术与发展. 2009(01)
硕士论文
[1]相似字符串查找算法研究[D]. 黄厚柱.安徽大学 2017
[2]基于网络安全系统的大规模模式集合匹配算法的研究[D]. 姜丽丽.东南大学 2015
[3]基于局部过滤的字符串近似匹配算法和优化技术[D]. 王尧舒.东北大学 2014
[4]网络入侵检测系统中模式匹配算法的应用研究[D]. 刘鑫.大连海事大学 2013
[5]单模式字符串匹配算法效率的研究[D]. 潘冠桦.太原理工大学 2013
[6]基于后缀数组的近似字符串匹配[D]. 张喜娟.西安电子科技大学 2012
[7]编辑距离快速算法研究[D]. 王培培.东北大学 2011
[8]程序代码抄袭检测中串匹配算法的研究与实现[D]. 王春晖.内蒙古师范大学 2008
[9]网络内容过滤关键技术与研究[D]. 徐国胜.电子科技大学 2007
[10]用位并行法进行过滤的中文近似串匹配算法[D]. 范立新.浙江大学 2006
本文编号：3455636
【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校
【文章页数】：64 页
【学位级别】：硕士
【部分图文】：
有限模式匹配自动机如图2.1所示自动机，自动机的第i行代表进行到当前行中状态时已经出现
图 2.2 变量打包字节具体计算过程如下：1. 将四个数字如上述打包到一个机器字 V 中。2. addone ← 00000001 00000001 00000001 000000013. V += addone4. return V由此可见位并行算法的效率要比串行方法高数倍，另外如果存储一个单位所需的字节数越少，一个机器字所能容纳的元素数量就越多，效率就越高。一个种常见的字符串匹配算法的位并行实现首先是运用在精确模式匹配算法上，随后对精确模式匹配算法进行改进，形成了一种近似串模式匹配算法的位并行实现。精确串模式匹配位并行实现：定义一个数组 R 来表示文本串当前位置与模式串的匹配情况，该数组的取值
因此 L[ d][e]> i，这与假设相矛盾，证同样为 O (mn)，但是空间复杂度相较于Morris 和 V.R.Pratt 三人根据暴力匹配想，该算法使用三人姓名的缩写被称为 K效快速的算法之一[18]。配字符串的算法中模式串首先从文本串不匹配则从文本串第二位重新匹配，以此结束。
【参考文献】：
期刊论文
[1]网络入侵检测系统中的模式匹配算法设计优化[J]. 陈卓民. 电子设计工程. 2018(15)
[2]模式匹配算法的研究与实现[J]. 李萍,赵润林. 电脑知识与技术. 2017(18)
[3]氨基酸序列特征向量提取方法的探讨[J]. 谭生龙. 电脑知识与技术. 2016(22)
[4]应用Q-gram命中特征优化的近似串匹配算法[J]. 王晓霞,孙德才. 电子设计工程. 2016(15)
[5]一种改进的BM模式匹配算法[J]. 蒋亚平,田月霞,赵军伟. 科技通报. 2015(09)
[6]近似串匹配过滤算法研究[J]. 孙德才,王晓霞. 计算机技术与发展. 2015(04)
[7]基于WM算法改进的多模式匹配算法[J]. 董迎亮,玄雪花,王德民. 吉林大学学报(信息科学版). 2011(04)
[8]改进的近似模式匹配算法[J]. 张丽霞,宋鸿陟. 计算机工程与设计. 2011(05)
[9]一种改进的模式匹配算法[J]. 田宏,李君秋. 大连交通大学学报. 2010(04)
[10]一种基于有限自动机的快速串匹配算法[J]. 陈倩. 计算机技术与发展. 2009(01)
硕士论文
[1]相似字符串查找算法研究[D]. 黄厚柱.安徽大学 2017
[2]基于网络安全系统的大规模模式集合匹配算法的研究[D]. 姜丽丽.东南大学 2015
[3]基于局部过滤的字符串近似匹配算法和优化技术[D]. 王尧舒.东北大学 2014
[4]网络入侵检测系统中模式匹配算法的应用研究[D]. 刘鑫.大连海事大学 2013
[5]单模式字符串匹配算法效率的研究[D]. 潘冠桦.太原理工大学 2013
[6]基于后缀数组的近似字符串匹配[D]. 张喜娟.西安电子科技大学 2012
[7]编辑距离快速算法研究[D]. 王培培.东北大学 2011
[8]程序代码抄袭检测中串匹配算法的研究与实现[D]. 王春晖.内蒙古师范大学 2008
[9]网络内容过滤关键技术与研究[D]. 徐国胜.电子科技大学 2007
[10]用位并行法进行过滤的中文近似串匹配算法[D]. 范立新.浙江大学 2006
本文编号：3455636
本文链接：https://www.wllwen.com/kejilunwen/shengwushengchang/3455636.html
最近更新
教材专著
