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