数据结构与算法 / 系统课时

用编辑距离建模字符操作

用编辑距离建模字符操作

编辑距离要计算把一个字符串变成另一个字符串所需的最少单字符操作数。难点不在三种操作本身,而在于看清插入、删除、替换分别让两个前缀下标怎样变化,从而把选择统一写进一个二维状态。

学习目标

  • 用字符串前缀定义编辑距离的二维状态
  • 推导插入、删除、替换对应的三个前驱状态
  • 正确初始化空字符串边界并实现最小编辑距离

把转换任务限制到两个前缀

设源字符串为 source,目标字符串为 target。定义 dp[i][j] 为把 source 的前 i 个字符转换成 target 的前 j 个字符所需的最少操作数,最终答案是 dp[m][n]。

边界状态直接来自操作含义:空字符串变成目标前 j 个字符必须插入 j 次,所以 dp[0][j] = j;源前 i 个字符变成空字符串必须删除 i 次,所以 dp[i][0] = i。这也是为什么第 0 行和第 0 列不能全部初始化为 0。

从最后一次操作倒推来源

当 source[i - 1] == target[j - 1] 时,末尾字符已经一致,不需要新操作,直接继承 dp[i - 1][j - 1]。

当两个末尾字符不同时,可以把最优方案的最后一步分类为三种情况:

  • 删除源字符串末尾字符:从 dp[i - 1][j] 来,再加 1
  • 向源字符串末尾插入目标字符:从 dp[i][j - 1] 来,再加 1
  • 把源字符串末尾替换成目标字符:从 dp[i - 1][j - 1] 来,再加 1

因此当前状态取这三个候选值的最小值。这里的“插入”之所以只减少目标下标,是因为倒推最后一步时,插入前已经把当前源前缀转换成了少一个字符的目标前缀。

编辑距离三类操作与二维状态来源

用操作序列理解最优值

以 "horse" 转换为 "ros" 为例,一条最优路径可以是:先把 h 替换为 r 得到 "rorse",再删除多余的第二个 r 得到 "rose",最后删除 e 得到 "ros",共 3 步。

动态规划不会预先猜这条路径,而是在每个前缀状态同时比较三种最后操作。某个局部选择暂时看起来更短,也不会阻止后续状态改用另一条来源,这正是二维表能得到全局最优值的原因。

实现最小编辑距离

下面的程序按照边界、字符相等、字符不等三种情况填表:

python
def edit_distance(source: str, target: str) -> int:
    m, n = len(source), len(target)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 空字符串与非空前缀之间只能连续插入或连续删除。
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if source[i - 1] == target[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                delete = dp[i - 1][j]
                insert = dp[i][j - 1]
                replace = dp[i - 1][j - 1]
                dp[i][j] = 1 + min(delete, insert, replace)

    return dp[m][n]


if __name__ == "__main__":
    print(edit_distance("horse", "ros"))

预期输出

text
3

状态总数为 (m + 1) × (n + 1),每个状态比较至多三个候选值,所以时间复杂度为 O(mn),空间复杂度为 O(mn)。只求距离时可压缩到两行甚至一行;若还要恢复具体编辑步骤,则需要保留完整状态表或额外记录每个状态的来源。

编辑距离的通用建模方法是先固定“前缀到前缀”的含义,再从最后一次操作反推下标变化。只要三种操作与三个前驱状态一一对应,边界初始化和最小值转移就不容易混淆。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用编辑距离建模字符操作

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通