最小编辑距离

1.定义

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

2.推导

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

  1. 是否存在简单情况
    很明显，两字符串长度较短时情况会比较简单。
    如，m=0时，插入n次；n=0时，删除n次；m=n=1且A和B不同时，替换1次。

  2. 简单情况到复杂情况的变量是什么
    是两个字符串的长度。因此我们设最小编辑距离为D(m,n)。

  3. 是否存在简单情况到复杂情况的递推关系
    由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}。

  • 每一步取最短路径，最后一定是最短路径吗？对于每次都归结于一点的树形结构，这是必然的。
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容