自己實現文本相似度算法（余弦定理） - 呼吸的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 - 開源中國社區