計(jì)算字符串相似度算法

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

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

3、1,2）中選出最小的為B處的值。e.于是表就更新了abcabcabe0123a10b21e3C處C處計(jì)算后：上面的值為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個(gè)需要編輯的操作。這個(gè)是需要計(jì)算出來(lái)的。同時(shí)，也獲得一些額外的信息。A處:表示a 和a 需要有0個(gè)操作。字符串一樣B處:表示ab 和a 需要有1個(gè)操作。C處:表示abe 和a 需要有2個(gè)操作。D處:表示a 和ab 需要有1個(gè)操作。E處:表

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

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

6、eateTime2012-1-1223. */24. publicstaticvoidlevenshtein(Stringstr1,Stringstr2)25. /計(jì)算兩個(gè)字符串的長(zhǎng)度。26. intlen1=str1.length();27. intlen2=str2.length();28. /建立上面說(shuō)的數(shù)組，比字符長(zhǎng)度大一個(gè)空間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. /計(jì)

7、算兩個(gè)字符是否一樣，計(jì)算左上的值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.猜測(cè)原理為什么這樣就能算出相似度了？首先在連續(xù)相等的字符就可以考慮到紅色是取值的順序。1.今天周一 天周一天周一0123今1123天2123周3213一4331實(shí)現(xiàn)是去掉“今”，一步完成。2.聽(tīng)說(shuō)馬上就要放假了 你聽(tīng)說(shuō)要放假了你聽(tīng)說(shuō)要放假了01234567聽(tīng)11123456說(shuō)22212345馬33322345上44433345就55544445要66654555放

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

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

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

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

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

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

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

15、的實(shí)現(xiàn)請(qǐng)不吝賜教）?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();/將兩個(gè)字符串中的中文字符以及出現(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個(gè))* return ch在GB2312中的位置，-1表示該字符不認(rèn)識(shí)*/public static short getGB2312Id(char ch) try byte buffer = Character.toStri