关于编辑距离

Published on 2019 Apr 02 14:31:15
Last Updated on 2019 Apr 02 15:34:56

编辑距离问题:

给定两个字符串\(a\)和\(b\),计算经过\(a\)以下操作最少几次会变得和\(b\)相同:

  1. 替换\(a\)中的一个字符
  2. 删去\(a\)中的一个字符
  3. 在\(a\)中的某个位置插入一个字符

例:

a=”114” b=”514” – distance=1 (将第一个1替换为5)

a=”1919” b=”810” – distance=3

a=”abcdmape” b=”acemap” – distance=3

解法:

采用动态规划。
使用\(d_{i,j}\)来代表“字符串\(a\)的前\(i\)位与\(b\)的前\(j\)位的编辑距离”。
初始状态是\(d_{0,0}=0, d_{0,i}=d_{i,0}=i\),要求的值就是\(d_{len(a),len(b)}\)。
假设已经计算好\(i\leq m-1\)和\(i=m,j\leq n-1\)时所有的\(d_{i,j}\),现在我们来计算\(d_{m,n}\)。
对于\(a_m\)和\(b_n\)位置的字符,有三种情况:

  1. \(a_m\)与\(b_n\)匹配(相同或不相同)。
  2. \(a\)中\(a_m\)被删除。
  3. \(a\)中\(a_m\)后添加了\(b_n\)

(1)对应\(a_{1..m-1}\)与\(b_{1..n-1}\)计算编辑距离后,\(a_m\)与\(b_n\)比较。如果\(a_m=b_n\)那么(1)对应的编辑距离就是\(d_{m-1,n-1}\);\(a_m\neq b_n\)那么(1)对应的编辑距离则是\(d_{m-1,n-1}+1\)。
(2)对应\(a_{1..m-1}\)与\(b_{1..n}\)计算编辑距离后删除\(a_m\)。(2)对应的编辑距离就是\(d_{m-1,n}+1\)。
(3)对应\(a_{1..m}\)与\(b_{1..n-1}\)计算编辑距离后添加\(b_n\)。(3)对应的编辑距离就是\(d_{m,n-1}+1\)。
最终的\(d_{i,j}\)应该是这三种情况取最小值,因为距离越小越好。
那么最终就是:

$$
d_{m,n}=\begin{cases}
min\{d_{m-1,n-1},d_{m-1,n}+1,d_{m,n-1}+1\} &a_m=b_n\\
min\{d_{m-1,n-1}+1,d_{m-1,n}+1,d_{m,n-1}+1\} &a_m\neq b_n
\end{cases}
$$

那么只需要从小到大枚举\(i\),对于每个\(i\)从小到大枚举\(j\),计算\(d_{i,j}\)就可以了。
就完事了。
/cy

代码见ppt(((