最近由于工作項目，需要判斷兩個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是它們分别對應的個數，
最後我們的相似度可以這麼計算：
1 public class CosineSimilarAlgorithm {
2 public static double getSimilarity(String doc1, String doc2) {
3 if (doc1 != null && doc1.trim().length() > 0 && doc2 != null
4 && doc2.trim().length() > 0) {
5
6 Map<Integer, int[]> AlgorithmMap = new HashMap<Integer, int[]>();
7
8 //将兩個字元串中的中文字元以及出現的總數封裝到，AlgorithmMap中
9 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![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)