编辑距离：把一个词改成另一个最少几步
「近似匹配」首先需要定义距离。最常用的是 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 删除
; ← dp[i][j-1] + 1 插入
)。
试试： 距离 3（k→s 替换、e→i 替换、末尾插 g）。把 a、b 改成形近词看路径怎么变。绿色格子是回溯出的最优路径，下面是对应的编辑操作。「BK-tree」用这个距离加三角不等式组织词典，做容错查询。