编辑距离快速算法研究

论文摘要

字符串匹配技术是计算机科学中研究最为广泛的问题之一,在众多领域中发挥着重要的作用。通常,衡量两个字符串之间的匹配程度是通过计算两个字符串之间的距离函数来确定的,而编辑距离是衡量两个字符串的匹配程度最常用的距离函数指标。所以,编辑距离问题已经成为信息理论和计算机科学研究领域中的一个重点问题。编辑距离又称Levenshtein距离,是由俄罗斯科学家Vladimir Levenshtein在1965年提出的。目前,计算编辑距离最常使用的算法是动态规划算法。动态规划算法的时间复杂度为O（mm）,时间开销很大,寻找一种新的编辑距离快速算法意义重大。基于此,本文对编辑距离算法作进一步的研究和改进。本文的主要内容为：首先对字符串相似匹配进行了定义,介绍了近似字符串相似匹配相关技术的理论及主要研究方法,并对基于FFT（快速傅里叶变换）的序列相似性进行了研究。为了实现编辑距离的快速计算,本文利用快速傅里叶变换和线性卷积的思想,首先提出了一种新的距离函数：基于FFT的字符串距离函数FFT-D,并利用字符串距离函数FFT-D提出了字符串过滤方法,通过对数据集的过滤,实现减少一些不必要的编辑距离计算,从而提高了字符串匹配的效率。最后,本文还提出了基于线性卷积思想的编辑距离LC-ED算法,该算法的最重要特点就是利用插入空格代替插入和删除操作,即通过对两个字符串序列的不同位置比对,找到插入空位的数量以及位置,从而实现编辑距离的快速计算。该算法在理论上和实践中均有较好的表现。实验测试表明本文所提出的方法可以有效地解决编辑距离快速计算的问题。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 面临的挑战及本文贡献
• 1.3 本文的组织结构
• 第2章 相关技术
• 2.1 字符串的相似匹配的定义
• 2.2 字符串的相似匹配的相关技术
• 2.2.1 动态规划技术
• 2.2.2 QUASAR技术
• 2.2.3 文本分片技术
• 2.2.4 多模式匹配
• 2.2.5 基于过滤的技术
• 2.3 本章小结
• 第3章 问题定义
• 3.1 字符串的编辑距离与编辑操作
• 3.2 常见的距离函数
• 3.3 问题定义
• 3.4 本章小结
• 第4章 基于FFT的序列相似性研究
• 4.1 DFT的基本概念
• 4.1.1 离散傅里叶级数（DFS）的性质
• 4.1.2 非周期序列和周期序列的一般关系
• 4.1.3 离散傅里叶变换（DFT）
• 4.1.4 离散傅里叶变换（DFT）的性质
• 4.2 FFT与卷积
• 4.2.1 快速傅里叶变换（FFT）的基本思想
• 4.2.2 快速傅里叶变换（FFT）与线性卷积
• 4.3 基于快速傅里叶变换（FFT）的序列相似性
• 4.3.1 基于FFT的序列相似性的基本方法
• 4.3.2 基于FFT的序列相似性的数据压缩方案
• 4.4 本章小结
• 第5章 基于卷积思想的编辑距离算法
• 5.1 基于FFT的字符串距离FFT-D函数
• 5.2 基于FFT-D距离函数的字符串过滤方法
• 5.2.1 基于FFT-D距离的过滤算法
• 5.2.2 基于FFT-D的序列相似性查询系统设计
• 5.3 编辑距离的重定义
• 5.3.1 编辑距离重定义概念
• 5.3.2 编辑距离重定义理论分析
• 5.4 基于卷积的编辑距离LC-ED算法
• 5.4.1 基于卷积的编辑距离LC-ED算法思想
• 5.4.2 基于卷积的编辑距离插入与删除操作的处理
• 5.4.3 基于卷积的编辑距离LC-ED基本算法
• 5.4.4 优化基于卷积的编辑距离LC-ED算法
• 5.5 本章小结
• 第6章 实验与分析
• 6.1 测试环境
• 6.2 测试方案
• 6.2.1 测试数据
• 6.2.2 测试方案设计
• 6.3 测试结果与分析
• 6.4 本章小结
• 第7章 结论和展望
• 7.1 工作总结
• 7.2 工作展望
• 参考文献
• 致谢
• 攻硕期间参加的项目及发表的论文