【摘 要】
:
模式匹配问题是计算机科学的一个基本问题。在早期的模式匹配研究中,多数算法集中于精确模式匹配的研究,如:著名的单模式匹配算法KMP、BM及多模式匹配算法CA、CW、BNDM等。但
论文部分内容阅读
模式匹配问题是计算机科学的一个基本问题。在早期的模式匹配研究中,多数算法集中于精确模式匹配的研究,如:著名的单模式匹配算法KMP、BM及多模式匹配算法CA、CW、BNDM等。但在实际应用中,近似模式匹配算法在信息过滤及计算生物学等领域显得非常重要。比如人们通常在DNA的片段分析中,只是寻找到与目标模式相似的DNA片段,从而判断它们之间是否有亲缘关系等等。要在海量的信息中快速地找到有意义的模式串,运用一般的方法进行模式查找,所花费的时间让人难以忍受,为了提高模式查找算法的运行效率,这里提出了模式查找的新算法。本文是针对长篇英文小说中的高频词(模式串)查找问题,应用了近似串匹配的过滤的思想,提出了模式查找的算法Epattern_searcherH和Epattern_searcher。本论文的主要工作如下:(1)提出了模式查找的算法。针对近似模式匹配中过滤思想设计模式查找的算法,首先按照一定的过滤原则(某种条件限定)搜索文本串,过滤掉那些不可能发生匹配的的文本段;然后验证剩下的匹配候选位置处是否真的存在成功匹配。由于过滤去了大部分不可能发生匹配的文本串,加速了匹配的查找过程,从而达到提高模式查找算法运行效率的目的。(2)应用后缀数组的数据结构来实现提出的算法。对于字符串处理问题,后缀树是一种很好的数据结构,但后缀树需要占用较大内存空间,而空间问题一直是运用后缀树数据结构来处理超长字符串的一个瓶颈。与后缀树结构相比,后缀数组可节约三分之二以上的空间,因此这里运用后缀数组的数据结构来实现提出的算法。
其他文献
近年来,随着计算机技术的发展,计算机仿真作为研究问题的新方法,越来越受到学者们的重视。通过将问题抽象为程序模型在计算机中进行运算,可模拟现实情况,据此给出建议和参考信息,并
近年来,无线传感器网络获得了快速的发展,并以其低成本、大规模和自组织的特点带来了信息感知的一场变革。在无线传感器网络中,传感器节点自身位置信息的获取对各种应用而言
数字化作品具有易存储加工和易传送等特征,使知识的传播和交流更为方便,但同时也为某些非法者恶意篡改,攻击和窃取别人作品提供了便利条件。因而,如何保护数字媒体信息安全已
近几年来,随着网络技术的迅速发展,能够随时随地进行通信的移动网络受到越来越多的关注。在一些特殊、紧急的环境下进行网络通信日益重要,Ad hoc网络正是在这种背景下产生的。但
图像发排控制技术是在数控技术和计算机技术的基础上发展起来的一种自动化控制技术。该技术综合了嵌入式、机械设计、光学、电子、图像处理等相关技术,以机械速度、位置、扭
基于内容的图像检索是多媒体信息检索领域的一项新兴技术。和传统的基于标注的图像检索方式相比,它具有客观,自动高效等优点,有着非常广阔的应用空间。目前,大多数基于内容的图像
广播加密指加密方通过广播信道,将消息同时发送给收听该广播的多个用户的加密方案,广播加密作为信息安全的重要内容,近年来成为了研究的重点。和传统的广播加密方案相比,基于
双目立体视觉的基本原理是模仿人眼与人类视觉的立体感知过程,从两个视点观察同一物体,得到不同视角下的图像后再通过三角测量原理计算图像像素间的位置偏差,由此获取景物的
图像数字水印技术是随着数字化和网络发展而新兴的一种保护图像版权的技术。它也是信息隐藏技术和数字水印技术里面一个重要的分支。本文是在现有研究理论的基础上进一步探讨
在视频会议、可视电话、防盗监控等领域中,人们往往关心的是人的面部特征,而对背景区域却不是特别感兴趣,此时就没有必要对整个图像采用同样的编码方式,因为若对整个图像进行无