計算字元串的相似度（編輯距離）

問題

許多程式會大量使用字元串。對于不同的字元串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個不相同的字元串變得相同，具體的操作方法為：

1.修改一個字元（如把“a”替換為“b”）。

2.增加一個字元（如把“abdd”變為“aebdd”）。

3.删除一個字元（如把“travelling”變為“traveling”）。

比如，對于“abcdefg”和“abcdef”兩個字元串來說，我們認為可以通過增加/減少一個“g“的方式來達到目的。上面的兩種方案，都僅需要一次操作。把這個操作所需要的次數定義為兩個字元串的距離，給定任意兩個字元串，你是否能寫出一個算法來計算出它們的距離？

分析與解法

不難看出，兩個字元串的距離肯定不超過它們的長度之和（我們可以通過删除操作把兩個串都轉化為空串）。雖然這個結論對結果沒有幫助，但至少可以知道，任意兩個字元串的距離都是有限的。

我們還是應該集中考慮如何才能把這個問題轉化成規模較小的同樣的問題。如果有兩個串a=xabcdae和b=xfdfa，它們的第一個字元是相同的，隻要計算a[2,…,7]=abcdae和b[2,…,5]=fdfa的距離就可以了。但是如果兩個串的第一個字元不相同，那麼可以進行如下的操作（lena和lenb分别是a串和b串的長度）：

1．删除a串的第一個字元，然後計算a[2,…,lena]和b[1,…,lenb]的距離。

2．删除b串的第一個字元，然後計算a[1,…,lena]和b[2,…,lenb]的距離。

3．修改a串的第一個字元為b串的第一個字元，然後計算a[2,…,lena]和b[2,…,lenb]的距離。

4．修改b串的第一個字元為a串的第一個字元，然後計算a[2,…,lena]和b[2,…,lenb]的距離。

5．增加b串的第一個字元到a串的第一個字元之前，然後計算a[1,…,lena]和b[2,…,lenb]的距離。

6．增加a串的第一個字元到b串的第一個字元之前，然後計算a[2,…,lena]和b[1,…,lenb]的距離。

在這個題目中，我們并不在乎兩個字元串變得相等之後的字元串是怎樣的。是以，可以将上面6個操作合并為：

1.一步操作之後，再将a[2,…,lena]和b[1,…,lenb]變成相同字元串。

2.一步操作之後，再将a[1,…,lena]和b[2,…,lenb]變成相同字元串。

3.一步操作之後，再将a[2,…,lena]和b[2,…,lenb]變成相同字元串。

這樣，很快就可以完成一個遞歸程式。

代碼實作：

以上解法來自《程式設計之美》，有什麼地方需要改進的呢？問題在于：在遞歸的過程中，有些資料被重複計算了。

很經典的可使用動态規劃方法解決的題目，和計算兩字元串的最長公共子序列相似。

設ai為字元串a(a1a2a3 … am)的前i個字元（即為a1,a2,a3 … ai）

設bj為字元串b(b1b2b3 … bn)的前j個字元（即為b1,b2,b3 … bj）

設 l(i,j)為使兩個字元串和ai和bj相等的最小操作次數。

當ai==bj時 顯然 l(i,j) = l(i-1,j-1)

當ai!=bj時 

　　若将它們修改為相等，則對兩個字元串至少還要操作l(i-1,j-1)次

 　 若删除ai或在bj後添加ai，則對兩個字元串至少還要操作l(i-1,j)次

 　 若删除bj或在ai後添加bj，則對兩個字元串至少還要操作l(i,j-1)次

 　 此時l(i,j) = min( l(i-1,j-1), l(i-1,j), l(i,j-1) ) + 1 

顯然，l(i,0)=i，l(0,j)=j, 再利用上述的遞推公式，可以直接計算出l(i,j)值。

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。

http://www.cnblogs.com/luxiaoxun/archive/2012/08/05/2623894.html