亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

自己實現文本相似度算法(余弦定理) - 呼吸的J

系統 2260 0

自己實現文本相似度算法(余弦定理) - 呼吸的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

自己實現文本相似度算法(余弦定理) - 呼吸的Java - 開源中國社區


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 91视频这里只有精品 | 亚洲视频国产视频 | 亚洲欧美综合国产精品一区 | 日本一级~片免费永久 | 四虎成人免费网站在线 | 国产农村妇女一级毛片 | 美女久久 | 大伊香蕉精品视频在线天堂 | 久久99国产综合色 | 黄色毛片免费观看 | 黄色aaa级片| 日本一区二区三区在线观看 | 一级毛片不卡免费看老司机 | 欧美一级看片a免费观看 | 五月婷婷亚洲 | 亚洲精品动漫3d一区二区 | 日韩日韩| 91精品国产露脸在线 | 国产精品亚洲综合色拍 | 不卡免费播放 | 日韩国产欧美一区二区三区 | 亚洲天堂欧美 | 色站综合 | 日本高清专区一区二无线 | 亚洲精品第五页中文字幕 | 成人看的午夜免费毛片 | 亚洲成人日韩 | 一本到视频在线观看 | 波多野结衣精品一区二区三区 | 亚洲日本欧美日韩高观看 | 99久久精品免费精品国产 | 亚洲黄色激情视频 | 在线播放日本爽快片 | 色偷偷久久| 91麻豆精品一二三区在线 | 国产精品99精品久久免费 | 亚洲综合成人在线 | 爱爱免费 | 国产精品免费一区二区区 | 狠狠色噜噜狠狠狠狠2021天天 | 中文字幕在线观看免费视频 |