理解编辑距离

顾名思义，编辑距离（Edit distance）是一种距离，用于衡量两个字符串之间的远近程度，方式是一个字符串至少需要多少次基础变换才能变成另一个字符串，可应用在拼写检查、判断 DNA 相似度等场景中。根据可操作的基础变换不同，可分为以下几种：

• 莱文斯坦距离（Levenshtein distance）：最常见的编辑距离，基础变换包括插入、删除和替换。但是需要注意一点的是，当每种变换发生时，产生的距离（或者称为代价）并不一定是 1，例如斯坦福大学关于最小编辑距离的课件中，一次替换产生的距离就可能是 2。
• 最长公共子序列（LCS）距离：基础变换包括插入和删除。
• Jaro 距离：基础变换只包括转置，即交换两个字符的位置，AB -> BA。
• 汉明距离：基础变换只包括替换，所以只能应用于两个字符串长度相等的情况。

本文只讨论最常见的第一种形式，莱文斯坦距离。

解法

解法有两种：暴力法和动态规划法。

暴力法

暴力法思想很直接，采用递归思想，直接取所需插入、删除和替换操作的最小值。

代码：

def brute_force(s1, s2):
    m = len(s1)
    n = len(s2)
    if m == 0:
        return n
    if n == 0:
        return m
    if s1[m - 1] == s2[n - 1]:
        c = 0
    else:
        c = 1  # 一次替换产生的距离，也可以定义成 2
    return min(
        brute_force(s1, s2[: n - 1]) + 1,  # 插入
        brute_force(s1[: m - 1], s2) + 1,  # 删除
        brute_force(s1[: m - 1], s2[: n - 1]) + c,  # 替换
    )

缺点就是耗时很大，这是由于存在大量的重复计算。有多大量？我举一个例子，brute_force('geek', 'gesek')，下图是函数调用次数排行榜：

可以看到，排第一的 brute_force('', 'g') 被调用了 192 次，brute_force() 总计被调用了 1021 次，这还仅仅是对两个长度分别为 4、5 的字符串进行的比较，其耗时程度可见一斑。

动态规划法

动态规划法是对暴力法的改进，把所有的重复计算都干掉，空间换时间，将计算过的值存储到一个矩阵中，后面用的时候就直接取。

代码：

def levenshtein_distance_dp(s1, s2):
    m = len(s1) + 1
    n = len(s2) + 1
    dp_table = np.zeros((m, n))
    # 初始化
    for i in range(m):
        dp_table[i, 0] = i
    for i in range(n):
        dp_table[0, i] = i

    for i in range(1, m):
        for j in range(1, n):
            dp_table[i, j] = min(
                dp_table[i - 1, j] + 1,
                dp_table[i, j - 1] + 1,
                dp_table[i - 1, j - 1] + (1 if s1[i - 1] != s2[j - 1] else 0),
            )
    return int(dp_table[m - 2, n - 2])

初始化为什么是那样呢？想象一下，假设我们想计算 geek 和 gesek 之间的距离，即从 geek 到 gesek 至少需要多少步，记着这一点。和其他动态规划问题一样，首先会有一个 DP 表：

从第一个单元开始，先看第一列，"" -> "" 所需步骤为 0（因为相等），所以第一个填 0。

第二行第一列，"" -> g，需要插入一个字符 g，因此所需步骤为 1：

第三行第一列，"" -> ge，需要插入两个字符 ge，因此需要两个步骤：

以此类推，得到第一列：

对于第一行，同样的道理，只不过是删除操作，例如 ge -> "" 需要删除两个字符，即两步删除操作。

这就完成了初始化过程。从过程中我们可以看出，其实对于一个单元格 T [ i , j ] T[i,j] T[i,j] 来说，其左上角 T [ i − 1 , j − 1 ] T[i-1, j-1] T[i−1,j−1] 是最小替换步数，正上方 T [ i − 1 , j ] T[i-1, j] T[i−1,j] 是最小删除步数，左边 T [ i , j − 1 ] T[i, j-1] T[i,j−1] 是最小插入步数，然后我们只需根据条件取最小即可，表格剩余部分就是这么推出来的。

至于这个改进有多猛？我做了个实验：假设 s1 和 s2 长度相等，依次测试长度为 1-15 时的不同方法耗时（单位为秒）。结果看下图：

可以看到暴力法是指数级增长，当字符串长度为 15 时，暴力法耗时已经达到 30000 秒，约为 8.3 小时，动态规划法仅耗时万分之六秒。而当长度翻倍变为 30 时，暴力法预计至少需要 1.27 亿年才能算万，具体秒数可以点开图右上角灰色的ex 来查看暴力法耗时的模拟曲线。该曲线并不是y=ex 的曲线，具体公式如下：

y = 2.21990087\times10^{-7} e^{1.70878196x} - 1.40410625 y=2.21990087×10−7e1.70878196x−1.40410625

还有

一些没说到的：

• 有时候只求出编辑距离可能还不够，还需要回溯，对两个字符串进行对齐。
• Weighted Edit Distance，即加权编辑距离，这其实是在初始化和后续计算时加入了一些权重作为先验，一步操作产生的距离不再是 1 或者 2。
• 其他变种……

这些等有时间再说吧。

Reference

• Minimum Edit Distance
• Edit distance
• Similarity Search - The String Edit Distance - Nikolaus Augsten
• 编辑距离 - 维基百科，自由的百科全书

END