自己實現文本相似度算法(余弦定理) - 呼吸的Java - 開源中國社區
自己實現文本相似度算法(余弦定理)
52人收藏此文章, 我要收藏 發表于9個月前(2012-03-04 16:59) , 已有5592次閱讀 ,共6個評論
?????? 最近由于工作項目,需要判斷兩個txt文本是否相似,于是開始在網上找資料研究,因為在程序中會把文本轉換成String再做比較,所以最開始找到了這篇關于 距離編輯算法 Blog寫的非常好,受益匪淺。
?????? 于是我決定把它用到項目中,來判斷兩個文本的相似度。但后來實際操作發現有一些問題:直接說就是查詢一本書中的相似章節花了我7、8分鐘;這是我不能接受……
?????? 于是停下來仔細分析發現,這種算法在此項目中不是特別適用,由于要判斷一本書中是否有相同章節,所以每兩個章節之間都要比較,若一本書書有x章的話,這里需對比x(x-1)/2次;而此算法采用矩陣的方式,計算兩個字符串之間的變化步驟,會遍歷兩個文本中的每一個字符兩兩比較,可以推斷出時間復雜度至少為 document1.length × document2.length,我所比較的章節字數平均在幾千~一萬字;這樣計算實在要了老命。
?????? 想到Lucene中的評分機制,也是算一個相似度的問題,不過它采用的是計算向量間的夾角(余弦公式),在google黑板報中的:數學之美(余弦定理和新聞分類) 也有說明,可以通過余弦定理來判斷相似度;于是決定自己動手試試。
?????? 首相選擇向量的模型:在以字為向量還是以詞為向量的問題上,糾結了一會;后來還是覺得用字,雖然詞更為準確,但分詞卻需要增加額外的復雜度,并且此項目要求速度,準確率可以放低,于是還是選擇字為向量。
?????? 然后每個字在章節中出現的次數,便是以此字向量的值。現在我們假設:
?????? 章節1中出現的字為:Z1c1,Z1c2,Z1c3,Z1c4……Z1cn;它們在章節中的個數為:Z1n1,Z1n2,Z1n3……Z1nm;
?????? 章節2中出現的字為:Z2c1,Z2c2,Z2c3,Z2c4……Z2cn;它們在章節中的個數為:Z2n1,Z2n2,Z2n3……Z2nm;
?????? 其中,Z1c1和Z2c1表示兩個文本中同一個字,Z1n1和Z2n1是它們分別對應的個數,
?????? 最后我們的相似度可以這么計算:
?????? 程序實現如下:(若有可優化或更好的實現請不吝賜教)
view source
print?
01??? public class CosineSimilarAlgorithm {
02??? ??? public static double getSimilarity(String doc1, String doc2) {
03??? ??????? if (doc1 != null && doc1.trim().length() > 0 && doc2 != null
04??? ??????????????? && doc2.trim().length() > 0) {
05??? ????????????
06??? ??????????? Map<Integer, int[]> AlgorithmMap = new HashMap<Integer, int[]>();
07??? ????????????
08??? ??????????? //將兩個字符串中的中文字符以及出現的總數封裝到,AlgorithmMap中
09??? ??????????? for (int i = 0; i < doc1.length(); i++) {
10??? ??????????????? char d1 = doc1.charAt(i);
11??? ??????????????? if(isHanZi(d1)){
12??? ??????????????????? int charIndex = getGB2312Id(d1);
13??? ??????????????????? if(charIndex != -1){
14??? ??????????????????????? int[] fq = AlgorithmMap.get(charIndex);
15??? ??????????????????????? if(fq != null && fq.length == 2){
16??? ??????????????????????????? fq[0]++;
17??? ??????????????????????? }else {
18??? ??????????????????????????? fq = new int[2];
19??? ??????????????????????????? fq[0] = 1;
20??? ??????????????????????????? fq[1] = 0;
21??? ??????????????????????????? AlgorithmMap.put(charIndex, fq);
22??? ??????????????????????? }
23??? ??????????????????? }
24??? ??????????????? }
25??? ??????????? }
26??? ?
27??? ??????????? for (int i = 0; i < doc2.length(); i++) {
28??? ??????????????? char d2 = doc2.charAt(i);
29??? ??????????????? if(isHanZi(d2)){
30??? ??????????????????? int charIndex = getGB2312Id(d2);
31??? ??????????????????? if(charIndex != -1){
32??? ??????????????????????? int[] fq = AlgorithmMap.get(charIndex);
33??? ??????????????????????? if(fq != null && fq.length == 2){
34??? ??????????????????????????? fq[1]++;
35??? ??????????????????????? }else {
36??? ??????????????????????????? fq = new int[2];
37??? ??????????????????????????? fq[0] = 0;
38??? ??????????????????????????? fq[1] = 1;
39??? ??????????????????????????? AlgorithmMap.put(charIndex, fq);
40??? ??????????????????????? }
41??? ??????????????????? }
42??? ??????????????? }
43??? ??????????? }
44??? ????????????
45??? ??????????? Iterator<Integer> iterator = AlgorithmMap.keySet().iterator();
46??? ??????????? double sqdoc1 = 0;
47??? ??????????? double sqdoc2 = 0;
48??? ??????????? double denominator = 0;
49??? ??????????? while(iterator.hasNext()){
50??? ??????????????? int[] c = AlgorithmMap.get(iterator.next());
51??? ??????????????? denominator += c[0]*c[1];
52??? ??????????????? sqdoc1 += c[0]*c[0];
53??? ??????????????? sqdoc2 += c[1]*c[1];
54??? ??????????? }
55??? ????????????
56??? ??????????? return denominator / Math.sqrt(sqdoc1*sqdoc2);
57??? ??????? } else {
58??? ??????????? throw new NullPointerException(
59??? ??????????????????? " the Document is null or have not cahrs!!");
60??? ??????? }
61??? ??? }
62??? ?
63??? ??? public static boolean isHanZi(char ch) {
64??? ??????? // 判斷是否漢字
65??? ??????? return (ch >= 0x4E00 && ch <= 0x9FA5);
66??? ?
67??? ??? }
68??? ?
69??? ??? /**
70??? ???? * 根據輸入的Unicode字符,獲取它的GB2312編碼或者ascii編碼,
71??? ???? *
72??? ???? * @param ch
73??? ???? *??????????? 輸入的GB2312中文字符或者ASCII字符(128個)
74??? ???? * @return ch在GB2312中的位置,-1表示該字符不認識
75??? ???? */
76??? ??? public static short getGB2312Id(char ch) {
77??? ??????? try {
78??? ??????????? byte[] buffer = Character.toString(ch).getBytes("GB2312");
79??? ??????????? if (buffer.length != 2) {
80??? ??????????????? // 正常情況下buffer應該是兩個字節,否則說明ch不屬于GB2312編碼,故返回'?',此時說明不認識該字符
81??? ??????????????? return -1;
82??? ??????????? }
83??? ??????????? int b0 = (int) (buffer[0] & 0x0FF) - 161; // 編碼從A1開始,因此減去0xA1=161
84??? ??????????? int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一個字符和最后一個字符沒有漢字,因此每個區只收16*6-2=94個漢字
85??? ??????????? return (short) (b0 * 94 + b1);
86??? ??????? } catch (UnsupportedEncodingException e) {
87??? ??????????? e.printStackTrace();
88??? ??????? }
89??? ??????? return -1;
90??? ??? }
91??? }
?????? 程序中做了兩小的改進,以加快效率:
?????? 1. 只將漢字作為向量,其他的如標點,數字等符號不處理;2. 在HashMap中存放漢字和其在文本中對于的個數時,先將單個漢字通過GB2312編碼轉換成數字,再存放。
?????? 最后寫了個測試,根據兩種不同的算法對比下時間,下面是測試結果:
?????? 余弦定理算法:doc1 與 doc2 相似度為:0.9954971, 耗時:22mm
?????? 距離編輯算法:doc1 與 doc2 相似度為:0.99425095, 耗時:322mm
?????? 可見效率有明顯提高,算法復雜度大致為:document1.length + document2.length。
?????? 原創blog,轉載請注明http://my.oschina.net/BreathL/blog/42477
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
