理解编辑距离

朴灿烈づ我的快乐病毒、 2022-12-17 13:56 178阅读 0赞

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

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

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

## 解法 ##

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

### 暴力法 ###

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

代码：

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')`，下图是函数调用次数排行榜：  
![函数调用次数排行][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwOTkwODA_size_16_color_FFFFFF_t_70_pic_center]

可以看到，排第一的 `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 时的不同方法耗时（单位为秒）。结果看下图：  
![暴力法VS动态规划法][VS]

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

y = 2.21990087 × 1 0 − 7 e 1.70878196 x − 1.40410625 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 ##

[LCS]: https://alanlee.fun/2020/04/07/understanding-lcs/
[Jaro]: https://en.wikipedia.org/wiki/Jaro_distance
[Link 1]: https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwOTkwODA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/d4dc50359944427693db5fd1906731e4.png
[VS]: /images/20221122/0b8d581727e6400199f508804b20deb6.png
[Minimum Edit Distance]: https://web.stanford.edu/class/cs124/lec/med.pdf
[Edit distance]: https://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html
[Similarity Search - The String Edit Distance - Nikolaus Augsten]: https://dbresearch.uni-salzburg.at/teaching/2016ws/ssdb/ssdb_02-handout-1x1.pdf
[-]: https://zh.wikipedia.org/wiki/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2