编辑距离算法的优化与实现.doc

《编辑距离算法的优化与实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编辑距离算法的优化与实现摘要：在分析基于动态规划的编辑距离算法对文本相似度计算的不足的基础上，利用数据结构在空间效率和时间效率上优化该算法、采用中文分词的思想优化和改善该算法的时间效率和准确率，克服了原有的基于动态规划的计算方法所具有的效率低、准确率低、耗存高的缺点。通过多种优化方案的实验测试和分析，结果表明优化后的算法取得了很好的准确率和时空效率，更好的用于文本相似度计算。关键词：编辑距离算法；文本相似度计算；算法优化；动态规划1引言文本相似度的计算在信息检索、文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，长期以来一直是研究的热点和难点。人们在文

2、本相似度计算中使用编辑距离算法，但该方法单纯以字为单位计算各个字符之间的编辑距离，插入删除替换三种基本操作的代价值的方法不够明确合理，从而使计算结果存在一定的偏差。故对传统的文本相似度检测编辑距离算法进行优化和改善，提出了一种基于改进编辑距离和中文分词相融合的计算文本相似度的方法，使优化改善后的算法具有较高的准确率和效率、较低的存储空间，更符合文本相似度计算的要求，有效提高文本相似度算法的效率和准确性，使文本相似度计算的性能进一步改善。2编辑距离算法4.3.1编辑距离定义编辑距离又称Levenshtein距离（也叫做EditDistance），是由俄国科学家Vladim

3、irLevenshtein于1965年在文献[1]中提出的，是一种常用的距离函数度量方法，在多个领域特别是文本相似度检测得到了广泛的应用。编辑距离是指两系列字符串之间只能通过插入、删除和替换三种基本操作把源字符串（S）转换成目标字符串（T）所需的最少基本操作次数。编辑距离值越大，则相似度越小。214.3.1编辑距离算法原理对于求两个字符串之间的编辑距离实际上可以转化为一个求最优解的问题，可以利用动态规划的思想[2]来计算，计算原理的步骤如下表2-1所示：表2-1编辑距离算法原理的计算步骤步骤描述1设置n为源字符串s的长度。设置m为目标字符串t的长度。如果n等于0，返回m

4、并退出。如果m等于0，返回n并退出。构造一个矩阵d[m+1,n+1]含有0..m行和0..n列。2初始化矩阵第一行0..ñ。初始化矩阵第一列0..m。3检查s(ifrom1ton)中的每个字符。4检查t(jfrom1tom)中的每个字符。5如果s[i]等于t[j]，则编辑代价cost为0；如果s[i]不等于t[j]，则编辑代价cost为1。6设置矩阵单元格d[i,j]的值为下面的最小值:a.正上方单元格的值1:d[i-1,j]+1.b.左边单元格的值加1:d[i,j-1]+1.c.对角线单元格的值加上编辑代价cost的值:d[i-1,j-1]+cost.7在完成迭代(3

5、,4,5,6)之后，d[m,n]便是编辑距离的值。本小节将演示如何计算源字符串"GUMBO"和目标字符串"GAMBOL"两个字符串之间的Levenshtein距离，计算步骤如下：步骤1、2步骤3、6，当i=1步骤3、6，当i=221  GUMBO 012345G1  A2  M3  B4  O5  L6    GUMBO 012345G10  A21  M32  B43  O54  L65    GUMBO 012345G101  A211  M322  B433  O544  L655  步骤3、6，当i=3步骤3、6，当i=4步骤3、6，当i=5  GUMBO 01

6、2345G1012  A2112  M3221  B4332  O5443  L6554    GUMBO 012345G10123 A21123 M32212 B43321 O54432 L65543   GUMBO 012345G101234A211234M322123B433212O544321L655432步骤7，编辑距离是矩阵右下角的值，d[m,n]=2；源字符串"GUMBO"变换为目标字符串"GAMBOL"的过程，直观可看出的，即通过将"A"替换为"U"，并在末尾追加"L"字符，这跟计算的结果一致。4.3.1编辑距离以及文本相似度计算编辑距离D（S,T）的计

7、算方法如下所述。首先假设Dij=D(s1…si,,t1…tj)，0≤i≤m,0≤j≤n,Dij表示从s1…si到t1…tj的编辑距离，那么（m+1）×(n+1)阶矩阵Dij可通过下面的（1）式计算得到：0i=0且j=0;Di-1j-1+(ifsi=tjthen0else1);Dij=MinDi-1,j+1;i>0或j>0；(1)式Di,j-1+1;21(1)式包含删除、插入、替换三种操作，该算法是从两字符串的左边开始比较，记录已经比较过的编辑距离，然后进一步得到下一个字符位置时的编辑距离。矩阵Dij能够通过从D00逐步逐列计算获取，最终D