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

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

收到來信，到此一看。
憂鬱的貢丸湯大大，小弟能力十分有限，恐怕無法解開你的憂鬱，因為你的問題在於演算法，而非程式語言。
題目：文章每篇平均大約在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大大提妙招，諸位大大共讚賞！用字相同為同類，實際資訊恐有異？中文意義詞為主，關鍵字詞可否速？

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

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

你的問題應該是：
假設現有已知的文章 = {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進行檢測已經具有足夠的代表性可以判斷相似度了，不知你認為如何若是無法用人工維護，那麼想辦法自動擷取一些有意義統計資料，至少可以在進行比對之前先篩選

你是如何比較字串?

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

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掉呢...?減少很多迴圈..??