支持编辑距离约束的近似最长公共子串匹配及其优化算法

《支持编辑距离约束的近似最长公共子串匹配及其优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号密级UDC学位论文支持编辑距离约束的近似最长公共子串匹配及其优化算法作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：叶心杨晓春教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：王大玲董晓梅石祥滨东北大学2014年6月万方数据万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成

2、果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：叶N1日期：加f牛，6、坶学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年∥学位论文作者签名：

3、叶N、签字日期：珈J牛．七．雌聊签名：钐睐签字日期：加坶．6、涉万方数据东北大学硕士学位论文摘要支持编辑距离约束的近似最长公共子串匹配及其优化算法摘要目前许多信息都以文本的形式存放在计算机中，所以基于文本的信息检索技术，如最长公共子串匹配问题一直是文本管理、程序分析等领域的经典问题，长期以来受到广泛地关注与研究。然而最长公共子串的要求过于严格，在实际应用中，两个局部非常相似的文本其中的公共部分往往不是完全精确匹配的，因此需要提供支持近似匹配的最长公共子串匹配方法。目前尚未有相关技术的报道。因此，本文重点

4、研究支持编辑距离约束的近似最长公共子串匹配问题。本文首先综述了现有的字符串近似匹配技术，并基于此，提出了一种基于动态规划的算法，这个算法首先用最长公共子串的动态规划算法求出公共子串，再用编辑距离和最长公共子序列的动态规划方法，计算具有公共前缀的子串组成的比对区域，找到所有支持编辑距离约束的近似公共子串，最后进行长度验证找到支持编辑距离约束的近似最长公共子串。该算法可以保证O(砌胛)的时间复杂度。为了进一步提高算法的效率，本文提出了基于后缀数组的公共子串匹配优化算法。该算法先采用后缀数组的方法求出所有公共

5、子串，再将相邻连接距离不大于编辑距离阈的公共子串连接起来构造验证集，在构造验证集的过程中采用了基于公共子串位置和基于公共子串间距离的过滤策略，最后用启发式的方法在验证集中找出支持编辑距离约束的近似最长公共子串，提高了查询效率。最后，本文在三个不同的真实数据集上测试了这两种算法的性能，基于动态规划的算法，由于需要对所有具有相同前缀开始的比对区域进行动态规划计算，所以算法的性能比基于公共子串的查询算法差。实验发现，基于公共子串的算法由于采用了基于公共子串位置和公共子串间距离的过滤技术，所以该算法的性能跟两个

6、串的公共子串的个数和长度有关系，如果公子串个数比较少，且长度都比较长，算法的性能越好。关键词：近似匹配：编辑距离；动态规划；后缀数组；最长公共子串一II—万方数据万方数据篓羹鐾霎萋霆雾鬟囊蚕薹羹§冀刊蠢

7、蒌垂蠢萋鲤鬟I型羹薹冀荔薹薹蓬雾萎i雾燮

8、冀雾霎篓l臻塾蓁墼翼羹翼i蓁霆蓁冀雾薹睡蓁羹聚薅蘑羹万方数据东北大学硕士学位论文目录目录独创性声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯I摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯IIAbstract⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

9、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．III第1章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．2本文的研究内容及面临的挑战⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．31．3本文的贡献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．41．4本文的组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．4第2章背景知识与问题定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72．1编辑距离⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

10、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．72．2最长公共子串⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．82．3最长公共子序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．92．4后缀数组⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯102．5近似最长公共子串的问题定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯132．6本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯14第3章相关工作