基于编辑距离的近似字符串匹配及其优化技术

摘要

随着计算机技术在各个领域的广泛应用，信息量也在呈指数增长。在如此多的数据之中，由于各种各样的原因，难免会存在一些错误。在众多的数据类型中，文本数据是最常见也是最古老的类型之一。在文本数据上进行允许一定错误的匹配，即近似字符串匹配已经应用于很多领域，例如数据清洗、实体识别、拼写检查、集合连接和Web搜索等。然而，近似字符串匹配在为用户提供更强大、更全面的功能的同时也使得匹配处理过程及索引建立更加复杂。如何高效地进行近似字符串匹配至关重要。
　　目前，已经有大量工作致力于解决近似字符串匹配问题。其中大部分工作都是围绕着基于编辑距离的近似字符串匹配进行的。基于编辑距离的近似字符串匹配算法大多基于签名，并采用索引结构来支持近似字符串匹配。在匹配的时候采用两阶段的方式，即过滤阶段和验证阶段。过滤阶段首先从索引结构中获取可能与查询字符串近似匹配的字符串的集合，然后通过各种过滤算法过滤掉一些不可能是结果的字符串从而生成候选集合。候选集合中包含了所有近似匹配的字符串和一些并不近似匹配的字符串，所以需要在验证阶段对候选集合中的字符串逐一进行验证以确定其是否真正近似匹配。
　　本文在现有工作的基础之上将变长gram算法的思想和非对称的定长chunk-gram算法的思想相结合提出了非对称的变长chunk-gram算法，并对该算法的公共签名数量的下限进行了分析。在变长chunk-gram算法的基础之上，本文又提出了最优的变长chunk算法，该算法对查询字符串划分最优的τ+1个变长chunk，同时基于BWT提出了BWTPA索引来支持最优τ+1个变长chunk划分，使之满足基于签名框架的最小签名数量τ+1。本文还研究了如何将基于签名的近似字符串匹配技术应用于商用数据库管理系统(DBMS)的顶层来支持近似字符串匹配。这样在利用商用数据库提供的一些功能的同时不需要对商用数据库的底层进行修改。最后，在真实数据集上进行了大量的实验。通过实验结果本身及对实验结果的分析证明了本文提出的算法都能够高效地回答近似字符串匹配问题。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 本文的研究内容及面临的挑战

1．3 本文的贡献

1．4 本文的组织结构

第2章 相关工作

2．1 近似字符串查询算法

2．1．1 q-gram算法

2．1．2 VGRAM算法

2．1．3 q-chunk-gram算法

2．2 字符串集合近似连接算法

2．3 基于签名的过滤规则

2．4 本章小结

第3章 背景知识和问题定义

3．1 编辑距离

3．2 后缀树

3．3 BWT变换

3．3．1 BWT转换算法

3．3．2 基于BWT的反向搜索

3．4 问题定义

3．5 本章小结

第4章 基于变长签名的算法v-chunk-gram

4．1 基本的v-chunk-gram算法

4．1．1 变长签名的划分算法

4．1．2 变长chunk集合和变长gram集合的相似性

4．1．3 v-chunk-gram的查询算法

4．2 最优变长chunk算法

4．2．1 最优τ+1个变长chunk的划分算法

4．2．2 支持最优变长chunk划分的索引结构

4．2．3 公共签名数量下限的分析

4．3 本章小结

第5章 近似字符串匹配在DBMS中的实现

5．1 无索引结构的DBMS近似字符串匹配方法

5．1．1 无索引的gram在DBMS中的实现

5．1．2 无索引的chunk-gram在DBMS中的实现

5．2 基于索引结构的DBMS近似字符串匹配方法

5．2．1 基于索引的gram在DBMS中的实现

5．2．2 基于索引结构的chunk-gram在DBMS中的实现

5．3 本章小结

第6章 实验与分析

6．1 实验设置

6．2 查询性能对比及分析

6．2．1 查询性能对比

6．2．2 查询性能分析

6．3 索引结构对比

6．4 IndexVGram与CostBasedVGram对比分析

6．5 BestVChunk的进一步分析

6．6 无索引结构的DBMS实现

6．7 本章小结

第7章 结束语

7．1 本文总结

7．2 工作展望

参考文献

致谢

攻硕期间参加的项目及发表的论文