問題

最小編輯距離 Minimum Edit Distance

關(guān)于兩個(gè)字符串s1,s2的差別，可以通過計(jì)算他們的最小編輯距離來決定。
設(shè)A、B為兩個(gè)字符串，狹義的編輯距離定義為把A轉(zhuǎn)換成B需要的最少刪除（刪除A中一個(gè)字符）、插入（在A中插入一個(gè)字符）和替換（把A中的某個(gè)字符替換成另一個(gè)字符）的次數(shù)，用ED（A，B）來表示。直觀來說，兩個(gè)串互相轉(zhuǎn)換需要經(jīng)過的步驟越多，差異越大。

例如 s1 = "12433" 和 s2 = "1233";
則可以通過在s2中間插入4得到12433與s1一致。
即 d(s1,s2) = 1 (進(jìn)行了一次插入操作)

性質(zhì)

計(jì)算兩個(gè)字符串s1+c1, s2+c2的編輯距離有這樣的性質(zhì):

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 ,d(s1+c1,s2),d(s1,s2+c2) );

第一個(gè)性質(zhì)是顯然的。
第二個(gè)性質(zhì): 由于我們定義的三個(gè)操作來作為編輯距離的一種衡量方法，于是對(duì)c1,c2可能的操作只有：

1. 把c1變成c2 2. s1+c1后刪除c1 d = (1 + d(s1, s2 + c2)) 3. s1+c1后插入c2 d = (1 + d(s1 + c1, s2))對(duì)于2和3的操作可以等價(jià)于: _2. s2+c2后添加c1 d = (1 + d(s1, s2 + c2)) _3. s2+c2后刪除c2 d = (1 + d(s1 + c1, s2))

因此可以得到計(jì)算編輯距離的性質(zhì)2。

復(fù)雜度分析

從上面性質(zhì)2可以看出計(jì)算過程呈現(xiàn)這樣的一種結(jié)構(gòu)(假設(shè)各個(gè)層用當(dāng)前計(jì)算的串長(zhǎng)度標(biāo)記，并假設(shè)兩個(gè)串長(zhǎng)度都為 n )
可以看到，該問題的復(fù)雜度為指數(shù)級(jí)別 3 的 n 次方，對(duì)于較長(zhǎng)的串，時(shí)間上是無法讓人忍受的。

分析: 在上面的結(jié)構(gòu)中，我們發(fā)現(xiàn)多次出現(xiàn)了 (n-1,n-1), (n-1,n-2)……。換句話說該結(jié)構(gòu)具有重疊子問題。再加上前面性質(zhì)2所具有的最優(yōu)子結(jié)構(gòu)。符合動(dòng)態(tài)規(guī)劃算法基本要素。因此可以使用動(dòng)態(tài)規(guī)劃算法把復(fù)雜度降低到多項(xiàng)式級(jí)別。

動(dòng)態(tài)規(guī)劃求解

首先為了避免重復(fù)計(jì)算子問題，添加兩個(gè)輔助數(shù)組。

一. 保存子問題結(jié)果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 與 s2(0->j) 的編輯距離

二. 保存字符之間的編輯距離.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s1[i] = s2[j] ? 0 : 1

三. 新的計(jì)算表達(dá)式
根據(jù)性質(zhì)1得到

M[ 0,0] = 0; M[ s1i, 0 ] = |s1i|; M[ 0, s2j ] = |s2j|;

根據(jù)性質(zhì)2得到

M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,m[i, j-1] + 1 ,m[i-1, j] + 1 );

復(fù)雜度
從新的計(jì)算式看出，計(jì)算過程為

i=1 -> |s1|j=1 -> |s2|M[i][j] = ……

因此復(fù)雜度為 O( |s1| * |s2| ) ，如果假設(shè)他們的長(zhǎng)度都為n，則復(fù)雜度為 O(n^2)

改進(jìn)

當(dāng)s[i]和s[j]相等時(shí)，代價(jià)為0，必然為最小值，所以首先判斷兩字符是否相等，若相等則直接判定M[i][j]=M[i-1][j-1]，判斷下個(gè)。這樣可以省很多計(jì)算。

工具宏：直接用一個(gè)宏來完成“求取三者最小值”的功能。不同于遞歸，宏定義消耗很小，完全可以放心使用。

1: #ifndef _MIN(xyz) 2: #define _MIN(xyz) ((x<y)?((x<z)?x:z):((y<z)?y:z)) 3: #endif // _MIN(xyz)

轉(zhuǎn)載于:https://www.cnblogs.com/sk-blogs/articles/3681693.html

總結(jié)

以上是生活随笔為你收集整理的【转】最小编辑距离 算法原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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