有沒有函式庫可以快速計算二個字串之間的相似度?

Question

請教各位大大,小弟目前在做一個資料庫, 希望在將某一篇文章存進資料庫之前, 能先比對它和現有文章的相似度; 如果發現有相同內容, 或是相似度達80% 以上者, 先做一些其他的處理之後再存入.所謂相似度百分比是指, 如果有二個字串 "今天是星期一" 和 "昨天是星期一", 則相似度便是高達 10/12 = 83.3%.如果字串是 "今天是星期一" 和 "明天是星期二" 相比, 則相似度便是 8/12 = 66.67%小弟寫了一個函數來計算二篇文章的相似度, 先以迴圈計算相同的字數, 再除以二篇的字數總和, 出來便是一個百分比.但是由於要比對的文章每篇平均一萬字上下, 資料庫現有文章又高達一萬多篇, 儘管該函數已經優化到每秒可以比對17~18篇(在我的Dothan 2.26GHz上面), 在P4-3.2G 上面每秒可以比對12~13篇, 效能仍是太慢, 比完一輪要跑十幾分鐘才能存入一篇新文章; 一天如果有三十篇文件要存入, Full-loading 跑六個小時都還比不完; 如果文章數量再增加, 情況只會更糟.試過以C++重寫, 透過DLL 來呼叫, 也試過以.NET來全部改寫, 效能也未見多大的進步. (有啦, 快了一成左右而已)不知是否有什麼既有的高效能函式庫提供這樣的比對函數?或是有什麼其他的方法或演算法可以提高比對的速度?本版常見的幾位大大們, 是否有什麼好建議? ^O^

回明忠大大: 文章內容可能是Word檔, 網頁, PDF, 純文字檔, eMail..... 都有可能!
但我都會分別先處理成pure text 才丟進去比對, 所以來源不造成效能影響. ^_^

更正:
剛才分析了一下, 真正要輸入比對的文章, 平均大約在25000~27000 字上下;
在我的Dothan 上面每秒比對數目下降至9篇不到...... (哭泣中....)

回明忠大大:
no, 直接用二篇裡面的相同字數, 除以二篇字數和.

回明忠大大:
是的, 若如您所說, B文的十個字是在A文的一百字內, 則相似率為10/110 = 9.1%
這個問題在小弟目前的這項應用上, 尚屬可接受.

回Diamond大大:
小弟這個問題是已經寫出一個函數來算出相似度, 所以應該還沒有到NP-complete 那麼難;
只是因為字串長度驚人, 且數量龐大, 所以用正常的暴力法來比對的話, 每篇文章要存入前得耗用六兆次的迴圈.
各位前輩經驗豐富, 小弟想請教是否有較好的演算法, 或是有高效的函式庫?
KMP 和Boyer Moore 我去看過, 主要偏向用來在A字串裡面找尋B字串的位置, 有一點不同.

回WJS大大:
是的! 我知道聽起來很不合理, 至少在數學上不應如此;
但是在實際的應用上還OK, 因為上萬字的文章裡, 要出現用字相同, 內容全異的機會不大;
至少這樣的機率和風險, 經評估後還可以承擔.

回Diamond大大:
您所說的 "不為人知" 的用意, 其實還好, 只是一個工程研發的Knowledge-Base.
文章內容..... 嗯..... 要找一個共通的關鍵字可能不容易.....

To WJS大大:
是的, 目前只考慮中文字, 英文還需要斷字, 會更麻煩一點.

To 明忠大大:
是的! 這樣可以讓實際比對的迴圈數少掉45%~60%, 因為有許多常用字,
而小弟目前正是這樣做.
但是多了這個Replace的function所花的時間, 卻又多花掉大約25~30%
造成整體省下的時間效益只有一半不到.

To 明忠大大:
Replace的方法我也試過好幾種, 看看能不能再提升一點速度:
1. 用VB內建的Repalce(string1, string2)
2. 用VB.NET 字串物件的 .Replace() 方法
3. 呼叫 strcpy, strcat 的字串處理API
結果速度差異不大;
目前一篇26000字的文章, 光是replace 100次就要花去2.5~2.8秒.
這個迴圈的code 我放在這裡:
http://tw.knowledge.yahoo.com/question/?qid=1306062010003

novus大大提的作法愈來愈接近我要問的東西了:
用一個完全不同的演算模式來計算不同字串之間的相似程度.
但是我有一個問題: 即使先用一個欄位把一萬篇文章的s2值事先存下, 要計算s3的時候也是要把x的內容和一萬個既有的A串接, 然後即時作壓縮才能得到s3, 不是嗎?
這樣假使realtime壓縮一篇x+A的時間要花0.1秒, 那一秒鐘的比對數目還是不到十篇, 效能看來並不樂觀 (因為還要串接及其他程序的時間)
還是其實用zip壓一篇二萬字的文章不用0.1秒? 我們估得太慢?

To Diamond 大大:
很感謝各位都對小弟這個難題竭心盡智, 真是各方好漢精銳盡出.
不過如果還要額外的maintain人力來做分類的話, 可能還有些困難需要排除.
目前方向是希望花這一次的effort, 後續就儘量不要再麻煩.
^_^

小弟在此感謝各位大大共襄盛舉,能集各路英雄好漢至此討論,小弟感到相當榮幸
各位所提到的方向,讓小弟受益不少
相信這二天來這版腦力激盪下,各位也應該從其他人身上得到許多靈感

明忠大大的做法和小弟大同小異,讓人一目瞭然
Diamond大大的方向應該是將來如果資料量到達一定水準時,必走的方向
novus大大提到系統化方式給了WJS和小弟很大的靈感,並且還能藉重發展多年高效能的zip壓縮演算法
最後WJS大大將字元數目簡化的做法,則是給了小弟臨門一腳的關鍵

simon最後用的方式是: 開一個65535的integer(),用來代表unicode二個byte的table,分別把A字串和B字串各掃過一次,並將每一字對應字碼填入integer(),每填入一次就計數加一.
最後再用另一個陣列來統計字元出現的次數.
在我的NB 上面,用"原來我不帥" 和"星座搏感情"比對一百次,只花了0.4 秒不到! 實際套到資料庫去,每秒可以比到四百多篇上下.

sample code在這裡,小弟不敢藏私,僅供各位參考.
http://*****/jxydg

這次答案小弟不想交付投票,因為我想來投票的網友程度,能區分各位大大的功力的可能不會太多
小弟在此僅以對自己幫助最大的答案來選,對其他大大還是致上十二萬分的謝意

Answer 1

To:版大
那您的意思是指不管位置,只要有字相同即可?
BBAACC跟AACCBB相似度=100%?

2006-06-20 16:53:11 補充：
若真的不管位置與詞意那就如同明忠大大講的直接用Replace移掉相同的字,再比較雙方各減少了幾個字元,再將差距加到代表不相似的總數就行了,但至少應只限於中文字吧?

2006-06-20 16:54:47 補充：
英文至少也該比較單字而非只比較字母XD

2006-06-21 17:32:24 補充：
'novus大大給了我1個方向,把文章每個字的數目記錄起來,產生1個新字串存在資料庫,以此方式比對100次的時間約1.2秒,不過此方式卻會增加資料庫的大小,如何取捨還是要看樓主了(另外再開個資料庫)Function Cmp(ByVal Str As String) As String    Dim S$, A$, T&        Str = Replace(Str, vbCrLf, Chr(2), , , vbBinaryCompare) '換行字元以chr(2)取代    T = Len(Str)    Do      S = Left$(Str, 1)      Cmp = Cmp & S      A = A & UBound(Split(Str, S)) & " "      Str = Replace(Str, S, "", , , vbBinaryCompare)    Loop Until Len(Str) = 0    '新字串以Chr(0)串接    Cmp = Cmp & Chr(0) & RTrim(A) & Chr(0) & T    '例:"AABBCCDDE"經過簡化變成"ABCDE"(簡化後每個字都只剩1個) & Chr(0) & "2 2 2 2 1"(每字的數量) & Chr(0) & "9"(總長度)End FunctionPrivate Sub Command1_Click()    Dim A() As Byte, S1$, S2$, X1() As String, X2() As String, Y1() As String, Y2() As String    Dim I&, T&, Sum&, N$, M$, J&, G%            M = "C:\原來我不帥.txt"    ReDim A(FileLen(M) - 1)    Open M For Binary As #1    Get #1, , A    Close #1    S2 = StrConv(A, vbUnicode)    S2 = Cmp(S2)        '時間應該從這裡開始計算,再加上從資料庫取出S2的時間*100次    D = Timer    N = "C:\星座搏感情.txt"    ReDim A(FileLen(N) - 1)    Open N For Binary As #1    Get #1, , A    Close #1    S1 = StrConv(A, vbUnicode)    S1 = Cmp(S1)    X1 = Split(S1, Chr(0))    Y1 = Split(X1(1))    For G = 1 To 100 '跑100次        Sum = 0: T = 0        X2 = Split(S2, Chr(0))        Y2 = Split(X2(1))        For I = 1 To Len(X1(0))            J = InStr(X2(0), Mid$(X1(0), I, 1))            If J Then               If Int(Y1(I - 1)) < Int(Y2(J - 1)) Then                  T = T + Y1(I - 1) * 2               Else                  T = T + Y2(J - 1) * 2               End If            End If        Next        Sum = Int(X1(2)) + Int(X2(2))    Next    Print Format(T / Sum, "0.000"), Timer - DEnd Sub

Answer 2

收到來信，到此一看。
憂鬱的貢丸湯大大，小弟能力十分有限，恐怕無法解開你的憂鬱，因為你的問題在於演算法，而非程式語言。
題目：文章每篇平均大約在25000~27000 字上下，資料庫現有文章又高達一萬多篇，而且又持續增長中。以25000字計算，這25000字需與25000×10000字進行比較，你要把電腦給累死嗎？！

2006-06-20 00:13:42 補充：
解決之道暫時還想不到，但有些建議：
1.類似這種大量資料計算的工作，使用螞蟻雄兵的分散式計算應對之，找多部伺服器以multi-thread方式解之，但此方法只能提高運算速度暫時應付，非長久之計。因為這個問題，是一個非多項式時間的問題(NP problem)。
2.徹底瞭問題的需求，將此一NP problem化成P Problem，如此就可大幅降低運算所需時間。但要如何化解，由於所知有限，尚難回復！

2006-06-20 00:26:56 補充：
字串搜尋比對(Pattern Matching)有2種演算法可供參考，希望能夠有用。
1.The Knuth Morris Pratt pattern search method
2.The Boyer Moore pattern search method
不過在也只能加速而已，尚未能達到P Problem之境界。

2006-06-20 00:33:13 補充：
要使問題成為P Problem之境界，初步認為關鍵在於下面這段話『小弟目前在做一個資料庫, 希望在將某一篇文章存進資料庫之前, 能先比對它和現有文章的相似度; 如果發現有相同內容, 或是相似度達80% 以上者, 先做一些其他的處理之後再存入.』
1.由上可知在資料庫內的部份文章可能是不需經過比較便可推算其相似度。
2.將文章存進資料庫內且又陸續存入新的文章，這一定有一個不為我知的目的，有可能找出一個省時省力的關鍵字嗎？

2006-06-20 11:55:22 補充：
不才之愚見，惠請斧正！
工程研發的Knowledge-Base. 使用這種暴力全文比對的方式分類？ 請恕不才孤陋寡聞！
竊以為工程研發的Knowledge-Base必有其應用之方向及研發之方向，何不以摘要萃取器(abstractor)作為嚐試之新方向呢？！
1.先將Knowledge-Base先進行摘要萃取，人工或自動進行。
2.依摘要進行分類。
3.新文章增加時，先進行摘要萃取，並與庫存各分類摘要進行初步比對，再就比對成果挑選符合比率較高的文章進行細部比對。
Diamond曰：暴力比對加速難，層層篩選速速看！？

2006-06-20 20:21:06 補充：
不才心中已有若干想法，惟非一時可使他人理解。希藉由問題發問回復方式能得一一化解，不知各位意下如何？

問題1：對一篇文章之重點加以摘要萃取以利有效縮小比較資料數量，是否同意摘要萃取器(abstractor)作為嚐試之新方向呢？

後續之問題將待前面之問題已有回復後，再行提出！

2006-06-20 22:51:32 補充：
不才看到novus大大的回答，覺得非常有用。但有一疑問：增加一篇新文章只要花個幾秒鐘壓縮，剩下來的是否應該還要依照3.將x串接A得到z字串，壓縮z字串，得到壓縮後的大小s3。其後才是數字運算，一秒比對十萬篇也不是問題。
若不才推論正確，則若壓縮一篇約0.1秒，則十萬篇共需約2.78小時。
又或許novus大大的意思並不需要一一比對十萬篇，那又應如何比對呢？還請費心指導！

2006-06-21 11:24:49 補充：
首先感謝novus大大對不才意見之評析，不才以為novus大大所提的壓縮方法與不才之摘要萃取器(abstractor)概念乃殊途同歸，不知各位大大意下如何？因為壓縮乃將檔案內之字及詞的資訊亂度(entropy)縮小，此乃摘要也！？若如此，不才再提另一概念，請各位大大指正！在之前，不才提出愚見概念如下：3.新文章增加時，先進行摘要萃取，並與庫存各分類摘要進行初步比對，再就比對成果挑選符合比率較高的文章進行細部比對。也就是先分類，若同質性高者，其實不必再比較了。以實例解釋之：-------------若資料庫內已有文章10篇，一開始由人工分類為3類，並以壓縮方式萃取其摘要(這一點個人頗為困惑，但因憂鬱的貢丸湯大大喜愛此法，故暫時使用，若有興趣可另外討論)假設狀況如下：=============原有資料庫----------class AFile   Original   Compressed   Matcha1     45KB       10KB            100%a2     50KB       15KB              80%a3     40KB       9KB                85%class BFile   Original   Compressed   Matchb1     48KB       11KB           100%b2     53KB       19KB             81%b3     38KB        8KB              87%class CFile   Original   Compressed   Matchc1     55KB       10KB            100%c2     60KB       15KB              80%c3     30KB        9KB               85%c4     42KB       10KB              90%新增文章--------File   Original   Compressed   Matchd      62KB       20KB             a1:50%                                              b1:10%                                              c1:70%由於class C Match Ratio最高，故取class C之其它檔案繼續比較。                                              c2:75%                                              c3:81%符合class C門檻值，新增至class C。新增文章之比較法，可使用novus大大所提的壓縮方法：3.將x串接A得到z字串，壓縮z字串，得到壓縮後的大小s34.若x和A之間的歧異度越大，則(s1+s2)-s3就越大，因此這個值可以表示歧異度。5.[(s1+s2)-s3]/s3可以將差異的程度正規化為0~1之間的值，0表示完全不同，1表示完全相同。  故其比較之資料是摘要萃取過的，即檔案已先分別壓縮，再將欲比較之2壓縮檔相加後再進行壓縮，以求其歧異度(或稱資訊亂度(entropy))。經過摘要萃取及分類過濾後，其所比對之資料量已巨幅縮小了，這應已達不才之前期望：將非多項式時間的問題(NP problem)轉化為多項式時間的問題(P problem)。不才以為原問題之時間複雜度為O(N)，現似已降為O(logN)。但以上愚見猶有不足之處，尚需人工時時再注意是否需將原分類細分或再增加新的大分類，此又是另一項大工程也。不才打油詩曰：「比對工作工程大，層層篩選何妨速？ 壓縮分類可能速？人工作業又費工！」。不才雖提出如上之愚見，但心中實另有困惑，有打油詩為證：貢丸湯大提好問，不才腦袋作體操。novus大大提妙招，諸位大大共讚賞！用字相同為同類，實際資訊恐有異？中文意義詞為主，關鍵字詞可否速？

Answer 3

感謝novus大大, 您提的方向很好, 也許值得花時間寫來實測幾篇看看效能如何.

Answer 4

跳脫字串處理的演算法
純粹從資訊理論下手會比較容易

你的問題應該是：
假設現有已知的文章 = {A, B, C, D, E,.....}
(每個大寫英文字皆為一篇文章內容，也就是一個字串)

現在有一個新的字串x，我們希望找到一個方法可以量化x和我們指定的字串之間的歧異度

你可以試試下面的方法

1.將x用最佳化的方式壓縮，壓縮後的大小為s1
2.將已知的文章(例如A)壓縮，壓縮後的大小為s2
3.將x串接A得到z字串，壓縮z字串，得到壓縮後的大小s3
4.若x和A之間的歧異度越大，則(s1+s2)-s3就越大，因此這個值可以表示歧異度。
5.[(s1+s2)-s3]/s3可以將差異的程度正規化為0~1之間的值，0表示完全不同，1表示完全相同。(由於不存在完美的壓縮法，所以不可能會出現剛好是0或1，就算兩篇文章完全相同可能也只有0.99)。然而此正規化的值不具有等距性，所以0.8並不意味著80%相同，只代表0.8的相似程度高於0.75，所以實用的門檻值要實驗一下

因為是資料庫方面的應用，所以對於已知的文章可以增加一個欄位來存放壓縮後的大小，這只是一個數值而已，但是可以避免每次重算的時間浪費。

增加一篇新文章只要花個幾秒鐘壓縮，剩下來的只不過是數字運算，一秒比對十萬篇也不是問題

實作注意事項：這裡提到的壓縮演算法，照理說用傳說中絕無任何累贅的終極壓縮最好，但是要是真有這種壓縮，執行時間會變成無限大，那還是字串搜尋還比較快。現有的Zip演算法將就用一下吧(據說.NET 2.0有GZip的程式庫，足不足以勝任我就不知道了)
由於一般套裝程式庫的壓縮結果可能還會包含檔頭資訊，造成計算上的誤差，可能要想辦法克服

2006-06-20 23:34:17 補充：
不小心鬧了一個笑話....
多謝指正
串接的部分仍然是需要逐一去做的

2006-06-21 00:38:30 補充：
這個方法說穿了，就是你現在正在做的事，只是比較系統化而已

壓縮演算法速度的話，我用C++搭配zlib，壓50k的文字檔(含讀寫檔案所花費的時間)平均為0.012秒。壓100k的文字檔，平均一篇0.025秒。

壓縮的另一項附帶好處是不必考慮語言編碼問題，中、英、日、韓甚至二進位通吃

要實際比較歧異度都有速度極限，因為不管再怎麼優化程式，最後還是要面臨工作複雜度的問題。

若要在工作複雜度上突破就不能真的去比較全部的歧異度，Diamond Liu大大的意見值得參考

2006-06-21 00:39:22 補充：
ps.上述測試的電腦為P4 2.4G

2006-06-21 18:07:47 補充：
初步用C++和zlib做了一些實驗針對32k以下的字串若是合併、壓縮等動作完全在記憶體完成而不用寫入檔案大約一秒中可以比對200~400篇(上述X萬篇純粹是搞錯了)對於超過32k以上的字串，我認為只取32k進行檢測已經具有足夠的代表性可以判斷相似度了，不知你認為如何若是無法用人工維護，那麼想辦法自動擷取一些有意義統計資料，至少可以在進行比對之前先篩選

Answer 5

你是如何比較字串?

Answer 6

文章的內容從哪裡來的...?檔案?表單?

2006-06-19 22:48:40 補充：
所謂相似度百分比是指, 如果有二個字串 "今天是星期一" 和 "昨天是星期一", 則相似度便是高達 10/12 = 83.3%.如果字串是 "今天是星期一" 和 "明天是星期二" 相比, 則相似度便是 8/12 = 66.67%
----
10/12 跟 8 /12 你是用內碼去比對嗎...?

2006-06-19 23:49:07 補充：
我有幾個問題，第一個是你怎麼解決字數的問題...?如果一篇文章有一百字，另外一篇文章有十個字...，但是搞不好這十個字，是在，一百個字中的十個字...A文：所謂相似度百分比是指, 如果有二個字串 "今天是星期一" 和 "昨天是星期一", 則相似度便是高達 10/12 = 83.3%.如果字串是 "今天是星期一" 和 "明天是星期二" 相比, 則相似度便是 8/12 = 66.67%B文"今天是星期一" 和 "明天是星期那這樣算起的相似度是....?第二個這樣比對的用途是...?搞不好可以從資料庫下手....

2006-06-20 01:12:10 補充：
如果只是比對位址，然後用二篇裡面的相同字數, 除以二篇字數和.又加上"80%以上，先做一些其他的處理之後再存入"...所以80%以下不處理..所以先比對字數..?兩篇文章小的那篇字數/兩篇文章總字數 要大於0.8才開始比對..?.....

2006-06-20 12:00:19 補充：
如果不管位置的話...只算字數的話，每跑一次回圈...就把雙方的相同的字數直接Replace掉呢...?減少很多迴圈..??