Dayi Lin, Ph.D.

Data Scientist | Software Engineering Researcher

Tag: 动态规划

最小编辑距离 算法原理

问题 最小编辑距离 Minimum Edit Distance关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。例如 s1 = “12433” 和 s2 = “1233”;则可以通过在s2中间插入4得到12433与s1一致。即 d(s1,s2) = 1 (进行了一次插入操作) 性质 计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“c1″,”c2”) = c1 == c2 ? 0 : 1; 2. d(s1+c1,s2+c2) = min( d(s1,s2)+ c1==c2 ? 0 : 1 , 1 + d(s1+c1,s2), 1 + d(s1,s2+c2) ); 第一个性质是显然的。第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法,于是对c1,c2可能的操作只有: 1.