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