計算字符串相似度算法

1、計算字符串相似度算法Levenshtein博客分類： 我喜歡的算法levenshtein相似度編輯距離算法實現(xiàn)0.這個算法實現(xiàn)起來很簡單1.百度百科介紹：Levenshtein 距離，又稱編輯距離，指的是兩個字符串之間，由一個轉(zhuǎn)換成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。編輯距離的算法是首先由俄國科學(xué)家Levenshtein提出的，故又叫Levenshtein Distance。2.用途模糊查詢3.實現(xiàn)過程a.首先是有兩個字符串,這里寫一個簡單的 abc和abeb.將字符串想象成下面的結(jié)構(gòu)。A處是一個標記，為了方便講解，不是這個表

2、的內(nèi)容。abcabcabe0123a1A處b2e3c.來計算A處出得值它的值取決于：左邊的1、上邊的1、左上角的0.按照Levenshtein distance的意思：上面的值和左面的值都要求加1，這樣得到1+1=2。A處由于是兩個a相同，左上角的值加0.這樣得到0+0=0。這是后有三個值，左邊的計算后為2，上邊的計算后為2，左上角的計算為0，所以A處取他們里面最小的0.d.于是表成為下面的樣子abcabcabe0123a10b2B處e3在B處會同樣得到三個值，左邊計算后為3，上邊計算后為1，在B處由于對應(yīng)的字符為a、b，不相等，所以左上角應(yīng)該在當(dāng)前值的基礎(chǔ)上加1，這樣得到1+1=2，在（3,

3、1,2）中選出最小的為B處的值。e.于是表就更新了abcabcabe0123a10b21e3C處C處計算后：上面的值為2，左邊的值為4，左上角的：a和e不相同，所以加1，即2+1，左上角的為3。在（2,4,3）中取最小的為C處的值。f.于是依次推得到abc0123a1A處0D處1G處2b2B處1E處0H處1e3C處2F處1I處1I處:表示abc 和abe 有1個需要編輯的操作。這個是需要計算出來的。同時，也獲得一些額外的信息。A處:表示a 和a 需要有0個操作。字符串一樣B處:表示ab 和a 需要有1個操作。C處:表示abe 和a 需要有2個操作。D處:表示a 和ab 需要有1個操作。E處:表

4、示ab 和ab 需要有0個操作。字符串一樣F處:表示abe 和ab 需要有1個操作。G處:表示a 和abc 需要有2個操作。H處:表示ab 和abc 需要有1個操作。I處:表示abe 和abc 需要有1個操作。g.計算相似度先取兩個字符串長度的最大值maxLen，用1-（需要操作數(shù)除maxLen），得到相似度。例如abc 和abe 一個操作，長度為3，所以相似度為1-1/3=0.666。4.代碼實現(xiàn)直接能運行， 復(fù)制過去就行。Java代碼1. packagecode;2. 3. /*4. *className:MyLevenshtein.java5. *classDescription:Lev

5、enshteinDistance算法實現(xiàn)6. *可以使用的地方：DNA分析拼字檢查語音辨識抄襲偵測7. *author:donghai.wan8. *createTime:2012-1-129. */10. publicclassMyLevenshtein11. 12. publicstaticvoidmain(Stringargs)13. /要比較的兩個字符串14. Stringstr1=今天星期四;15. Stringstr2=今天是星期五;16. levenshtein(str1,str2);17. 18. 19. /*20. *DNA分析拼字檢查語音辨識抄襲偵測21. *22. *cr

6、eateTime2012-1-1223. */24. publicstaticvoidlevenshtein(Stringstr1,Stringstr2)25. /計算兩個字符串的長度。26. intlen1=str1.length();27. intlen2=str2.length();28. /建立上面說的數(shù)組，比字符長度大一個空間29. intdif=newintlen1+1len2+1;30. /賦初值，步驟B。31. for(inta=0;a=len1;a+)32. difa0=a;33. 34. for(inta=0;a=len2;a+)35. dif0a=a;36. 37. /計

7、算兩個字符是否一樣，計算左上的值38. inttemp;39. for(inti=1;i=len1;i+)40. for(intj=1;ji)64. min=i;65. 66. 67. returnmin;68. 69. 70. 5.猜測原理為什么這樣就能算出相似度了？首先在連續(xù)相等的字符就可以考慮到紅色是取值的順序。1.今天周一 天周一天周一0123今1123天2123周3213一4331實現(xiàn)是去掉“今”，一步完成。2.聽說馬上就要放假了 你聽說要放假了你聽說要放假了01234567聽11123456說22212345馬33322345上44433345就55544445要66654555放

8、77765456假88876546了99987664這兩個字符串是：去掉“你”，加上“馬上就”，總共四步操作。3.還是沒弄懂6.結(jié)束算法優(yōu)化空間很大。最后也沒弄懂為什么這樣算能算出相似度。7頂0踩分享到：StringUtils源碼理解（下）|StringUtils源碼理解（中）有點意思的方法 2012-01-13 00:42 瀏覽 22393 評論(11) 分類:編程語言 相關(guān)推薦評論11 樓xu-ch2013-07-20今天面試，遇到這題，求出了相似度，面試官問我算法原理是什么，悲催的我沒有答上來10 樓flywangfei2013-06-08你是創(chuàng)新工場的么？9 樓beike2013-03

9、-30mark8 樓yangxiutian2012-01-13算法、數(shù)據(jù)結(jié)構(gòu) 很重要 可是沒掌握啊7 樓wdhdmx2012-01-13wangchen.ily 寫道g.計算相似度先取兩個字符串長度的最大值maxLen，用需要操作數(shù)除maxLen，得到相似度。例如abc 和abe 一個操作，長度為3，所以相似度為1/2=0.666有問題吧：例如abc和abe maxLen=3 需要操作數(shù)是1應(yīng)該是1/3=0.333謝謝提出來，大意了。我已經(jīng)改回來了。6 樓wangchen.ily2012-01-13g.計算相似度先取兩個字符串長度的最大值maxLen，用需要操作數(shù)除maxLen，得到相似度。例

10、如abc 和abe 一個操作，長度為3，所以相似度為1/2=0.666有問題吧：例如abc和abe maxLen=3 需要操作數(shù)是1應(yīng)該是1/3=0.3335 樓wwsnowfoxww2012-01-13沒有看懂什么意思4 樓wdhdmx2012-01-13我寫錯了，不是相似度，是 “最少編輯操作次數(shù)”。 為什么用這個方法能算出最少編輯次數(shù)，相似度這個我理解了，已經(jīng)。3 樓ansjsun2012-01-13Java代碼1. System.out.println(字符串+str1+與+str2+的比較);2. /取數(shù)組右下角的值，同樣不同位置代表不同字符串的比較3. System.out.pri

11、ntln(差異步驟：+diflen1len2);4. /計算相似度5. floatsimilarity=1-(float)diflen1len2/Math.max(str1.length(),str2.length();我覺得吧.首先他是一個參考前面過程的算法.當(dāng)?shù)搅俗詈缶褪莇iflen1len2的時候.就是最終的差異值.這個差一值越大肯定就越不一樣然后根據(jù).差異值比上文本長度. 被1減去 .所以越趨近于1.說明文本越相似.2 樓liuningbo2012-01-13尷尬1 樓ansjsun2012-01-13最后一句我徹底凌亂了自己實現(xiàn)文本相似度算法（余弦定理）發(fā)表于3年前(2012-03-

12、04 16:59) 閱讀（20540）|評論（21）105人收藏此文章,我要收藏贊13慕課網(wǎng)，程序員升職加薪神器，點擊免費學(xué)習(xí)Java算法余弦定理距離編輯相似度最近由于工作項目，需要判斷兩個txt文本是否相似，于是開始在網(wǎng)上找資料研究，因為在程序中會把文本轉(zhuǎn)換成String再做比較，所以最開始找到了這篇關(guān)于距離編輯算法Blog寫的非常好，受益匪淺。 于是我決定把它用到項目中，來判斷兩個文本的相似度。但后來實際操作發(fā)現(xiàn)有一些問題：直接說就是查詢一本書中的相似章節(jié)花了我7、8分鐘；這是我不能接受 于是停下來仔細分析發(fā)現(xiàn)，這種算法在此項目中不是特別適用，由于要判斷一本書中是否有相同章節(jié)，所以每兩個章

13、節(jié)之間都要比較，若一本書書有x章的話，這里需對比x(x-1)/2次；而此算法采用矩陣的方式，計算兩個字符串之間的變化步驟，會遍歷兩個文本中的每一個字符兩兩比較，可以推斷出時間復(fù)雜度至少為document1.length document2.length，我所比較的章節(jié)字數(shù)平均在幾千一萬字；這樣計算實在要了老命。 想到Lucene中的評分機制，也是算一個相似度的問題，不過它采用的是計算向量間的夾角（余弦公式），在google黑板報中的：數(shù)學(xué)之美（余弦定理和新聞分類）也有說明，可以通過余弦定理來判斷相似度；于是決定自己動手試試。 首相選擇向量的模型：在以字為向量還是以詞為向量的問題上，糾結(jié)了一會；

14、后來還是覺得用字，雖然詞更為準確，但分詞卻需要增加額外的復(fù)雜度，并且此項目要求速度，準確率可以放低，于是還是選擇字為向量。 然后每個字在章節(jié)中出現(xiàn)的次數(shù)，便是以此字向量的值?，F(xiàn)在我們假設(shè)： 章節(jié)1中出現(xiàn)的字為：Z1c1,Z1c2,Z1c3,Z1c4Z1cn；它們在章節(jié)中的個數(shù)為：Z1n1,Z1n2,Z1n3Z1nm；章節(jié)2中出現(xiàn)的字為：Z2c1,Z2c2,Z2c3,Z2c4Z2cn；它們在章節(jié)中的個數(shù)為：Z2n1,Z2n2,Z2n3Z2nm； 其中，Z1c1和Z2c1表示兩個文本中同一個字，Z1n1和Z2n1是它們分別對應(yīng)的個數(shù)，最后我們的相似度可以這么計算： 程序?qū)崿F(xiàn)如下：（若有可優(yōu)化或更好

15、的實現(xiàn)請不吝賜教）?12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091public class CosineSimilarAlgorithm public static double getSimilarity(String doc1, String doc2) if (doc1 != null & d

16、oc1.trim().length() 0 & doc2 != null& doc2.trim().length() 0) Map AlgorithmMap = new HashMap();/將兩個字符串中的中文字符以及出現(xiàn)的總數(shù)封裝到，AlgorithmMap中for (int i = 0; i doc1.length(); i+) char d1 = doc1.charAt(i);if(isHanZi(d1)int charIndex = getGB2312Id(d1);if(charIndex != -1)int fq = AlgorithmMap.get(charIndex);if(f

17、q != null & fq.length = 2)fq0+;else fq = new int2;fq0 = 1;fq1 = 0;AlgorithmMap.put(charIndex, fq);for (int i = 0; i doc2.length(); i+) char d2 = doc2.charAt(i);if(isHanZi(d2)int charIndex = getGB2312Id(d2);if(charIndex != -1)int fq = AlgorithmMap.get(charIndex);if(fq != null & fq.length = 2)fq1+;els

18、e fq = new int2;fq0 = 0;fq1 = 1;AlgorithmMap.put(charIndex, fq);Iterator iterator = AlgorithmMap.keySet().iterator();double sqdoc1 = 0;double sqdoc2 = 0;double denominator = 0; while(iterator.hasNext()int c = AlgorithmMap.get(iterator.next();denominator += c0*c1;sqdoc1 += c0*c0;sqdoc2 += c1*c1;retur

19、n denominator / Math.sqrt(sqdoc1*sqdoc2); else throw new NullPointerException( the Document is null or have not cahrs!);public static boolean isHanZi(char ch) / 判斷是否漢字return (ch = 0x4E00 & ch = 0x9FA5);/* 根據(jù)輸入的Unicode字符，獲取它的GB2312編碼或者ascii編碼，* * param ch* 輸入的GB2312中文字符或者ASCII字符(128個)* return ch在GB2312中的位置，-1表示該字符不認識*/public static short getGB2312Id(char ch) try byte buffer = Character.toStri