最小编辑距离

2020-04-22 本文已影响0人热爱生活的大川

假设只有三种编辑方式：插入，删除，替换。每种编辑方式对应一次操作。按规定的编辑方式，将原始字符串变换到目标字符串所需的最少操作次数，被称为最小编辑距离。
Levenshtein距离中定义替换对应两次操作。

设源字符串为A，长度m，目标字符串为B，长度n。

是否存在简单情况
很明显，两字符串长度较短时情况会比较简单。
如，m=0时，插入n次；n=0时，删除n次；m=n=1且A和B不同时，替换1次。
简单情况到复杂情况的变量是什么
是两个字符串的长度。因此我们设最小编辑距离为 $D(m,n)$ 。
是否存在简单情况到复杂情况的递推关系
由1有 $\begin{cases}D(i,0)=i,i \in (0,m) \\ D(0,j)=j,j \in (0,n) \end{cases}$
从 $D(i,j)$ 向前回溯，有三条路径，对应三种编辑方式，
$D(i,j) = min \begin{cases} D(i,j-1)+ins(B[j]) \\ D(i-1,j)+del(A[i]) \\ D(i-1,j-1)+sub(A[i],B[j]) \end{cases}$ 这里， $ins(x)=1$ ， $del(x)=1$ ， $sub(x,y) = \begin{cases} 1,x \neq y \\ 0,x = y \end{cases}$ 。