【摘 要】
:
近似串匹配是计算机科学的基础问题,在文本检索、生物信息学、信号处理、入侵检测、模式识别、数据挖掘和实体识别等领域具有广泛的应用。近似串匹配的效率决定了这些应用的
论文部分内容阅读
近似串匹配是计算机科学的基础问题,在文本检索、生物信息学、信号处理、入侵检测、模式识别、数据挖掘和实体识别等领域具有广泛的应用。近似串匹配的效率决定了这些应用的效率。传统的动态规划方法效率低,自动机方法构造复杂,过滤验证方法以其高效、简明成为使用最广泛的近似串匹配方法。为了进一步提高过滤验证算法的效率,本文提出用于近似串匹配的顺序检测方法,具体内容包括以下方面:1.提出顺序检测计算编辑距离的方法。该方法顺序比对两个字符串的当前位置,通过合理认定不匹配位置的基本操作,得到其编辑距离。该方法时间复杂度为O(n),与动态规划法的O(n2)相比,具有明显的优势。不匹配位置的基本操作认定,本文提出两种方法:第一种方法是基于基本操作序列顺序验证。该方法先枚举某一编辑距离对应的所有基本操作序列。顺序检测时,按照基本操作序列确定不匹配位置的基本操作,该方法适用于小于等于3的编辑距离的计算。第二种方法是基于局部最优规则(综合考虑当前位置每增加一个基本操作所能处理的字符数和处理后两子字符串的长度差)来确定当前位置的基本操作。按照该方法得到编辑距离的一个上界,可得到大部分符合条件的字符串,也可以为其设置一个上界,对剩余字符串进行过滤。2.以顺序检测方法为核心,在过滤验证的框架下,提出阈值为k的近似串匹配算法。过滤阶段,先进行离线的count过滤,然后基于局部最优规则顺序检测方法估计两个字符串的编辑距离,根据估计值对候选集进行筛选过滤;验证阶段,阈值k小于等于3时,用基本操作序列顺序验证方法验证两字符串的编辑距离,否则,用动态规划法验证其编辑距离。实验结果表明,相比目前高效的Merge Filter算法,本文方法在DBLP、IMDB、WEB Corpus数据集中的时间效率至少提高17%。
其他文献
软件运行出现故障之后,软件故障定位非常困难。传统的软件定位方法主要是结合测试技术,使用有针对性的测试,发现软件中存在的特定缺陷,再利用其他辅助技术找出故障原因并定位
随着Web数据和各种网络资源剧增以及语义网的兴起与发展,海量RDF(Resource Description Framework,资源描述框架)数据存储已成为当前Web数据存储领域的研究热点。作者在深入
由于三峡库区特殊的地质地理条件,自古以来就是滑坡灾害高发地区,特别是三峡大坝建成和三峡库区蓄水后,三峡库区地质环境受到严重的影响,滑坡灾害频发。滑坡灾害不但破坏桥涵、电
无线传感器网络(WSN)是近几年来国内外较为热门的研究领域,在国防军事和人们的日常生活上具有十分重要的应用前景。纵观计算机网络技术的发展史,应用需求始终是推动无线互联
形式化方法是建立在严密数学逻辑基础上的系统研究方法,其严谨、精确的特性适合发现系统设计与开发过程中并发性、安全性等方面的问题。PAT(Process Analysis Toolkit)平台是
人脑是自然界中最复杂的网络之一,而复杂网络理论为人脑的研究提供了一个新的方向。计算脑网络属性的方法是研究脑网络的一项重要途径,因此网络构建时间和属性计算时间是影响
数据库技术的广泛应用使得数据库应用系统中对时态信息处理的要求越来越高,越来越多的应用系统需要存储和管理相关的时态信息。为了描述时态信息,提出了时态数据库的概念。时
在医疗信息系统中,各部门的信息系统之间以及各个医疗机构之间缺乏有效的共享和统一的规范,因此形成了信息孤岛。传统的采用面向构件的方法缺乏灵活性的交互,而多Agent的社会
统一通信是一种新的通信模式,它把计算机技术与传统通信技术融合在一起,作为一种解决方案和应用,它的最终目的就是让人们能够在任何时间、任何地点,都可以通过任何设备、任何网络
随着免疫学理论研究的不断发展,人们对生物免疫系统的认识不断深入,提出了人工免疫系统,该系统已经被广泛应用于科学研究和工程实践的众多领域。免疫算法(Immune Algorithm,