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

1、 HYPERLINK /blog/1343856 計(jì)算(j sun)字符串相似度算法Levenshtein博客分類(fn li)： HYPERLINK /category/178462 我喜歡(x huan)的算法 HYPERLINK /blogs/tag/levenshtein levenshtein HYPERLINK /blogs/tag/%E7%9B%B8%E4%BC%BC%E5%BA%A6 相似度 HYPERLINK /blogs/tag/%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB 編輯距離 HYPERLINK /blogs/tag/%E7%AE%97%

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

3、內(nèi)容。abcabcabe0123a1A處b2e3c.來計(jì)算A處出得值它的值取決于：左邊的1、上邊的1、左上角的0.按照Levenshtein distance的意思：上面的值和左面的值都要求(yoqi)加1，這樣得到1+1=2。A處由于(yuy)是兩個(gè)a相同，左上角的值加0.這樣得到0+0=0。這是后有三個(gè)值，左邊的計(jì)算后為2，上邊(shng bin)的計(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)前值的

4、基礎(chǔ)上加1，這樣得到1+1=2，在（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ì)算出來的。同時(shí)，也獲得一些額外的信息。A處:表示(biosh)a 和a 需要有0個(gè)操作。字符串一樣B處:表示(biosh)ab 和a 需要有1個(gè)操作。C處:表示(bio

5、sh)abe 和a 需要有2個(gè)操作。D處:表示a 和ab 需要有1個(gè)操作。E處:表示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è)字符串長度的最大值maxLen，用1-（需要操作數(shù)除maxLen），得到相似度。例如abc 和abe 一個(gè)操作，長度為3，所以相似度為1-1/3=0.666。4.代碼實(shí)現(xiàn)直接能運(yùn)行， 復(fù)制過去就行。Java代碼packagecode;/*className:MyLevenshtein.

6、java*classDescription:LevenshteinDistance算法實(shí)現(xiàn)*可以使用的地方：DNA分析拼字檢查語音辨識(shí)抄襲偵測*author:donghai.wan*createTime:2012-1-12*/publicclassMyLevenshteinpublicstaticvoidmain(Stringargs)/要比較的兩個(gè)字符串Stringstr1=今天星期四;Stringstr2=今天是星期五;levenshtein(str1,str2);/*DNA分析(fnx)拼字檢查語音辨識(shí)抄襲偵測*createTime2012-1-12*/publicstaticvoidl

7、evenshtein(Stringstr1,Stringstr2)/計(jì)算(j sun)兩個(gè)字符串的長度。intlen1=str1.length();intlen2=str2.length();/建立上面(shng min)說的數(shù)組，比字符長度大一個(gè)空間intdif=newintlen1+1len2+1;/賦初值，步驟B。for(inta=0;a=len1;a+)difa0=a;for(inta=0;a=len2;a+)dif0a=a;/計(jì)算兩個(gè)字符是否一樣，計(jì)算左上的值inttemp;for(inti=1;i=len1;i+)for(intj=1;ji)min=i;returnmin;5.猜測

8、(cic)原理為什么這樣(zhyng)就能算出相似度了？首先在連續(xù)相等的字符(z f)就可以考慮到紅色是取值的順序。1.今天周一 天周一天周一0123今1123天2123周3213一4331實(shí)現(xiàn)是去掉“今”，一步完成。2.聽說馬上就要放假了 你聽說要放假了你聽說要放假了01234567聽11123456說22212345馬33322345上44433345就55544445要66654555放77765456假88876546了99987664這兩個(gè)字符串是：去掉“你”，加上“馬上(mshng)就”，總共四步操作。3.還是(hi shi)沒弄懂6.結(jié)束(jish)算法優(yōu)化空間很大。最后也沒弄懂

9、為什么這樣算能算出相似度。7頂0踩分享到： HYPERLINK /blog/1350164 o StringUtils源碼理解（下） StringUtils源碼理解（下）| HYPERLINK /blog/1342437 o StringUtils源碼理解（中）有點(diǎn)意思的方法 StringUtils源碼理解（中）有點(diǎn)意思的方法2012-01-13 00:42瀏覽 22393 HYPERLINK /blog/1343856 l comments 評(píng)論(11)分類: HYPERLINK /blogs/category/language 編程語言 HYPERLINK /wiki/blog/13438

10、56 t _blank 相關(guān)推薦評(píng)論11 樓 HYPERLINK / o xu-ch t _blank xu-ch2013-07-20今天面試，遇到這題，求出了相似度，面試官問我算法原理是什么，悲催的我沒有答上來10 樓 HYPERLINK / o flywangfei t _blank flywangfei2013-06-08你是創(chuàng)新工場的么？9 樓 HYPERLINK / o beike t _blank beike2013-03-30mark8 樓 HYPERLINK / o yangxiutian t _blank yangxiutian2012-01-13算法、數(shù)據(jù)結(jié)構(gòu) 很重要 可是

11、沒掌握啊7 樓 HYPERLINK / o wdhdmx t _blank wdhdmx2012-01-13wangchen.ily 寫道g.計(jì)算相似度先取兩個(gè)字符串長度的最大值maxLen，用需要操作數(shù)除maxLen，得到相似度。例如abc 和abe 一個(gè)操作，長度為3，所以相似度為1/2=0.666有問題吧：例如abc和abe maxLen=3 需要操作數(shù)是1應(yīng)該是1/3=0.333謝謝提出來，大意(dy)了。我已經(jīng)改回來了。6 樓 HYPERLINK / o wangchen.ily t _blank wangchen.ily2012-01-13g.計(jì)算相似度先取兩個(gè)字符串長度的最大值m

12、axLen，用需要操作數(shù)除maxLen，得到相似度。例如abc 和abe 一個(gè)操作，長度為3，所以(suy)相似度為1/2=0.666有問題吧：例如abc和abe maxLen=3 需要操作數(shù)是1應(yīng)該是1/3=0.3335 樓 HYPERLINK / o wwsnowfoxww t _blank wwsnowfoxww2012-01-13沒有看懂什么(shn me)意思4 樓 HYPERLINK / o wdhdmx t _blank wdhdmx2012-01-13我寫錯(cuò)了，不是相似度，是 “最少編輯操作次數(shù)”。 為什么用這個(gè)方法能算出最少編輯次數(shù)，相似度這個(gè)我理解了，已經(jīng)。3 樓 HYPE

13、RLINK / o ansjsun t _blank ansjsun2012-01-13Java代碼System.out.println(字符串+str1+與+str2+的比較);/取數(shù)組右下角的值，同樣不同位置代表不同字符串的比較System.out.println(差異步驟：+diflen1len2);/計(jì)算相似度floatsimilarity=1-(float)diflen1len2/Math.max(str1.length(),str2.length();我覺得吧.首先他是一個(gè)參考前面過程的算法.當(dāng)?shù)搅俗詈缶褪莇iflen1len2的時(shí)候.就是最終的差異值.這個(gè)差一值越大肯定就越不一樣

14、然后根據(jù).差異值比上文本長度. 被1減去 .所以越趨近于1.說明文本越相似.2 樓 HYPERLINK / o liuningbo t _blank liuningbo2012-01-13尷尬1 樓 HYPERLINK / o ansjsun t _blank ansjsun2012-01-13最后一句我徹底凌亂了自己實(shí)現(xiàn)文本相似(xin s)度算法（余弦定理）發(fā)表(fbio)于3年前(2012-03-04 16:59) 閱讀(yud)（20540）|評(píng)論（ HYPERLINK /BreathL/blog/42477 l comments 21）105人收藏此文章, HYPERLINK jav

15、ascript:add_to_favor(42477,3) o 添加到收藏夾 我要收藏贊13 HYPERLINK /course/list?from=oschina t _blank 慕課網(wǎng)，程序員升職加薪神器，點(diǎn)擊免費(fèi)學(xué)習(xí) HYPERLINK /search?scope=blog&q=Java Java HYPERLINK /search?scope=blog&q=%E7%AE%97%E6%B3%95 算法 HYPERLINK /search?scope=blog&q=%E4%BD%99%E5%BC%A6%E5%AE%9A%E7%90%86 余弦定理 HYPERLINK /search?sc

16、ope=blog&q=%E8%B7%9D%E7%A6%BB%E7%BC%96%E8%BE%91 距離編輯 HYPERLINK /search?scope=blog&q=%E7%9B%B8%E4%BC%BC%E5%BA%A6 相似度最近由于工作項(xiàng)目，需要判斷兩個(gè)txt文本是否相似，于是開始在網(wǎng)上找資料研究，因?yàn)樵诔绦蛑袝?huì)把文本轉(zhuǎn)換成String再做比較，所以最開始找到了這篇關(guān)于 HYPERLINK /blog/1343856 t _blank 距離編輯算法Blog寫的非常好，受益匪淺。 于是我決定把它用到項(xiàng)目中，來判斷兩個(gè)文本的相似度。但后來實(shí)際操作發(fā)現(xiàn)有一些問題：直接說就是查詢一本書中的相似章

17、節(jié)花了我7、8分鐘；這是我不能接受 于是停下來仔細(xì)分析發(fā)現(xiàn)，這種算法在此項(xiàng)目中不是特別適用，由于要判斷一本書中是否有相同章節(jié)，所以每兩個(gè)章節(jié)之間都要比較，若一本書書有x章的話，這里需對(duì)比x(x-1)/2次；而此算法采用矩陣的方式，計(jì)算兩個(gè)字符串之間的變化步驟，會(huì)遍歷兩個(gè)文本中的每一個(gè)字符兩兩比較，可以推斷出時(shí)間復(fù)雜度至少為document1.length document2.length，我所比較的章節(jié)字?jǐn)?shù)平均在幾千一萬字；這樣計(jì)算實(shí)在要了老命。 想到Lucene中的評(píng)分機(jī)制，也是算一個(gè)相似度的問題，不過它采用的是計(jì)算向量間的夾角（余弦公式），在google黑板報(bào)中的： HYPERLINK .

18、hk/ggblog/googlechinablog/2006/07/12_4010.html t _blank 數(shù)學(xué)之美（余弦定理和新聞分類）也有說明，可以通過余弦定理來判斷相似度；于是決定自己動(dòng)手試試。 首相選擇向量的模型：在以字為向量還是以詞為向量的問題上，糾結(jié)了一會(huì)；后來還是覺得用字，雖然詞更為準(zhǔn)確，但分詞卻需要增加額外的復(fù)雜度，并且此項(xiàng)目要求速度，準(zhǔn)確率可以(ky)放低，于是還是選擇字為向量。 然后(rnhu)每個(gè)字在章節(jié)中出現(xiàn)的次數(shù)，便是以此字向量的值?，F(xiàn)在我們假設(shè)： 章節(jié)(zhngji)1中出現(xiàn)的字為：Z1c1,Z1c2,Z1c3,Z1c4Z1cn；它們在章節(jié)中的個(gè)數(shù)為：Z1n1,

19、Z1n2,Z1n3Z1nm；章節(jié)2中出現(xiàn)的字為：Z2c1,Z2c2,Z2c3,Z2c4Z2cn；它們在章節(jié)中的個(gè)數(shù)為：Z2n1,Z2n2,Z2n3Z2nm； 其中，Z1c1和Z2c1表示兩個(gè)文本中同一個(gè)字，Z1n1和Z2n1是它們分別對(duì)應(yīng)的個(gè)數(shù)，最后我們的相似度可以這么計(jì)算： 程序?qū)崿F(xiàn)如下：（若有可優(yōu)化或更好的實(shí)現(xiàn)請不吝賜教） HYPERLINK /BreathL/blog/42477 ?12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565

20、758596061626364656667686970717273747576777879808182838485868788899091public class CosineSimilarAlgorithm public static double getSimilarity(String doc1, String doc2) if (doc1 != null & doc1.trim().length() 0 & doc2 != null& doc2.trim().length() 0) Map AlgorithmMap = new HashMap();/將兩個(gè)字符串中的中文字符以及出現(xiàn)的總

21、數(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(fq != null & fq.length = 2)fq0+;else fq = new int2;fq0 = 1;fq1 = 0;AlgorithmMap.put(charIndex, fq);for (int i = 0;

22、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+;else fq = new int2;fq0 = 0;fq1 = 1;AlgorithmMap.put(charIndex, fq);Iterator iterator = AlgorithmMap.keySet().iterator

23、();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;return denominator / Math.sqrt(sqdoc1*sqdoc2); else throw new NullPointerException( the Document is null or have not ca

24、hrs!);public static boolean isHanZi(char ch) / 判斷是否漢字return (ch = 0 x4E00 & ch = 0 x9FA5);/* 根據(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.toString(ch).getBytes(GB2312);if (buffer.length != 2) / 正常情況下buffer應(yīng)該是兩個(gè)字節(jié)，否則說明ch不屬于GB2312編碼，故返回?，