编辑距离 (Levenshtein Distance算法)

一个会写诗的程序员

发布于 2020-04-09 11:55:26

2.6K0

发布于 2020-04-09 11:55:26

文章被收录于专栏：一个会写诗的程序员的博客一个会写诗的程序员的博客

编辑距离是指利用字符操作，把字符串A转换成字符串B所需要的最少操作数。在这里定义的单字符编辑操作有且仅有三种：

插入（Insertion）
删除（Deletion）
替换（Substitution）

譬如，"kitten" 和 "sitting" 这两个单词，由 "kitten" 转换为 "sitting" 需要的最少单字符编辑操作有：

1.kitten → sitten (substitution of "s" for "k")
2.sitten → sittin (substitution of "i" for "e")
3.sittin → sitting (insertion of "g" at the end)

因此，"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。

一般来说，两个字符串的编辑距离越小，则它们越相似。如果两个字符串相等，则它们的编辑距离（为了方便，本文后续出现的“距离”，如果没有特别说明，则默认为“编辑距离”）为0（不需要任何操作）。

不难分析出，两个字符串的编辑距离肯定不超过它们的最大长度（可以通过先把短串的每一位都修改成长串对应位置的字符，然后插入长串中的剩下字符）。

形式化定义

问题描述

给定两个字符串A和B，求字符串A至少经过多少步字符操作变成字符串B。

问题解决

当其中某个字符串长度为0的时候,编辑距离就是另一个字符串的长度. (我们可以理解为, 对长度为0的字符串一直插入字符变成另一个字符串)
当字符串不等的时候, 我们总是习惯性的从字串开头开始看. 那么A[0] = B[0];的时候, 那么此时编辑距离依旧是0, 我们可以直接去除字符串的第一个字符了. 因为此时A与B的编辑距离应该是等于A[1]..A[A.length-1], B[1]..B[B.length-1]两者的编辑距离的. 如果A[0] != B[0], 那么此时我们要考虑的很多了, A[0] 会不会与B[1]相等, 这样只要添加一个字符就可以了. B[0] 会不会与A[1]相等, 或者A[1]与B[1]也不相等. 这样若我们从后面往前看,ij代表a,b 的长度,我们让求编辑距离的方法为f 当 a[i] = a [j] 时候,f(i, j) = f(i-1, j-1); a[i] != a [j] 时候,f(i, j) = f(i-1, j-1) + 1; 或者是 f(i, j-1) +1 或者是f(i-1, j) + 1; 那么此时动态转移方程为

   f(i,j) = max(i,j)  if i与j其中一个为0<br>
   f(i,j) = f(i-1,j-1) if a[i]=a[j]
   f(i,j) = min (f(i-1,j-1) + 1,
                f(i, j-1) + 1,
                f(i-1, j) + 1);

这是一个动态规划问题.使用公式我们可以很快写出递归方法

public static int getEditDistanceByRecursion(String a, String b, int aIndex, int bIntex) {
    if (Math.min(aIndex, bIntex) == 0) {
        return Math.max(aIndex, bIntex);
    }
    if (a.charAt(aIndex) == b.charAt(bIntex)) {
        return getEditDistanceByRecursion(a, b, aIndex - 1, bIntex - 1);
    }

    return Math.min(getEditDistanceByRecursion(a, b, aIndex - 1, bIntex - 1) + 1,
            Math.min(getEditDistanceByRecursion(a, b, aIndex, bIntex - 1) + 1,
                    getEditDistanceByRecursion(a, b, aIndex - 1, bIntex) + 1));
}

但是递归的最大缺点为重复计算. 多次计算同一个结果. 我们需要一个表来存储重复计算的结果.

代码如下

public static int getEditDistance(String origin, String target) {

    if (TextUtils.isEmpty(origin) && TextUtils.isEmpty(target)) {
        return 0;
    }

    if (TextUtils.isEmpty(origin)) {
        return target.length();
    }

    if (TextUtils.isEmpty(target)) {
        return origin.length();
    }

    int[][] dp = new int[origin.length() + 1][target.length() + 1];

    for (int i = 0; i <= origin.length(); i++) {
        dp[i][0] = i;
    }

    for (int j = 0; j <= target.length(); j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= origin.length(); i++) {
        for (int j = 1; j <= target.length(); j++) {
            if (origin.charAt(i - 1) == target.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }

            dp[i][j] = Math.min(dp[i][j], Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
        }
    }
    return dp[origin.length()][target.length()];
}

如果我们需要求两个字符串的相识度,则是:

public static float getSimilarity(String origin, String target) {

    if (TextUtils.isEmpty(origin) || TextUtils.isEmpty(target)) {
        return 0f;
    }

    return 1.0f - getEditDistance(origin, target) / (float) Math.max(origin.length(), target.length());
}

应用与思考编辑距离是NLP基本的度量文本相似度的算法，可以作为文本相似任务的重要特征之一，其可应用于诸如拼写检查、论文查重、基因序列分析等多个方面。但是其缺点也很明显，算法基于文本自身的结构去计算，并没有办法获取到语义层面的信息。

由于需要利用矩阵，故空间复杂度为O(MN)。这个在两个字符串都比较短小的情况下，能获得不错的性能。不过，如果字符串比较长的情况下，就需要极大的空间存放矩阵。例如：两个字符串都是20000字符，则 LD 矩阵的大小为：20000 * 20000 * 2=800000000 Byte=800MB。