《编辑距离-计算字符串相似度》由会员分享，可在线阅读，更多相关《编辑距离-计算字符串相似度（3页珍藏版）》请在金锄头文库上搜索。
1、基于编辑距离求两个字符串的相似度最近在编程之美这本书上看到这样一道题，计算两个字符串的相似度。首先得明确的是两个字符串的相似度有很多定义，既有字符表面意义的，如apple和applet很接近只相差1个字符，但是意思相差很远，也有基于语义的，如person和people，人的单复数，但是相差了好几个字符。这里主要讨论字符表面意义的相似度。在给出字符串表面意义的相似度之前首先给出编辑距离的概念。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。例如将kitten一字转成sitting：sitten （ks）
2、sittin （ei） sitting （g）总共需要三次变换，那么他们之间的距离就是3定义：相似度=1/(编辑距离+1)，那么kitten和sitting的相似度就是0.25那么如何计算编辑距离呢？编程之美上给的解法个人没看懂。于是搜索出另外一种解法，简易明确。算法思路如下：给出字符串s1，字符串s2，长度分别是m和n。 初始化：构造一个矩阵distance，(m+1)(n+1)，其中第一行写上0-m，第一列写上0-n。 构造：给每个矩阵元素赋值，赋值规则如下，如果当前指向的s1和s2中的元素相同，那么设cost为0否则为1.比较当前赋值元素current的左边的值(left)，上面的值(t
3、op)，左上角的值(left-top)，取出最小值min。如果min是left或top，那么current=min+1.否则current=min + cost。 依次赋值，distancemn就是两个字符串的编辑距离。例子：kitten和sitting的距离矩阵如下：原理：为什可以这样做呢？为什么这样做能够求出两个字符串的编辑距离呢？自己的考量如下，各位看官若有不对，不完善之处，恳请纠正。 首先看初始化，第一行0-m，显然是空字符到一个长度m的字符串的距离，就是依次加上去呗！执行插入操作。第一列的值也是同样的道理。 那么第二步构造是啥意思呢？为了简便起见，假设我们正在填distance33。
4、该点的值无非是三种选择。a) current = left+1 = 3 执行插入操作。依次变化为ki-si-s-sib) current = top+1 = 3 执行删除操作。依次变化为ki-si-sii-sic) current = left-top+cost = 1 不执行任何操作。 依次变化为ki-si。显然这种方式最优用装逼语言描述如下：设s1=a1,am-1,am. s2=b1,bn-1,bn。由s1到s2经过这三种途径（保证完备性） 由a1,am-1,am到b1,bn-1,最后插入bn 由a1,am-1到b1,bn-1,bn,最后删除am 由a1,am-1到b1,bn-1,最后将a
5、m改成bn这上述三种方式对应上面的a,b,c三种方式。因此我们取他们之间的最小值然后得到当前距离可能能保持最小，即编辑距离。附Java代码class editDistance private String s1;private String s2;public editDistance(String s1,String s2) this.s1 = s1;this.s2 = s2;public double getSimilarity() int matrix=new ints1.length()+1s2.length()+1; int i,j; int cost=0; /初始化矩阵 for (
6、i=0;i=s1.length();i+) matrixi0=i; for (j=0;j=s2.length();j+) matrix0j=j; for (i=1;i=s1.length();i+) for (j=1;j=s2.length();j+) /字符不等时，cost为1，否则为0 if (s1.charAt(i-1)!=s2.charAt(j-1) cost=1; int left=matrixij-1; int top=matrixi-1j; int left_top=matrixi-1j-1; int min=(lefttop)?left:top; matrixij=left_tops2.length()?s1.length():s2.length(); return sim;public static void main(String args) String s1 = apple;String s2 = applet;editDistance ed = new editDistance(s1,s2);System.out.print(The similarity between s1 and s2 is:);System.out.println(ed.getSimilarity();
