similar_text 有哪些意想不到的驚喜(PHP)
PHP字串處理函式中有一個similar_text用於計算兩個字串的相似程度。今天來看看similar_text如何實現的。
similar_text — 計算兩個字串的相似度,返回兩個字串中匹配字元的數目
兩個字串的相似程度。注意該實現沒有使用 Oliver 虛擬碼中的堆疊,但是卻進行了遞迴呼叫,這個做法可能會導致整個過程變慢或變快。也請注意,該演算法的複雜度是 O(N**3),N 是最長字串的長度。
上面的文件說明還是很繞。
原始碼中similar_text函式在內部呼叫了php_similar_char進行處理。ac是引數的個數。函式返回的是兩個字串中匹配字元的數目。如果想要獲取相似的百分比,則需要傳遞一個引用引數獲取。
在php_similar_char中有呼叫了php_similar_str,在看php_similar_char前,先看看php_similar_str的功能。
php_similar_str內部跑了三個巢狀的迴圈,這就難怪文件中描述的,時間複雜度是O(N**3)。在最裡面的迴圈中,檢查兩個字串連續一致的個數。最裡層迴圈結束之後,判斷是否大於已經獲取到的最大相似數目。並記錄最大相似情況下兩個字串相似處開始的位置。
在php_similar_char,通過php_similar_str拿到最大相似數目,以及兩個字串起始位置。在底下,則把text1,text2分為最大相似字串前的字元,最大相似字串,最大相似字串後面字串三個部分,分別在遞迴呼叫計算兩個字串中相似字串前後兩個部分對應的相似長度。直到字串長度為0.
看到這,similar_text只能大概計算相似程度。其中有幾個小問題。
1、兩個空字串的相似度是0。
2、假設兩個字串'abcdefg','qabdefgabc',直觀上這兩個字串中“匹配字元”的數目有a,b,c,d,e,f,g 但是當你執行similar_text拿到的結果確是6。
看看整個執行過程:
a、獲取最常匹配串的長度'defg',長度4,pos1=3,pos2=3
b、獲取abc,qab相似長度度2
c、獲取空字串和abc相似度0
所以上述計算結果,相似字串長度為6.
3、順序敏感 順序敏感其實也是由於拆分的問題導致的。比如字串"PHP IS GREAT" 和字串"WITH MYSQL" 不同的順序得到的結果分別是2,3。