使用编辑距离计算文本相似度-蒲公英云

1. 使用simhash计算文本相似度
2. 使用余弦相似度计算文本相似度
3. 使用编辑距离计算文本相似度
4. jaccard系数计算文本相似度

3. 最小编辑距离计算文本相似度

3.1 编辑距离

概念：

通俗来讲，编辑距离Edit Distance（ED），是指将一个字符串转化为另一个字符串所需的最少操作数。操作包含以下几种：

增：增加一个字符
删：删除一个字符
改：修改一个字符

举例：

将“abc”转化为“acb”。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d4Z3hncA_size_16_color_FFFFFF_t_70_pic_center

通过2次替换操作（即修改）将abc转化为了acb（使用删除再增加操作也可以），所以其最小编辑距离为2。

理论求解：

本质是一个递归问题，即对于两个长度为 L 1 L_1 L1和 L 2 L_2 L2的文本，要计算整个文本的最小编辑距离，就要算出 L 1 − 1 L_1-1 L1−1与 L 2 L_2 L2的编辑距离，然后再加1（针对增加操作的情况，添加最后一个字符），或者算出 L 1 L_1 L1与 L 2 − 1 L_2-1 L2−1的编辑距离，然后再加1（针对删除操作的情况，删除最后一个字符），或者算出 L 1 − 1 L_1-1 L1−1与 L 2 − 1 L_2-1 L2−1的编辑距离，然后再加1（针对修改操作的情况，修改一个字符），然后取这三个的最小值作为上一步的最小编辑距离，以此类推到第一个字符。

简化下以上文字：

假设有两个字符串 A A A, B B B，其长度分别为 L A L_A LA和 L B L_B LB，那么对于3种操作的编辑距离为：

增加操作：
d 1 = E D ( A i − 1 , B j ) + 1 d_1=ED(A_{i-1},B_j)+1 d1=ED(Ai−1,Bj)+1
删除操作：
d 2 = E D ( A i , B j − 1 ) + 1 d_2=ED(A_i,B_{j-1})+1 d2=ED(Ai,Bj−1)+1
修改操作：
d 3 = { E D ( A i − 1 , B j − 1 ) ( A i = B j ) E D ( A i − 1 , B j − 1 ) + 1 ( A i ≠ B j ) d_3=\left\{ \begin{aligned} &ED(A_i-1,B_j-1)&(A_i=B_j) \\ &ED(A_i-1,B_j-1)+1&(A_i≠B_j) \end{aligned} \right. d3={ ED(Ai−1,Bj−1)ED(Ai−1,Bj−1)+1(Ai=Bj)(Ai=Bj)
取这3个中的最小的一个即为最小编辑距离。

所以可以得到一个状态转移方程：
E D A i B j = { m a x ( L A , L B ) ( L A = 0 ∣ ∣ L B = 0 ) m i n { E D ( A i − 1 , B j ) + 1 E D ( A i , B j − 1 ) + 1 E D ( A i − 1 , B j − 1 ) ( A i = B j ) E D ( A i − 1 , B j − 1 ) + 1 ( A i ≠ B j ) ED_{A_iB_j}=\left\{ \begin{aligned} &max(L_A,L_B) &(L_A=0 ||L_B=0)\\ &min\left\{ \begin{aligned} &ED(A_{i-1},B_j)+1 \\ &ED(A_i,B_{j-1})+1 \\ &\begin{aligned} &ED(A_i-1,B_j-1)&(A_i=B_j) \\ &ED(A_i-1,B_j-1)+1&(A_i≠B_j) \end{aligned} \end{aligned} \right. \end{aligned} \right. EDAiBj=⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧max(LA,LB)min⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧ED(Ai−1,Bj)+1ED(Ai,Bj−1)+1ED(Ai−1,Bj−1)ED(Ai−1,Bj−1)+1(Ai=Bj)(Ai=Bj)(LA=0∣∣LB=0)

3.2 计算编辑距离（递归）

public static void main(String[] args) { 
        String s1 = "abc";
        String s2 = "acb";
        System.out.println(dis(s1, s2, s1.length(), s2.length()));
        //2
    }
    static int d = 0;
    private static int dis(String s1, String s2, int i, int j) { 
        if (i == 0 || j == 0) { 
            return Math.max(i, j);
        }
        int op1 = dis(s1, s2, i - 1, j) + 1;
        int op2 = dis(s1, s2, i, j - 1) + 1;
        int op3 = dis(s1, s2, i - 1, j - 1);
        if (s1.charAt(i - 1) != s2.charAt(j - 1)) { 
            op3 += 1;
        }
        return Math.min(Math.min(op1, op2), op3);
    }

3.3 计算编辑距离（动态规划）

public static void main(String[] args) { 
        String s1 = "abc";
        String s2 = "acb";
        System.out.println(dis(s1, s2));
        //2
    }
    private static int dis(String s1, String s2) { 
        int[][] temp = new int[s1.length()][s2.length()];
        for (int i = 0; i < s1.toCharArray().length; i++) { 
            temp[i][0] = i;
        }
        for (int j = 0; j < s2.toCharArray().length; j++) { 
            temp[0][j] = j;
        }
        for (int i = 1; i < s1.toCharArray().length; i++) { 
            for (int j = 1; j < s2.toCharArray().length; j++) { 
                if (s1.charAt(i) == s2.charAt(j)) { 
                    temp[i][j] = temp[i - 1][j - 1];
                } else { 
                    int op1 = temp[i - 1][j] + 1;
                    int op2 = temp[i - 1][j - 1] + 1;
                    int op3 = temp[i][j - 1] + 1;
                    temp[i][j] = Math.min(Math.min(op1, op2), op3);
                }
            }
        }
        System.out.println(Arrays.deepToString(temp));
        return temp[s1.length() - 1][s2.length() - 1];
    }

3.4 最小编辑距离计算相似度

计算公式：
s i m i l a r i t y = 1 − E D A B m a x ( L A , L B ) similarity = 1-\frac{ED_{AB}}{max(L_A,L_B)} similarity=1−max(LA,LB)EDAB

举例：

A：今天天气真好，适合去逛街，也适合晒太阳。;
B：今天天气不错，适合去玩，也适合去晒太阳。;

最小编辑距离： E D A B = 5 ED_{AB}=5 EDAB=5

相似度： s i m i l a r i t y = 1 − E D A B m a x ( L A , L B ) = 1 − 5 20 = 0.75 similarity = 1-\frac{ED_{AB}}{max(L_A,L_B)}=1-\frac{5}{20}=0.75 similarity=1−max(LA,LB)EDAB=1−205=0.75

3.5 总结

最小编辑距离很直接的从字面上反映了两个文本间的差异程度，即两个文本越相似，其编辑距离就越小。但是由这种普通的编辑距离来计算相似度还是有些缺陷，比如：

耗时长
对于短文本来说，速度还是比较快的，但是对于长文本，其速度就不是很理想了。其次，基于动态规划计算时使用的矩阵也会增加不少空间复杂度。以下是对1000字符内，以10为增量，在没有优化的情况下得到的最小编辑距离计算相似度的耗时：
计算不准确
由于只是从文本字面本身来计算的，没有更多的特征来进行进一步判断，所以其结果不是很准确。个人认为可改进的方法有：计算分词后的词语的编辑距离，而不是一个字符的；在计算过程中加入权重等参数进行距离调整；基于同义词词库进行距离调整等等。这个后面陆续再总结。