一直不理解，為什么要計(jì)算兩個(gè)字符串的相似度呢。什么叫做兩個(gè)字符串的相似度。經(jīng)常看別人的博客，碰到比較牛的人，然后就翻了翻，終于找到了比較全面的答案和為什么要計(jì)算字符串相似度的解釋。因?yàn)樗阉饕嬉淹ㄟ^爬蟲抓取的頁面給記錄下來，那么除了通過記錄url是否被訪問過之外，還可以這樣，比較兩個(gè)頁面的相似度，因?yàn)椴煌膗rl中可能記錄著相同的內(nèi)容，這樣，就不必再次記錄到搜索引擎的存儲空間中去了。還有，大家畢業(yè)的時(shí)候都寫過論文吧，我們論文的查重系統(tǒng)相信也會采用計(jì)算兩個(gè)字符串相似度這個(gè)概念。
以下敘述摘自編程之美一書：
許多程序會大量使用字符串。對于不同的字符串，我們希望能夠有辦法判斷其相似程序。我們定義一套操作方法來把兩個(gè)不相同的字符串變得相同，具體的操作方法為：
1.修改一個(gè)字符（如把“a”替換為“b”）;　　
2.增加一個(gè)字符（如把“abdd”變?yōu)椤癮ebdd”）;
3.刪除一個(gè)字符（如把“travelling”變?yōu)椤皌raveling”）;
比如，對于“abcdefg”和“abcdef”兩個(gè)字符串來說，我們認(rèn)為可以通過增加/減少一個(gè)“g”的方式來達(dá)到目的。上面的兩種方案，都僅需要一 次 。把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離，而相似度等于“距離+1”的倒數(shù)。也就是說，“abcdefg”和“abcdef”的距離為1，相似度 為1/2=0.5。
給定任意兩個(gè)字符串，你是否能寫出一個(gè)算法來計(jì)算它們的相似度呢？
原文的分析與解法
不難看出，兩個(gè)字符串的距離肯定不超過它們的長度之和（我們可以通過刪除操作把兩個(gè)串都轉(zhuǎn)化為空串）。雖然這個(gè)結(jié)論對結(jié)果沒有幫助，但至少可以知道，任意兩個(gè)字符串的距離都是有限的。我們還是就住集中考慮如何才能把這個(gè)問題轉(zhuǎn)化成規(guī)模較小的同樣的子問題。如果有兩個(gè)串A=xabcdae和B=xfdfa，它們的第一個(gè)字符是 相同的，只要計(jì)算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距離就可以了。但是如果兩個(gè)串的第一個(gè)字符不相同，那么可以進(jìn)行 如下的操作（lenA和lenB分別是A串和B串的長度）。
1.刪除A串的第一個(gè)字符，然后計(jì)算A[2,...,lenA]和B[1,...,lenB]的距離。
2.刪除B串的第一個(gè)字符，然后計(jì)算A[1,...,lenA]和B[2,...,lenB]的距離。
3.修改A串的第一個(gè)字符為B串的第一個(gè)字符，然后計(jì)算A[2,...,lenA]和B[2,...,lenB]的距離。
4.修改B串的第一個(gè)字符為A串的第一個(gè)字符，然后計(jì)算A[2,...,lenA]和B[2,...,lenB]的距離。
5.增加B串的第一個(gè)字符到A串的第一個(gè)字符之前，然后計(jì)算A[1,...,lenA]和B[2,...,lenB]的距離。
6.增加A串的第一個(gè)字符到B串的第一個(gè)字符之前，然后計(jì)算A[2,...,lenA]和B[1,...,lenB]的距離。
在這個(gè)題目中，我們并不在乎兩個(gè)字符串變得相等之后的字符串是怎樣的。所以，可以將上面的6個(gè)操作合并為：
1.一步操作之后，再將A[2,...,lenA]和B[1,...,lenB]變成相字符串。
2.一步操作之后，再將A[2,...,lenA]和B[2,...,lenB]變成相字符串。
3.一步操作之后，再將A[1,...,lenA]和B[2,...,lenB]變成相字符串。

通過以上1和6,2和5，3和4的結(jié)合操作，最后兩個(gè)字符串每個(gè)對應(yīng)的字符會相同，但是這三種操作產(chǎn)生的最終的兩個(gè)字符串是不一樣的。我們不知道通過上述的三種結(jié)合那種使用的操作次數(shù)是最少的。所以我們要比較操作次數(shù)來求得最小值。