基于编辑距离字符串Top-k相似性搜索算法的研究

摘要

字符串相似性搜索在众多的领域具有广泛的应用，例如：数据清洗、数据集成、拼写检查、抄袭检测、生物序列分析等。到目前为止，有很多度量标准用来衡量字符串之间的相似程度，然而众所周知不存在一个相似性函数在所有领域中都具有最好的性质，编辑距离是所有被广泛接受的相似性函数中的一个。因此本文通过编辑距离表示两个字符串之间的相似程度。一般而言，字符串相似性搜索主要有两种类型：范围查询和Top-k相似性搜索，本文主要研究Top-k搜索问题，即给定一个查询字符串q，Top-k搜索返回字符串集合S中k个字符串，满足这k个字符串和查询字符串q的编辑距离最小。
　　现如今解决字符串Top-k相似性搜索共有三类算法，AQ和Appgram基于n-gram模型，但这两种方法忽略了n-gram的位置信息，同时AQ算法需要对不同长度n-gram建立多个索引导致很低的效率，Appgram不是精确查询，往往会丢失结果，Bedtree算法基于B+树结构，由于过滤条件过于宽松导致遍历过多节点，Range算法和Hstopk算法针对短字符串很有效，当处理长字符串集合时，为了提高查询性能，这两种算法需要很大的额外内存空间。
　　针对现如今方法的缺陷，本文基于n-gram模型，结合n-gram位置信息，设计了新的倒排索引结构，在这个新的索引结构上设计了新的顺序搜索和改进的循环搜索算法；在过滤阶段，加入了长度过滤，数量过滤和位置过滤，同时加入了新的过滤方式频率过滤，实验证明频率过滤可以进一步过滤掉大量候选字符串；同时本文针对top-k查询的初始化进行了研究，结合字符串集合整体统计信息，将字符串集合分类，采用和查询字符串同一类的字符串进行初始化；最后设计了基于磁盘的索引构建和查询方法；最后本文在三个真实数据集上进行了多组对比实验验证本文提出算法的高效性，首先测试各种算法在这三个真实数据集上内存消耗，然后比较了各个算法查询性能，同时对索引的两种构建方式，两种搜索策略，堆的四种初始化算法进行了对比实验，然后对基于磁盘索引构建时间和查询性能进行了测试，最后对长度过滤策略和频率过滤策略进行了测试，通过多组实验证明了本文提出算法的高效性。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究背景及目的和意义

1.2 字符串相似性查询的类型和度量标准

1.3 国内外研究现状

1.4 本文的研究内容

1.5 论文组织结构

第2章 字符串相似性搜索理论基础

2.1 引言

2.2 基本概念

2.3 字符串过滤策略

2.4 现有算法介绍

2.5 本章小结

第3章 索引结构及搜索策略

3.1 引言

3.2 索引结构设计及构建方法

3.3搜索策略

3.4 磁盘索引构建算法

3.5 本章小结

第4章 堆初始化策略

4.1引言

4.2 频率过滤

4.3 堆初始化整体框架

4.4组合字符和区间划分

4.5 字符串集合分类

4.6 堆初始化算法

4.7 本章小结

第5章 实验结果

5.1 引言

5.2各算法需要内存空间大小对比

5.3 与其他算法对比实验

5.4 索引构建方法对比

5.5搜索策略对比

5.6堆初始化策略对比

5.7 磁盘算法性能测试

5.8 过滤性能

5.9 本章小结

结论

参考文献

声明

致谢