利用余弦定理實現文本相似度算法
由于工作項目，需要判斷兩個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是它們分別對應的個數，
最后我們的相似度可以這么計算：
程序實現如下：
public class CosineSimilarAlgorithm {
public static double getSimilarity(String doc1, String doc2) {
if (doc1 != null && doc1.trim().length() > 0 && doc2 != null
&& doc2.trim().length() > 0) {
Map<Integer, int[]> AlgorithmMap = new HashMap<Integer, int[]>();
//將兩個字符串中的中文字符以及出現的總數封裝到，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){
fq[0]++;
}else {
fq = new int[2];
fq[0] = 1;
fq[1] = 0;
AlgorithmMap.put(charIndex, fq);
}
}
}
}
for (int i = 0; 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){
fq[1]++;
}else {
fq = new int[2];
fq[0] = 0;
fq[1] = 1;
AlgorithmMap.put(charIndex, fq);
}
}
}
}
Iterator<Integer> iterator = AlgorithmMap.keySet().iterator();
double sqdoc1 = 0;
double sqdoc2 = 0;
double denominator = 0;
while(iterator.hasNext()){
int[] c = AlgorithmMap.get(iterator.next());
denominator += c[0]*c[1];
sqdoc1 += c[0]*c[0];
sqdoc2 += c[1]*c[1];
}
return denominator / Math.sqrt(sqdoc1*sqdoc2);
} else {
throw new NullPointerException(
" the Document is null or have not cahrs!!");
}
}
public static boolean isHanZi(char ch) {
// 判斷是否漢字
return (ch >= 0x4E00 && ch <= 0x9FA5);
}
/**
* 根據輸入的Unicode字符，獲取它的GB2312編碼或者ascii編碼，
*
* @param ch
* 輸入的GB2312中文字符或者ASCII字符(128個)
* @return ch在GB2312中的位置，-1表示該字符不認識
*/
public static short getGB2312Id(char ch) {
try {
byte[] buffer = Character.toString(ch).getBytes("GB2312");
if (buffer.length != 2) {
// 正常情況下buffer應該是兩個字節，否則說明ch不屬于GB2312編碼，故返回'?'，此時說明不認識該字符
return -1;
}
int b0 = (int) (buffer[0] & 0x0FF) - 161; // 編碼從A1開始，因此減去0xA1=161
int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一個字符和最后一個字符沒有漢字，因此每個區只收16*6-2=94個漢字
return (short) (b0 * 94 + b1);
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
return -1;
}
}
程序中做了兩小的改進，以加快效率：
1. 只將漢字作為向量，其他的如標點，數字等符號不處理；2. 在HashMap中存放漢字和其在文本中對于的個數時，先將單個漢字通過GB2312編碼轉換成數字，再存放。
最后寫了個測試，根據兩種不同的算法對比下時間，下面是測試結果：
余弦定理算法：doc1 與 doc2 相似度為：0.9954971, 耗時：22mm
距離編輯算法：doc1 與 doc2 相似度為：0.99425095, 耗時：322mm
可見效率有明顯提高，算法復雜度大致為：document1.length + document2.length。
原文地址：http://my.oschina.net/BreathL/blog/42477