文本相似度算法之编辑距离算法

定义

编辑距离又称Leveinshtein距离，是由俄罗斯科学家Vladimir Levenshtein在1965年提出。

以字符串为例，字符串a和字符串b的编辑距离是将a转换成b的最小操作次数，这里的操作包括三种：

插入一个字符

删除一个字符

替换一个字符

举个例子，

计算learning和meaning的编辑距离，需要下列步骤

learning -> mearning 将k替换成smearning -> meaning 将r删除

至少要做2次操作，编辑距离为2

公式

用eda,b(i,j)ed_{a,b}(i,j)eda,b​(i,j)来表示a,b字符串的编辑距离，其中i代表a的长度，j代表b的长度

eda,b(i,j)={min(i,j)=0max⁡(i,j)ai=bjeda,b(i−1,j−1)ai&lt;&gt;bjmin⁡(eda,b(i−1,j−1)+1,eda,b(i−1,j)+1,eda,b(i,j−1)+1)ed_{a,b}(i,j)=\left\{ \begin{aligned} min(i,j) =0 &amp;&amp; \max(i,j) \\ a_i = b_j &amp;&amp; ed_{a,b}(i-1,j-1)\\ a_i &lt;&gt; b_j &amp;&amp; \min(ed_{a,b}(i-1,j-1)+1,ed_{a,b}(i-1,j)+1,ed_{a,b}(i,j-1)+1) \end{aligned} \right. eda,b​(i,j)=⎩⎪⎨⎪⎧​min(i,j)=0ai​=bj​ai​<>bj​​​max(i,j)eda,b​(i−1,j−1)min(eda,b​(i−1,j−1)+1,eda,b​(i−1,j)+1,eda,b​(i,j−1)+1)​

eda,b(i,j)ed_{a,b}(i,j)eda,b​(i,j)的值描述如下：

min(i,j)=0 代表有一个字符串为空，编辑距离就是另一个非空字符串的长度当字符aia_iai​值等于bjb_jbj​的时候，编辑距离就是a,b字符串上一个字符的编辑距离eda,b(i−1,j−1)ed_{a,b}(i-1,j-1)eda,b​(i−1,j−1)当aia_iai​值不等于bjb_jbj​的时候，编辑距离如下三种情况的最小值 eda,b(i−1,j)+1ed_{a,b}(i-1,j)+1eda,b​(i−1,j)+1 删除aia_iai​eda,b(i,j−1)+1ed_{a,b}(i,j-1)+1eda,b​(i,j−1)+1 插入bjb_jbj​eda,b(i−1,j−1)+1ed_{a,b}(i-1,j-1)+1eda,b​(i−1,j−1)+1 替换bjb_jbj​

矩阵

在前面的公式中，我们可以很明显的感觉到可以用一个二维矩阵来表达该距离

我们用learn(a)和mean(b)比较简单的单词用矩阵来表达：

初始化：在矩阵的第1行的时候，表示b的长度为0，根据第一个规则，当b长度为0的时候，a的编辑距离就是a字符串的长度，也就是mean的1，2，3，4，反之第一列也是如此

如此持续迭代，直至推导最终结果

最后的编辑距离就是2

算法优化

当i<j的时候，最小的时间复杂度O(i2)(i^2)(i2)，最小空间复杂度是O(2∗i)(2*i)(2∗i)

为何复杂度不是O(i∗j)(i*j)(i∗j)?

当我们只是计算编辑距离的时候，只是求矩阵的最后一个值。当字符串的长度i<j的时候，我们并不需要继续计算在区间i到j的距离，因为在这种场景下只是插入字符到尾部，依据定义，只要将(j-i-1)差值直接加上就可，无需在继续计算

为何最小空间复杂度是O(2∗i)(2*i)(2∗i)

在我们计算的时候，发现只是需要2行也就是当前行和前一行的状态，所以没必要保存完整的矩阵，而只需要保存2行矩阵

优化后的代码如下：

public static int editDistance(String left, String right) {if(left.length() > right.length()) {String tmp = left;left = right;right = tmp;}int x,y,gap = 0;if(right.length() == left.length()) {x = left.length();y = x;} else {x = left.length()+1;y = left.length();gap = right.length() - left.length() -1;}int[] pre = new int[ y + 1];int[] cur = new int[ y + 1];for (int i = 0; i < pre.length; i++) {pre[i] = i;}for (int i = 1; i <= x; i++) {cur[0] = i;for (int j = 1; j <= y; j++) {if (right.charAt(i - 1) == left.charAt(j - 1)) {cur[j] = pre[j - 1];} else {cur[j] = Math.min(cur[j - 1], Math.min(pre[j], pre[j - 1])) + 1;}}int[] tmp = pre;pre = cur;cur = tmp;}return pre[pre.length - 1]+gap;}