编辑距离 · Levenshtein DP

编辑距离：把一个词改成另一个最少几步

「近似匹配」首先需要定义距离。最常用的是 Levenshtein 编辑距离：把字符串 a 改成 b，插入 / 删除 / 替换各算一步，所需的最少步数。它用一张动态规划表算出来——dp[i][j] = 把 a 的前 i 个字符变成 b 的前 j 个字符的最少步数。本页单步填表、回溯出具体的编辑操作；「BK-tree」正是以它为距离来组织词典的。

递推只看三个邻居：dp[i][j] = min( ↖ dp[i-1][j-1] + (a[i-1]==b[j-1] ? 0 : 1) 相同则不计、不同则替换；↑ dp[i-1][j] + 1 删除 $a[i-1]$ ; ← dp[i][j-1] + 1 插入 $b[j-1]$ )。

图 0-1 · 编辑距离 DP 表的逐格填充与回溯出的编辑脚本。可改两个串观察表与路径的变化。

kitten 到 sitting 的距离是 3：首字母换成 s、第四个字母换成 i、末尾插一个 g。图 0-1 里绿色格子是回溯出的最优路径，下方列出对应的编辑操作。「BK-tree」用这个距离加三角不等式组织词典，做容错查询。