基于局部过滤的字符串近似匹配算法和优化技术

《基于局部过滤的字符串近似匹配算法和优化技术》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于局部过滤的字符串近似匹配算法和优化技术作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：王尧舒杨晓春教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：王大玲王斌石祥滨东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyApproximateStringMatchingAlgorithmsandOptimizitionTechniquesUsingLocalFilteringB

2、yWangYaoshuSupervisor：ProfessorYangXiaochunNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢=盘▲。恩。学位论文作者签名：互花储一日期：2，J斗．；．I￥学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并

3、向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年旷学位论文作者签名：王轻销导师签名：1茜砭赤签字日期：乙，Iy-．良】年签字日期：1．f中．6．)，f万方数据东北大学硕士学位论文摘要基于局部过滤的字符串近似匹配算法和优化技术摘要随着计算机的发展，社会中各行各业都离不开计算机，同时计算机可以给人们带来很大的方便和创新。字符串在计算机领域中是一种重要且基础的存储结构。现如今大量的数据都是以字符串这种数据结构的形式存放的。如

4、何在给定的大规模字符串集合中高效率地找到与用户输入相匹配的字符串一直是个重要的研究问题。尤其是实现对字符串的近似匹配具有重要的现实意义和技术挑战。文本着重研究基于编辑距离的近似字符串匹配问题，研究高效率的匹配算法。本文首先综述了经典的支持编辑距离的近似字符串匹配技术，并分析出现有的方法都采用公共匹配因子进行过滤的思想。基于此，提出了局部过滤的匹配思想，即两个不相似的字符串一定由若干个不相似的片段组成。为了过滤掉不相似的字符串对，需要找到一些不相似的片段。本文首先定义局部距离的概念以用来度量两个字符串之间的局部不相似这个特性。根据局部距离的定义提出了局部距离的累加定理来进行过滤。提

5、出了带有位置约束的局部过滤以提高算法的过滤能力。本文还设计了一种索引结构BitTree来管理带有位置约束的局部距离。根据这个索引结构设计两种算法对字符串集合中的字符串进行过滤。另外，局部距离同样可以在验证阶段使用。由于BitTree索引结构存储空间很大，本文提出了新的索引结构PBitTree索引和CoreBitmap索引来减少空间复杂度，同时设计出一种局部过滤的估计算法来进行字符串的过滤。本文在三个真实的数据集上和如今三个主流的算法进行实验。实验结果显示局部过滤方法的运行时间，过滤能力和索引大小都要好于其余三个算法。并且本文提出的估计算法也在运行时间和过滤能力有很好的效果。关键词

6、：编辑距离；近似匹配；字符串：估计算法；局部过滤万方数据东北大学硕士学位论文Abs仃-actApproximateStringMatchingAlgorithmsandOptimizitionTechniquesUsingLocalFilteringAbstractAscomputersciencedevelopsrapidly,manyapplicationsarewidelyusedinthesociety．Meanwhile，thetechnologyofcomputersciencebringsmuchconveniencetohumanbeings．Thestringi

7、sabasicandimportantdatastructure，SOitisbeingusedtostorelargeamountofdata．Howtorelievethematchingstringsfromalargestringcollectionisstillabigresearchproblem．Especiallystringsimilaritymatchinghasmanycriticalsignificanceandtechnicalchallenge．Wee