目录

•写在前面

•什么是编辑距离？

•思路

•思路可视化

•代码实现

•写在前面

编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。最简单的方法是检查所有可能的编辑序列，从中找出最短的一条。但这个序列总数可能达到指数级，但完全不需要这么多，因为我们只要找到距离最短的那条而不是所有可能的序列。这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的，所以也叫 Levenshtein 距离。总是比较相似的，或多或少我们可以考虑编辑距离。我们在解决这个问题中，使用动态规划的思想进行求解。

•什么是编辑距离？

这里给一个题目的描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作。

• 插入一个字符
• 删除一个字符
• 替换一个字符

为了更好的理解，我这里给出两个示例，帮助理解这个概念

示例一：

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例二：

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

•思路

我们的目的是让问题简单化，比如说两个单词 horse 和 ros 计算他们之间的编辑距离 D，容易发现，如果把单词变短会让这个问题变得简单，很自然的想到用 D[n][m] 表示输入单词长度为 n 和 m 的编辑距离。具体来说，D[ i ][ j ] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。

更通俗的理解，假设我们可以使用d[ i , j ]个步骤（可以使用一个二维数组保存这个值，使用动态规划的思想），表示将串s[ 1…i ] 转换为串t [ 1…j ]所需要的最少步骤个数，那么，在最基本的情况下，即在 i 等于 0 时，也就是说串 s 为空，那么对应的d[ 0 , j ] 就是 增加 j 个字符，使得 s 转化为 t，在 j 等于 0 时，也就是说串 t 为空，那么对应的 d[ i, 0] 就是 减少 i 个字符，使得 s 转化为 t。

更一般的情况，加一点动态规划的想法，我们要想得到将 s[1..i] 经过最少次数的增加，删除，或者替换操作就转变为 t[1..j]，那么我们就必须在之前可以以最少次数的增加，删除，或者替换操作，使得现在串 s 和串 t 只需要再做一次操作或者不做就可以完成 s[1..i] == t[1..j] 的转换。所谓的“之前”分为下面三种情况：

• 要得到 s[1…i] == t[1…j-1]，需要 k 个操作
• 要得到 s[1..i-1] == t[1..j]，需要 k 个操作
• 要得到 s[1…i-1] == t [1…j-1]，需要 k 个操作

在上面的这三种情况的基础下，我们需要得到 s[1..i] == t[1..j] ，我们分别给出解决思路，如下

• 第1种情况，只需要在最后将 t[1…j-1] 加上 s[i] 就完成了匹配，这样总共就需要 k+1 个操作。
• 第2种情况，只需要在最后将 s[1..i-1] 加上 t[j] 就完成了匹配，所以总共需要 k+1 个操作。
• 第3种情况，只需要在最后将 s[ i ] 替换为 t[ j ]，使得满足 s[1..i] == t[1..j]，这样总共也需要 k+1 个操作。

特别注意：而如果在第3种情况下，s[i]刚好等于t[j]，那我们就可以仅仅使用k个操作就完成这个过程。

最后，为了保证得到的操作次数总是最少的，我们可以从上面三种情况中选择消耗最少的一种最为将s[1..i]转换为t[1..j]所需要的最小操作次数。我们把储存k的二维数组命名为 D[ ][ ] ，显而易见，当我们获得 D[i-1][j]，D[i][j-1] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。

如果两个子串的最后一个字母相同，即word1[i] = word2[i] 的情况下：

如果两个子串的最后一个字母不相同，即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：

•思路可视化

在上面的思路描述下，我们大致能够理解了，当然，如果还是有点迷糊的，这里我将思路用表格一步一步的表示出来，帮助理解。首先我们先初始化一个二维数组，如下。“.” 代表空串。第一行和第一列按照个数进行初始化，这一步要想明白，想明白了之后就好理解了。

如果两个子串的最后一个字母相同，即word1[i] = word2[i] 的情况下：

，图形如下。

如果两个子串的最后一个字母不相同，即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：

，图形如下。

最后我们会得到如下的结果，二维数组最后的 3 就是我们的答案。

•代码实现

public int minDistance(String word1, String word2){
    int n = word1.length();
    int m = word2.length();

    if(n * m == 0)
        return n + m;

    int[][] d = new int[n + 1][m + 1];
    for (int i = 0; i < n + 1; i++){
        d[i][0] = i;
    }

    for (int j = 0; j < m + 1; j++){
            d[0][j] = j;
    }

    for (int i = 1; i < n + 1; i++){
        for (int j = 1; j < m + 1; j++){
            int left = d[i - 1][j] + 1;
            int down = d[i][j - 1] + 1;
            int left_down = d[i - 1][j - 1];
            if (word1.charAt(i - 1) != word2.charAt(j - 1))
                left_down += 1;
            d[i][j] = Math.min(left, Math.min(down, left_down));
        }
    }
    return d[n][m];
}

编辑距离（Levenshtein Distance）算法详解和python代码

最近做NLP用到了编辑距离，网上学习了很多，看到很多博客写的有问题，这里做一个编辑距离的算法介绍，步骤和多种python代码实现，编辑距离有很多个定义，比如Levenshtein距离，LCS距离，汉明距离等，我们这里将Levenshtein距离默认为编辑距离。

基本概念：

编辑距离是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作仅包括删除、加入、取代字符串中的任何一个字符。
它是由俄罗斯科学家Vladimir Levenshtein在1965年提出，中文名叫做莱文斯坦距离。
例如将 jary 转为 jerry；

1. jery (a→e)
2. jerry(add r)

主要思想

假设我们可以使用d[i, j]个步骤（可以使用一个二维数组保存这个值），表示将字符串 s[ : i ] 转换为字符串 t[ : j ] 所需要的最少编辑操作次数，那么，考虑一个特殊情况，即在 i = 0，即s为空时，那么对应的d[0, j] 就是增加 j 个字符，使得 s 转化为 t；反之，在 j = 0，即t为空时，对应的d[i, 0] 就是减少 i 个字符，使得s转化为t。
然后我们考虑一般情况，利用动态规划的思想，我们要想得到将 s[ : i ]经过最少次数的增加，删除，或者替换操作就转变为 t[ : j ]，那么我们就必须在最后一步操作之前可以以最少次数的增加，删除，或者替换操作，使得现在 s 和 t 只需要再做一次操作或者不做就可以完全相等。
根据动态规划和贝尔曼最优性原理，这里的"最后一步操作之前"指的是：

1. 在k个操作内将 s[ : i ] 转换为 t[ : j-1 ]
2. 在k个操作里面将 s[ : i-1 ] 转换为 t[ : j ]
3. 在k个步骤里面将 s[ : i-1 ] 转换为 t[ : j -1]

于是，与之对应的最后一步操作即为：

4. 最后将 t[j] 加上s[ : i ]就完成了匹配，这样总共就需要 k+1 个操作
5. 最后将 s[i] 移除，也完成了匹配，所以总共需要 k+1 个操作
6. 最后将 s[i] 替换为 t[j]，完成匹配，这样总共也需要 k+1个操作。而如果在第3种情况下，s[i ]刚好等于 t[j]，那我 们就仅仅使用了k个操作就完成这个过程。

所以现在问题变为：为了保证得到的操作总次数最少，我们需要从上面三种情况中选择消耗最少的一种。

基本步骤

1. 初始化行数为m+1 列数为 n+1 的矩阵 matrix, 用来保存完成某个转换需要执行的操作的次数，那么将 s[ 1 : n ] 变为t[ 1 : m ] 所需要执行的操作次数为matrix[n][m]的值；

2. 初始化matrix第一行为0到n，第一列为0到m。Matrix[0][j]表示第1行第j+1列的值，这个值表示将串s[1 : 0]=[]转换为 t[1 : j] 所需要执行的操作的次数，很显然将一个空串转换为一个长度为 j 的串，只需要 j 次的add操作，所以matrix[0][j]的值应该是 j，其他值以此类推。

3. 检查每个从1到n的 s[i] 字符；

4. 检查每个从1到m的 t[j] 字符；

5. 将串 s 和串 t 的每一个字符进行两两比较，如果相等，则让cost为0，如果不等，则让cost为1（这个cost后面会用到）;

6. a、如果我们可以在k个操作里面将s[1:i-1]转换为t[1:j]，也就是说matrix[i-1,j]=k， 那么我们就可以将s[i]移除，然后再做这k个操作，所以总共需要k+1个操作。
   b、如果我们可以在k个操作内将 s[1:i] 转换为 t[1:j-1] ，也就是说matrix[i,j-1]=k，那么我们就可以将 t[j] 加上s[1:i]，这样总共就需要k+1个操作。
   c、如果我们可以在k个步骤里面将 s[1:i-1] 转换为 t [1:j-1]，那么我们就可以将s[i]转换为 t[j]，使得满足s[1:i] == t[1:j]，这样总共也需要k+1个操作。（这里需要加上cost，是因为如果s[i]刚好等于t[j]，那么就不需要再做替换操作，即可满足，如果不等，则需要再做一次替换操作，那么就需要k+1次操作）
   因为我们要取得最小操作的个数，所以我们最后还需要将这三种情况的操作个数进行比较，取最小值作为matrix[ i , j ]的值；

7. 然后重复执行3,4,5,6，最后的结果就在matrix[m,n]中；

文字看的不清不楚没有关系，我们下面以图解解释下每一个步骤，还是以"jary" → "jerry"为例。

图解如下

步骤1：初始化矩阵如下：

步骤2：从源串"jary"的第一个字符"j"开始，自上而下与目标串"jerry"比较

如果两个字符相等，则cost = 0, 如果两个字符不相等，则cost = 1。
当前值从此位置的 左+1，上+1和 左上+cost 三个值中取最小值。
第一次，源串第一个字符“j” 与目标串的“j”对比,左+1，上+1，左上+cost三个值中取出最小的值0，因为两字符相等，所以加上0；接着，依次对比“j”→“e”，“j”→“r”，“j”→“r”，，“j”→“y” 到扫描完目标串。

步骤三：遍历整个源串与目标串每一个字符比较



步骤四：遍历完成，则matrix[m][n]即为所求编辑距离
求出编辑距离后，可以计算两个字符串的相似度Similarity = $1-\frac{Levenshtein}{\max (s,t)}$，其中s,t分别是源串和目标串的长度。

代码实现

1. 利用python的三方库Levenshtein，调用Levenshtein.distance(str1,str2)方法即可，这是内部调用c库，优化了算法结构的，比我们按照上面那个步骤写的代码快。
2. 利用Numpy，DP，wiki上的代码 python_code.
2.一个简单的代码，用python的list实现

#!/usr/bin/env python
# -*- coding: cp936 -*-
def edit_distance(str1, str2):
'''
        :type str1: str
        :type str2: str
        :rtype: int
'''
    matrix = [[i+j for j in xrange(len(str2) + 1)] for i in xrange(len(str1) + 1)]
    for i in xrange(1,len(str1)+1):
        for j in xrange(1,len(str2)+1):
            if str1[i-1] == str2[j-1]:
                d = 0
            else:
                d = 1
            matrix[i][j] = min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+d)
    return matrix[len(str1)][len(str2)]

参考文献

• 编辑距离算法详解：Levenshtein Distance算法.
• 编辑距离.

编辑距离的定义

编辑距离（Edit Distance）最常用的定义就是Levenstein距离，是由俄国科学家Vladimir Levenshtein于1965年提出的，所以编辑距离一般又称Levenshtein距离。它主要作用是测量两个字符串的差异化程度，表示字符串a至少要经过多少个操作才能转换为字符串b，这里的操作包括三种：增加、删除、替换。

举个例子：
(1)增加：对于字符串a：abc 和 字符串b:abcde，显然，只需要在字符串a的末尾增加字符’d’和’e’就能变成字符串b了，所以a和b的最短编辑距离为2。
(2)删除：对于字符串a:abcd 和字符串b:abc，显然，只需要在字符串a的末尾删除字符’d’就能变成字符串b了，所以a和b的最短编辑距离为1。
(3)替换：对于字符串a:abcd 和 字符串b:abce，显然，只需要把字符串a的’d’替换成’e’就可以了，此时二者的最短编辑距离是1。

一般字符串都是需要增加、删除、替换三者结合起来一起使用，因为字符串a到b可能存在多种变化的方法，而我们往往最关心的是最短的编辑距离，这样才能得出a和b的相似程度，最短编辑距离越小，表示a到b所需要的操作越少，a和b的相似度也就越高。因此，Levenstein距离的一个应用场景就是判断两个字符串的相似度，可以用在字符串的模糊搜索上面。

Levenshtein 算法原理

先从一个问题谈起：对于字符串"xyz"和"xcz"，它们的最短距离是多少？我们从两个字符串的最后一个字符开始比较，它们都是’z’，是相同的，我们可以不用做任何操作，此时二者的距离实际上等于"xy"和"xc"的距离，即d(xyz,xcz) = d(xy,xc)。也即是说，如果在比较的过程中，遇到了相同的字符，那么二者的距离是除了这个相同字符之外剩下字符的距离。即d(i，j) = d(i - 1,j-1)。

接着，我们把问题拓展一下，最后一个字符不相同的情况：字符串A(“xyzab”)和字符串B(“axyzc”)，问至少经过多少步操作可以把A变成B。

我们还是从两个字符串的最后一个字符来考察即’b’和’c’。显然二者不相同，那么我们有以下三种处理办法：
(1)增加：在A末尾增加一个’c’，那么A变成了"xyzabc"，B仍然是"axyzc"，由于此时末尾字符相同了，那么就变成了比较"xyzab"和"axyz"的距离，即d(xyzab,axyzc) = d(xyzab,axyz) + 1。可以写成d(i,j) = d(i,j - 1) + 1。表示下次比较的字符串B的长度减少了1，而加1表示当前进行了一次字符的操作。

(2)删除：删除A末尾的字符’b’，考察A剩下的部分与B的距离。即d(xyzab,axyzc) = d(xyza,axyzc) + 1。可以写成d(i,j) = d(i - 1,j) + 1。表示下次比较的字符串A的长度减少了1。

(3)替换：把A末尾的字符替换成’c’，这样就与B的末尾字符一样了，那么接下来就要考察出了末尾’c’部分的字符，即d(xyzab,axyzc) = d(xyza,axyz) + 1。写成d(i,j) = d(i -1,j-1) + 1表示字符串A和B的长度均减少了1。

由于我们要求的是最短的编辑距离，所以我们取以上三个步骤得出的距离的最小值为最短编辑距离。由上面的步骤可得，这是一个递归的过程，因为除掉最后一个字符之后，剩下的字符串的最后一位仍然是最后一个字符，我们仍然可以按照上面的三种操作来进行，经过这样的不断递归，直到比较到第一个字符为止，递归结束。

按照以上思路，我们很容易写出下面的方程：

注释：该方程的第一个条件min(i,j) = 0，表示若某一字符串为空，转换成另一个字符串所需的操作次数，显然，就是另一个字符串的长度(添加length个字符就能转换)。这个条件可以看成是递归的出口条件，此时i或j减到了0。

根据以上方程，我们能快速写出递归代码，但由于递归包含了大量的重复计算，并且如果初始字符串过长，会造成递归层次过深，容易造成栈溢出的问题，所以我们这里可以用***动态规划***来实现。**如果说递归是自顶向下的运算过程，那么动态规划就是自底向上的过程。**它从i和j的最小值开始，不断地增大i和j，同时对于一个i和j都会算出当前地最短距离，因为下一个i和j的距离会与当前的有关，所以通过一个数组来保存每一步的运算结果来避免重复的计算过程，当i和j增加到最大值length时，结果也就出来了，即d[length][length]为A、B的最短编辑距离。

动态规划中，i和j的增加需要两层循环来完成，外层循环遍历i，内层循环遍历j，也即是，对于每一行，会扫描行内的每一列的元素进行运算。因此，时间复杂度为o(n²)，空间复杂度为o(n²)。

图解动态规划求最短编辑距离过程

在写代码之前，为了让读者对动态规划有一个直观的感受，笔者以表格的形式，列出动态规划是如何一步步地工作的。
下面以字符串"xyzab"和"axyzc"为例来讲解。

由上面可以看出，动态规划就是逐行逐列地运算，逐渐填满整个数组，最后得到结果恰好保存在数组的最后一行和最后一列的元素上。

代码实现

一、基本实现

public class LevenshteinDistance {

    private static int minimum(int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }

    public static int computeLevenshteinDistance(CharSequence src,CharSequence dst){
        int[][] distance = new int[src.length() + 1][dst.length() + 1];

        for (int i = 0;i <= src.length();i++)
            distance[i][0] = i;
        for (int j = 0;j <= dst.length();j++)
            distance[0][j] = j;

        for (int i = 1;i <= src.length();i++){
            for (int j = 1;j <= dst.length();j++){
                int flag = (src.charAt(i - 1) == dst.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + flag);
            }
        }
        return distance[src.length()][dst.length()];
    }

    //测试方法
    public static void main(String args[]){
        String s1 = "xyzab";
        String s2 = "axyzc";

        String s3 = "等啊高原";
        String s4 = "阿登高原";

        String s5 = "xyz阿登高原";
        String s6 = "1y3等啊高原x";

        System.out.println("字符串(\"" + s1 + "\")和字符串(\"" + s2 + "\")的最小编辑距离为："+ computeLevenshteinDistance(s1,s2));
        System.out.println("字符串(\"" + s3 + "\")和字符串(\"" + s4 + "\")的最小编辑距离为："+ computeLevenshteinDistance(s3,s4));
        System.out.println("字符串(\"" + s5 + "\")和字符串(\"" + s6 + "\")的最小编辑距离为："+ computeLevenshteinDistance(s5,s6));

    }
}

上面的代码是利用了动态规划的思想来实现的最短编辑距离算法，它的实现与原理方程基本上是一致的，都是先对第一行和第一列的数据进行初始化，然后开始逐行逐列进行计算，填充满整个数组，即自底向上的思想，通过这样减少了大量的递归重复计算，实现了运算速度的提升。上面提到，这种实现的时间复杂度和空间复杂度都是n²级别的（实际上是m×n，两个字符串长度的乘积）。实际上，我们可以对代码进行优化，降低空间复杂度。

二、利用滚动数组进行空间复杂度的优化
滚动数组是动态规划中一种常见的优化思想。为了理解滚动数组的思想，我们先来看看如何进行空间复杂度的优化。回到原理方程，我们可以观察到d(i,j)只与上一行的元素d(i-1,j)、d(i,j-1)和d(i-1,j-1)有关，而上一行之前的元素没有关系，也就是说，对于某一行的d(i,j)，我们只需要知道上一行的数据就行，别的数据都是无效数据。实际上，我们只需要两行的数组就可以了。

举个例子：还是上面的"xyzab"和"axyzc"，当我们计算完第一行和第二行的数据后，到达第三行时，我们以第二行为上一行结果来计算，并把计算结果放到第一行内；到达第四行时，由于第三行的数据实际上保存在第一行，所以我们根据第一行来计算，把结果保存在第二行……以此类推，直到计算到最后一行，即不断交替使用两行数组的空间，“滚动数组”也因此得名。通过使用滚动数组的形式，我们不需要n×m的空间，只需要2×min(n,m)的空间，这样便能把空间复杂度降到线性范围内，节省了大量的空间。

利用滚动数组后的空间复杂度为o(2×n)或者o(2×m)，这取决于代码的实现，即取字符串A还是B的长度为数组的列数。(因为无论把哪一个字符串作为src或dst，都是等价的，结果都是一样的。)其实我们可以通过判断A、B的长度，来选取一个最小值作为列数，此时空间复杂度变为o(2×min(n,m))。下面给出基于滚动数组的最小编辑距离的优化版本，由Java实现。

/**
     *  利用滚动数组优化过的最小编辑距离算法。空间复杂度为O(2×min(lenSrc,lenDst))
     * @param src 动态规划数组的行元素
     * @param dst 动态规划数组的列元素
     * @return
     */
    public static int computeLevenshteinDistance_Optimized(CharSequence src,CharSequence dst){
        int lenSrc = src.length() + 1;
        int lenDst = dst.length() + 1;

        CharSequence newSrc = src;
        CharSequence newDst = dst;
        //如果src长度比dst的短，表示数组的列数更多，此时我们
        //交换二者的位置，使得数组的列数变为较小的值。
        if (lenSrc < lenDst){
            newSrc = dst;
            newDst = src;
            int temp = lenDst;
            lenDst = lenSrc;
            lenSrc = temp;
        }

        //创建滚动数组，此时列数为lenDst，是最小的
        int[] cost = new int[lenDst];   //当前行依赖的上一行数据
        int[] newCost = new int[lenDst];//当前行正在修改的数据

        //对第一行进行初始化
        for(int i = 0;i < lenDst;i++)
            cost[i] = i;

        for(int i = 1;i < lenSrc;i++){
            //对第一列进行初始化
            newCost[0] = i;

            for(int j = 1;j < lenDst;j++){
                int flag = (newDst.charAt(j - 1) == newSrc.charAt(i - 1)) ? 0 : 1;

                int cost_insert = cost[j] + 1;        //表示“上面”的数据，即对应d(i - 1,j)
                int cost_replace = cost[j - 1] + flag;//表示“左上方的数据”，即对应d(i - 1,j - 1)
                int cost_delete = newCost[j - 1] + 1; //表示“左边的数据”，对应d(i,j - 1)

                newCost[j] = minimum(cost_insert,cost_replace,cost_delete); //对应d(i,j)
            }

            //把当前行的数据交换到上一行内
            int[] temp = cost;
            cost = newCost;
            newCost = temp;
        }

        return cost[lenDst - 1];
    }

把main()方法的方法调用改为上述方法，比较前后两个方法的输出结果，结果一致，符合预期。

三、对空间复杂度的进一步优化
实际上，我们还能对这个进行进一步的优化，把空间复杂度减少为o(min(n,m))，即我们只需要一行的数组d加一个额外的临时变量就可以实现。比如说我们要修改d[i]的值时，只需知道它的左边、上边和左上方的元素的值，而左边的值就是d[i-1]，上边的值是修改之前的d[i]，左上方的值是d[i-1]修改之前的值。每一次需要修改d[i-1]的时候，都用临时变量把他保存起来，这样i位置就能直接获取这三个值进行比较，得到结果之后，先用这个临时变量把d[i]保存起来，然后再写入d[i]内，……以此类推，直到遍历完一行。

其核心思想是：把求得的数据，再次写回这一行数据对应下标元素的位置，而临时变量temp则保存当前位置左上方元素的值，以提供给下一个位置的计算。总的来说，数据的操作只集中在一行之内，所以空间复杂度就是o(n)。

下面以图解的形式表达这一过程，方便读者理解。

代码实现也不复杂，有兴趣的同学可以根据上图或者思路来实现，这里就不再实现了。

好了，这篇文章写到这里就结束了，希望能对各位同学有所裨益，谢谢你们的耐心阅读~