1、問題

例如兩個(gè)字符串 FAMILY 和 FRAME ,有兩種

對齊方式:

1)、

F_A MIL Y

FRAME

2）、

_FAMILY

FRAME

第 1 種對齊需要付出的代價(jià): 4 ,插入 R ,將 I 替換為 E ,刪除 L 、 Y 。
第 2 種對齊需要付出的代價(jià): 5 ,插入 F，將 F 替換為 R ,將 I 替換為 E ,刪除 L 、 Y 。
編輯距離是指將一個(gè)字符串變換為另一個(gè)字符串所需要的最小編輯操作。

怎么找到兩個(gè)字符串 x [1 ,...,m ] 和 y [1 ,...,n ] 的編輯距離

 

 

 

 

 

2、分析

假設(shè)已經(jīng)知道 d [ i ][ j ] 是 X i ={ x 1 ,x 2 ,x 3 ,...,x i } 和 Y j ={ y 1 ,y 2 ,y 3 ,...,y j } 的編輯距離，分3種情況

1）

x1,  x2,  x3,  x4, x(i - 1),  x(i)

y1,  y2,  y3, y4, y(j - 1),  _

推出

d [ i ][ j ]= d [ i ?1][ j ]+1

2）

 

x1,  x2,  x3,  x4, x(i - 1),  x(i)

y1,  y2,  y3, y4, y(j - 1),  _

推出

d [ i ][ j ]= d [ i ][ j ?1]+1

 

3）

 

x1,  x2,  x3,  x4, x(i - 1),  x(i)

y1,  y2,  y3, y4, y(j -

總結(jié)

以上是生活随笔為你收集整理的动态规划之编辑距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。