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

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

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

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

4、有0.m行和0.n列。2初始化矩阵第一行0.ñ。初始化矩阵第一列0.m。3检查 s (i from 1 to n) 中的每个字符。4检查 t (j from 1 to m) 中的每个字符。5如果 si 等于 tj，则编辑代价cost为0；如果 si 不等于 tj，则编辑代价cost为1。6设置矩阵单元格d i,j 的值为下面的最小值:a. 正上方单元格的值1: di-1,j + 1.b. 左边单元格的值加1: di,j-1 + 1.c. 对角线单元格的值加上编辑代价cost的值: di-1,j-1 + cost.7在完成迭代 (3, 4, 5, 6) 之后，dm,n便是编辑距离的值。

5、本小节将演示如何计算源字符串"GUMBO"和目标字符串"GAMBOL"两个字符串之间的Levenshtein距离，计算步骤如下：步骤1、2 步骤3、6，当i=1 步骤3、6，当i=2  GUMBO 012345G1  A2  M3  B4  O5  L6    GUMBO 012345G10  A21  M32  B4

6、3  O54  L65    GUMBO 012345G101  A211  M322  B433  O544  L655  步骤3、6，当i=3 步骤3、6，当i=4 步骤3、6，当i=5  GUMBO 012345G1012  A2112  M3221  B4332  O54

7、43  L6554    GUMBO 012345G10123 A21123 M32212 B43321 O54432 L65543   GUMBO 012345G101234A211234M322123B433212O544321L655432步骤7，编辑距离是矩阵右下角的值，dm,n=2；源字符串"GUMBO"变换为目标字符串"GAMBOL"的过程，直观可看出的，即通过将"A&quo

8、t;替换为"U"，并在末尾追加"L"字符，这跟计算的结果一致。4.3.3 编辑距离以及文本相似度计算编辑距离D（S,T）的计算方法如下所述。首先假设Dij=D(s1si, t1tj)，0im,0jn, Dij表示从s1si到t1tj的编辑距离，那么（m+1）×(n+1)阶矩阵Dij可通过下面的（1）式计算得到： 0 i=0且j=0;Di-1 j-1+(if si= tj then 0 else 1); Dij= Min Di-1,j+1; i>0或j>0； (1)式 Di,j-1+1; (1)式包含删除、插入、替换三种操作，该算法是

9、从两字符串的左边开始比较，记录已经比较过的编辑距离，然后进一步得到下一个字符位置时的编辑距离。矩阵Dij能够通过从D00逐步逐列计算获取，最终Dmn表示D(S，T)的值，即S和T的编辑距离。文本相似度计算3：编辑距离越大，相似度越小。假设源字符串S与目标字符串T长度的最大值为Lmax，编辑距离为LD，相似度为SI，则相似度SI的计算如（2）式所示。SI=1-LD/Lmax (2)式4.3.4 编辑距离算法核心代码public int LevenshteinDistance(string strs1, string strs2) char str1=strs1.ToCharArray(); ch

10、ar str2=strs2.ToCharArray(); int i,j,temp; if (str1.Length = 0) temp = str2.Length; if (str2.Length = 0) temp = str1.Length; int, dist = new intstr1.Length + 1, str2.Length + 1; for(i=0;i<=str1.Length;i+) disti,0=i; for(i=0;i<=str2.Length;i+) dist0,i=i; for(i=1;i<=str1.Length;i+) for(j=1;j&

11、lt;=str2.Length;j+) if( str1i-1 = str2j-1) disti,j=disti-1,j-1; else disti, j = LowerOfThree(disti, j - 1, disti - 1, j-1, disti - 1, j) + 1; temp = diststr1.Length, str2.Length; return temp;4.3.5 编辑距离算法分析假设m, n分别表示源字符串S和目标字符串T的长度，则上述的基于动态规划的编辑距离算法，其算法的空间复杂度为O（mn），时间复杂度为O（mn）。尽管编辑距离算法在文本相似度检测方面具有一定的

12、优势，具有简单易于计算，并有一定的正确率，但仍然存在一些问题。（1）此编辑距离算法忽略了序列长度对编辑距离产生的影响，没有考虑到算法所需的内存，因而造成所耗内存较大。（2）单纯以字为单位计算各个字符之间的编辑距离，计算出来的距离只是文字表面的距离，并没有充分考虑词语的概念，使得计算结果的语义准确率不高，特别是对中文的检测时常常得不到满意的结果。针对以上两个问题，下文提出了几种优化方案，分别是基于算法结构的内部调整优化以及基于词语相似度的文本计算，通过大量的实验测试证明了可降低计算所耗的存储空间，提高了算法的效率和准确率。 3 改进编辑距离算法3.1 空间复杂度优化经过对上面的传统编辑距离算法计

13、算过程的分析，发现算法中作为存储的二维矩阵，在每一个循环中，其实只有一行的数据参与了计算，之前的数据行都不再参与计算了。因此，从这个出发点入手，对算法结构进行调整，将二维数组改为两个一维数组。经测试，计算结果和速度没有太大的差异。但空间复杂度减少了很多，改进后空间复杂度降为：O（min(m,n）。设置n为源字符串s的长度，m为目标字符串t的长度。我们不妨设n<m，即源字符串s的长度较小，那么空间复杂度优化的编辑距离算法步骤如表3-1： 表3-1 空间复杂度优化的编辑距离算法步骤步骤描述1设置n为源字符串s的长度。设置m为目标字符串t的长度。如果n等于0，返回m并退出。如果m等于0，返回n

14、并退出。构造两个一维数组v0n+1 和v1n+1，串联0.n之间所有的元素。2初始化v0 to 0.n。3检查 t (j from 1 to m) 中的每个字符。4检查 s (i from 1 to n) 中的每个字符。5如果 si 等于 tj，则编辑代价cost为0；如果 si 不等于 tj，则编辑代价cost为1。6设置一维数组单元格v1i 的值为下面的最小值:a. 正上方单元格的值1: v0i + 1.b. 左边单元格的值加1: v1i-1 + 1.c. 对角线单元格的值加上编辑代价cost的值: v0i-1 + cost.7在完成迭代 (3, 4, 5, 6) 之后，v1n便是编辑距离

15、的值。本小节仍以源字符串"GUMBO"和目标字符串"GAMBOL"来演示如何计算这两个字符串之间的Levenshtein距离，计算步骤如下：步骤1、2 步骤3、6，当i=1 步骤3、6，当i=2   GUMBOV0 012345V1G    A  M  B  O  L     GUMBOv0 012345V1G1012 34A&

16、#160; M  B  O  L     GUMBO  012345v0G101234V1A211234M  B  O  L  步骤3、6，当i=3 步骤3、6，当i=4 步骤3、6，当i=5   GUMBO  012345G101234V0A211234V1M322123B  O  L&

17、#160;    GUMBO  012345G101234A211234V0M322123V1B433212O L    GUMBO  012345G101234A211234M322123V0B433212V1O544321L步骤3、6，当i=6   GUMBO  012345G101234A211234M322123B433212V0O544321V1L655432步骤7，右下角的值便是编辑距离的值，v1n=2；

18、传统的编辑距离算法会创建一个矩阵dm+1,n+1,但此经过优化的算法将会创建两个一维数组v0n+1 和v1n+1，其计算结果没有发生变化，但内存占用更少，其空间复杂度可为两个字符串长度的最小值O(min(m，n)。在经过空间复杂度优化的编辑距离算法，其编辑步数一样，因而相应的文本相似度计算的结果也一样。编辑距离算法的空间复杂度优化核心代码如下：public int LevenshteinDistance(string strs1, string strs2) char str1 = strs1.ToCharArray(); char str2 = strs2.ToCharArray(); in

19、t i, j,temp; if (str1.Length = 0) temp = str2.Length; if (str2.Length = 0) temp = str1.Length; int, dist = new int2, str2.Length + 1; for (i = 0; i <= str2.Length; i+) dist0, i = i; for (i = 1; i <= str1.Length; i+) dist1, 0 = i; for (j = 1; j <= str2.Length; j+) if (str1i - 1 = str2j - 1)

20、dist1, j = dist0, j - 1; else dist1, j = LowerOfThree(dist0, j - 1, dist0, j, dist1, j - 1) + 1; for (j = 0; j <= str2.Length; j+) dist0, j = dist1, j; temp = dist1, str2.Length; return temp;3.2 时间效率优化4.3.1 编辑距离算法的时间效率优化思想在对上面的传统编辑距离算法仔细分析后，发现两个字符串相对应位置上的字符相同时，把这两个相对应的相同的字符删除掉后，对计算结果没有任何影响。删除这些相对

21、应位置相同的字符后将会减少编辑计算的字符，即参与计算的两字符的长度变短，从而使得计算的时间效率加快，达到提高算法时间效率的效果。再者，针对于纯中文的文本，我们考虑到文本中的标点符号也会被当成一个独立的字符参与计算，但是这些标点符号对于我们所要计算的文本相似度来说毫无意义。因此可采取的做法就是把这些标点符号全部删除，只保留文字，用纯文字的字符来参与计算，这样将会使得参与计算的字符长度变短，加快计算的速率，减少计算所占用的内存空间，而且使得计算的结果更加地符合实际，获得更高的准确率。4.3.2 编辑距离算法的时间效率优化原理步骤一：把源字符串S里含有的标点符号用空格替换掉。步骤二：把源字符串S中所

22、含的空格全部清除。步骤三：把目标字符串T里含有的标点符号用空格替换掉。步骤四：把目标字符串T中所含的空格全部清除。步骤五：把去除标点符号的源字符串S转换成一维字符数组S1。步骤六：把去除标点符号的目标字符串T转换成一维字符数组T1。步骤七：从两数组的起始位置开始，比较S1和T1中相对应位置的字符是否相等，若相等，则S1和T1中相对应位置的字符将用空格代替。步骤八：从两数组的末尾位置开始，比较S1和T1中相对应位置的字符是否相等，若相等，则S1和T1中相对应位置的字符将用空格代替。步骤九：把经过步骤五、六后的数组S1转换成字符串S2，并把里面所含的空格全部清除。步骤十：把经过步骤五、六后的数组T

23、1转换成字符串T2，并把里面所含的空格全部清除。步骤十一:再把所得到的字符串S2和字符串T2进行计算它们之间的编辑距离。本小节以源字符串S“计算机,不怕你!”和目标字符串T“物理机电,谁怕谁?”来演示如何计算这两个字符串之间的Levenshtein距离。计算机，不怕你！源字符串S:物理机电，谁怕谁？目标字符串T: 计算机 不怕你步骤一：源字符串S:计算机不怕你步骤二：源字符串S:物理机电 谁怕谁 步骤三：目标字符串T: 物理机电谁怕谁步骤四：目标字符串T:计算机不怕你步骤五：字符数组S1:物理机电谁怕谁步骤六：字符数组T1:步骤七：计算不怕你物理电谁怕谁字符数组S1:字符数组T1:计 算 不

24、你 步骤八:字符数组S1:物 理 电 谁 谁字符数组T1:计算不你 步骤九：源字符串S2:物理电谁谁步骤十：目标字符串T2:步骤十一：计算字符串S2和字符串T2之间的编辑距离，如表3-2所示。表3-2 字符串S2和字符串T2之间的编辑距离计算计算不你01234物11234理22234电33334谁44444谁55555步骤十一右下角的值便是源字符串S“计算机,不怕你!”和目标字符串T“物理机电,谁怕谁?”的编辑距离的值，编辑步数为5。4.3.3 编辑距离算法的时间效率优化比较和分析源字符串S“计算机,不怕你!”和目标字符串T“物理机电,谁怕谁?”在没有经过时间效率优化的编辑距离算法，其算法步骤

25、如表3-3所示：表3-3 源字符串S和目标字符串T之间的编辑距离计算计算机，不怕你！012345678物112345678理222345678机333234567电444334567，555434567谁666544567怕777655456谁888766556？999877666右下角的值为源字符串S“计算机,不怕你!”和目标字符串T“物理机电,谁怕谁?”的编辑距离的值，编辑步数为6，则它们所对应的文本相似度计算为：因为Lmax= Max(S.Length,T.Length)=9；所以 SI=1-LD/ Lmax=1-6/933.33%经过时间效率优化后的编辑距离算法，它们的编辑步数为5，则

26、它们所对应的文本相似度的计算为：因为Lmax= Max(S1.Length,T1.Length)=7；（即为两个字符串删除标点符号后的字符串长度的最大值。）所以 SI=1-LD/ Lmax=1-5/728.57%对这两个文本相似度计算的结果分析，容易发现经过时间效率优化后的编辑距离算法更符合实际情况，更加实用。删除了字符串中标点符号和相对应位置的相同的字符后，使得计算量减少，所占内存减少，并加快了计算的效率，提高了准确率。4.3.4 编辑距离算法的时间效率优化核心代码string s1 = Regex.Replace(string1, "u4e00-u9fa5s", &qu

27、ot; ");string ss1 = Regex.Replace(s1, "s", "");string s2 = Regex.Replace(string2, "u4e00-u9fa5s", " ");string ss2 = Regex.Replace(s2, "s", "");if (ss1.Length < ss2.Length) string ss3; ss3 = ss1; ss1 = ss2; ss2 = ss3;char strs1 = ss1

28、.ToCharArray();char strs2 = ss2.ToCharArray();int k = 0;Stopwatch watch = new Stopwatch();watch.Start();for (int i = 0; i < strs2.Length; i+) if (strs2i = strs1i) strs1i = Convert.ToChar(" "); strs2i = Convert.ToChar(" "); if (strs1.Length != strs2.Length) for (int j = strs1.L

29、ength - strs2.Length; j < strs1.Length; j+) if (strs1j = strs2k) strs1j = Convert.ToChar(" "); strs2k = Convert.ToChar(" "); k+; string word1 = new String(strs1);string str1 = Regex.Replace(word1, "s", "");string word2 = new String(strs2);string str2 = Rege

30、x.Replace(word2, "s", "");3.3 准确率优化4.3.1 编辑距离算法的准确率优化思想对传统的编辑距离算法分析，发现单纯以字为单位计算字符串之间的编辑距离，计算出的语义距离4和实际情况出入很大，而且序列长度对代价函数的计算结果也有很大的影响，针对这些情况，下文提出了一种基于词语的编辑距离算法5的文本相似度检测方法，对字符串进行分词后进行编辑计算，从而使得计算结果更符合字符串词语相似度计算的要求，计算的速率和文本相似度的准确率都得以提高，使文本相似度计算的性能进一步改善，更符合实际情况。4.3.2 中文分词介绍中文分词6指的是使用计

31、算机自动对中文文本进行词语切分，将一个汉字序列切分成一个个单独的词，即像英文那样使中文句子中的词之间有空格以标识。而中文之间仅能通过标点符号、句和段作为分界符来简单划分，中文的划分比英文的划分要复杂的多、困难的多。因此对于中文分词一般都采用分词技术来进行分词。目前的分词方法可以分为两类，一是基于统计的方法, 一种是基于字典的方法。基于统计的方法一般精度低。基于字典的方法精度高, 实现简单。因此本文所提出改进算法是选用一种基于字典方法的“盘古分词”作为中文分词匹配时的词库。盘古分词的分词技术7相当成熟，在词频优先、歧义问题、中文未登录词识别、中文人名识别等方面有着非常好的功能，相对较完善。如：

32、输入：我爱吃苹果分词结果：我|爱|吃|苹果|输入：我喜欢吃香蕉分词结果：我|喜欢|吃|香蕉|4.3.3 编辑距离算法的准确率优化原理经过准确率优化的编辑距离算法以词语为单位代替以字为单位进行计算，基本步骤如下：步骤一：对源字符串S进行分词。步骤二：对目标字符串T进行分词。步骤三：把源字符串S分词后的词语组成数组S1。步骤四：把目标字符串T分词后的词语组成数组T1。步骤五：对数组S1与数组T1进行编辑距离计算。本小节以源字符串S“我爱吃苹果”和目标字符串T“我喜欢吃香蕉”来演示如何计算这两个字符串之间的Levenshtein距离。源字符串S: 我爱吃苹果目标字符串T: 我喜欢吃香蕉步骤一：我|爱

33、|吃|苹果|步骤二：我|喜欢|吃|香蕉|我爱吃苹果步骤三：数组S1：我喜欢吃香蕉步骤四：数组T1：步骤五：数组S1与数组T1的编辑距离计算结果如表3-4所示：表3-4 数组S1与数组T1的编辑距离计算我爱吃苹果01234我10123喜欢21123吃32212香蕉43322步骤五右下角的值便是源字符串S“我爱吃苹果”和目标字符串T“我喜欢吃香蕉”的编辑距离的值，编辑步数为2。4.3.4 编辑距离算法的准确率优化比较和分析源字符串S“我爱吃苹果”和目标字符串T“我喜欢吃香蕉”在没有经过时间效率优化的编辑距离算法，其算法步骤如表3-5所示：表3-5源字符串S与目标字符串T的编辑距离计算我爱吃苹果01

34、2345我101234喜211234欢322234吃433234香544334蕉655444右下角的值为源字符串S“我爱吃苹果”和目标字符串T“我喜欢吃香蕉”的编辑距离的值，编辑步数为4，则它们所对应的文本相似度计算为：因为Lmax= Max(S.Length,T.Length)=6；所以 SI=1-LD/ Lmax=1-4/633.33%经过时间效率优化后的编辑距离算法，它们的编辑步数为2，则它们所对应的文本相似度的计算为：因为Lmax= Max(S1.Length,T1.Length)=4；（即为两个字符串删除标点符号后的字符串长度的最大值。）所以 SI=1-LD/ Lmax=1-2/45

35、0%对这两个文本相似度计算的结果分析，我们可以看出，单纯以字为单位的编辑距离算法，在汉语中，单个的字往往是不具备意义的。例如上面的“苹”、“果”等字, 并不能反映其所合成词的意义，计算出的语义距离与实际情况有很大的出入。因此本文采用分词的思想，用词语代替单个汉字或者字符作为基本的编辑单元参与运算，充分考虑词语的概念，是一种基于词语的编辑距离算法，使得计算的结果更符合文本相似度计算的要求，并且提高了计算的速度和提高了准确率。4.3.5 编辑距离算法的准确率优化核心代码public class WordSegmentpublic static string GetWords(string word

36、) return Segment(word); private static string Segment(string word) Analyzer analyzer = new PanGuAnalyzer(); TokenStream tokenStream = analyzer.TokenStream("", new StringReader(word);Lucene.Net.Analysis.Token token = null; string txt = "" while (token = tokenStream.Next() != null)

37、txt += token.TermText() + "|" string segmentword = txt.Split(new char '|' , StringSplitOptions.RemoveEmptyEntries); return segmentword; 4 实验测试和结果分析4.1 实验环境本文实验是在Windows XP操作系统、Microsoft Visual Studio 2005的开发环境下，通过C#语言8实现的一个算法应用原型软件，用于测试算法的运行结果以及统计分析。4.2 实验目的通过实验测试分析上面提出的编辑距离算法是否正确，

38、以及通过实验数据的统计和分析得出实验结论。4.3 实验内容根据上面的提出的三种优化方案，本实验提出了五种实验方案，采用对比的方法来测试分析各优化方案的结果的差异，进而得出实验结论。实验结果的数据包括编辑距离算法计算的编辑步数、文本相似度、计算所用时间、所耗内存等。4.3.1 原方案与方案一比较分析本小节以源字符串“GUMBO”和目标字符串“GAMBOL”为例，计算它们之间的编辑距离，原方案为传统的编辑距离算法，方案一为经过空间复杂度优化的编辑距离算法，实验结果如图4-1所示： 图4-1 原方案和方案一的编辑距离算法计算结果图由实验测试结果，可见方案一算法结果中的编辑步数、文本相似度和计算时间跟

39、原方案的结果一样，所耗内存比原方案少很多。由此可以证明前面提出的编辑距离算法的空间复杂度的优化原理是正确的，改进后的编辑距离算法有效地提高算法运算过程中所耗的内存。4.3.2 原方案与方案二、三比较分析由于没有标准的文本相似度测试资料，所以实验所有的资料都是由我们自己构造。本小节实验所用的资料来源于图书文章的截取。原方案为传统的编辑距离算法，方案二为经过时间效率优化的编辑距离算法，方案三为在方案二优化的基础上，增加了空间复杂度的优化。实验结果如图4-2、4-3、4-4、4-5所示：图4-2 两个完全一样的字符串的编辑距离计算结果图4-3 两个相似度很大的字符串的编辑距离计算结果图4-4 两个相

40、似度接近50%的字符串的编辑距离计算结果图4-5 两个相似度很小的字符串编辑距离计算结果由图4-2、4-3、4-4、4-5实验结果分析，可见方案二的算法结果中的编辑步数、文本相似度与原方案的计算结果相差不大，计算时间和所耗内存的大小随着两字符串的文本相似度的增大而不断减小。方案三在方案二优化的基础上，增加了空间复杂度的优化，使得算法所耗的内存更少。由此可以证明上面提出的编辑距离算法的时间效率的优化原理是正确的，改进后的编辑距离算法，使得参与计算的字符串序列变短，所耗内存减少，加快了计算的速率，提高了准确率。4.3.3 原方案与方案四、五比较分析本小节以源字符串“我爱吃苹果”和目标字符串“我喜欢吃香蕉”为例，计算它们之间的编辑距离，原方案为传统的编辑距离算法，方案四为经过准确率优化的编辑距离算法，方案五为在方案四优化的基础上，增加了空间复杂度的优化。实验结果如图4-6所示：图4-6 原方案和方案四、五的编辑距离算法计算结果图由