Refrence : Dynamic Programming Algorithm (DPA) for Edit-Distance 编辑距离 关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。 所谓的编辑距离: 让s1和s2变成相同字符串需要下面操作的最小次数。 1. 把某个字符ch1变成ch2 2. 删除某个字符 3. 插入某个字符 例如 s1 = “12433” 和s2=”1233”; 则可以通过在s2中间插入4得到12433与s1一致。 即 d(s1,s2) = 1 (进行了一次插入操作) 编辑距离的性质 计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质: 1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1; 2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 , d(s1+ch1,s2), d(s1,s2+ch2) );
本文关键：edit distance 编辑距离
本站最佳浏览方式为 分辨率 1024x768 IE 6.0（或更高版本的 IE浏览器） 
|