自己實(shí)現(xiàn)文本相似度算法（余弦定理） - 呼吸的Java - 開源中國社區(qū)

自己實(shí)現(xiàn)文本相似度算法（余弦定理）
52人收藏此文章, 我要收藏 發(fā)表于9個(gè)月前(2012-03-04 16:59) , 已有5592次閱讀 ，共6個(gè)評(píng)論

?????? 最近由于工作項(xiàng)目，需要判斷兩個(gè)txt文本是否相似，于是開始在網(wǎng)上找資料研究，因?yàn)樵诔绦蛑袝?huì)把文本轉(zhuǎn)換成String再做比較，所以最開始找到了這篇關(guān)于 距離編輯算法 Blog寫的非常好，受益匪淺。

?????? 于是我決定把它用到項(xiàng)目中，來判斷兩個(gè)文本的相似度。但后來實(shí)際操作發(fā)現(xiàn)有一些問題：直接說就是查詢一本書中的相似章節(jié)花了我7、8分鐘；這是我不能接受……

?????? 于是停下來仔細(xì)分析發(fā)現(xiàn)，這種算法在此項(xiàng)目中不是特別適用，由于要判斷一本書中是否有相同章節(jié)，所以每?jī)蓚€(gè)章節(jié)之間都要比較，若一本書書有x章的話，這里需對(duì)比x(x-1)/2次；而此算法采用矩陣的方式，計(jì)算兩個(gè)字符串之間的變化步驟，會(huì)遍歷兩個(gè)文本中的每一個(gè)字符兩兩比較，可以推斷出時(shí)間復(fù)雜度至少為 document1.length × document2.length，我所比較的章節(jié)字?jǐn)?shù)平均在幾千～一萬字；這樣計(jì)算實(shí)在要了老命。

?????? 想到Lucene中的評(píng)分機(jī)制，也是算一個(gè)相似度的問題，不過它采用的是計(jì)算向量間的夾角（余弦公式），在google黑板報(bào)中的：數(shù)學(xué)之美（余弦定理和新聞分類） 也有說明，可以通過余弦定理來判斷相似度；于是決定自己動(dòng)手試試。

?????? 首相選擇向量的模型：在以字為向量還是以詞為向量的問題上，糾結(jié)了一會(huì)；后來還是覺得用字，雖然詞更為準(zhǔn)確，但分詞卻需要增加額外的復(fù)雜度，并且此項(xiàng)目要求速度，準(zhǔn)確率可以放低，于是還是選擇字為向量。

?????? 然后每個(gè)字在章節(jié)中出現(xiàn)的次數(shù)，便是以此字向量的值。現(xiàn)在我們假設(shè)：

?????? 章節(jié)1中出現(xiàn)的字為：Z1c1,Z1c2,Z1c3,Z1c4……Z1cn；它們?cè)谡鹿?jié)中的個(gè)數(shù)為：Z1n1,Z1n2,Z1n3……Z1nm；

?????? 章節(jié)2中出現(xiàn)的字為：Z2c1,Z2c2,Z2c3,Z2c4……Z2cn；它們?cè)谡鹿?jié)中的個(gè)數(shù)為：Z2n1,Z2n2,Z2n3……Z2nm；

?????? 其中，Z1c1和Z2c1表示兩個(gè)文本中同一個(gè)字，Z1n1和Z2n1是它們分別對(duì)應(yīng)的個(gè)數(shù)，

?????? 最后我們的相似度可以這么計(jì)算：

?????? 程序?qū)崿F(xiàn)如下：（若有可優(yōu)化或更好的實(shí)現(xiàn)請(qǐng)不吝賜教）

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??? ??????????? //將兩個(gè)字符串中的中文字符以及出現(xiàn)的總數(shù)封裝到，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??? ???? * 根據(jù)輸入的Unicode字符，獲取它的GB2312編碼或者ascii編碼，
71??? ???? *
72??? ???? * @param ch
73??? ???? *??????????? 輸入的GB2312中文字符或者ASCII字符(128個(gè))
74??? ???? * @return ch在GB2312中的位置，-1表示該字符不認(rèn)識(shí)
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應(yīng)該是兩個(gè)字節(jié)，否則說明ch不屬于GB2312編碼，故返回'?'，此時(shí)說明不認(rèn)識(shí)該字符
81??? ??????????????? return -1;
82??? ??????????? }
83??? ??????????? int b0 = (int) (buffer[0] & 0x0FF) - 161; // 編碼從A1開始，因此減去0xA1=161
84??? ??????????? int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一個(gè)字符和最后一個(gè)字符沒有漢字，因此每個(gè)區(qū)只收16*6-2=94個(gè)漢字
85??? ??????????? return (short) (b0 * 94 + b1);
86??? ??????? } catch (UnsupportedEncodingException e) {
87??? ??????????? e.printStackTrace();
88??? ??????? }
89??? ??????? return -1;
90??? ??? }
91??? }

?????? 程序中做了兩小的改進(jìn)，以加快效率：

?????? 1. 只將漢字作為向量，其他的如標(biāo)點(diǎn)，數(shù)字等符號(hào)不處理；2. 在HashMap中存放漢字和其在文本中對(duì)于的個(gè)數(shù)時(shí)，先將單個(gè)漢字通過GB2312編碼轉(zhuǎn)換成數(shù)字，再存放。

?????? 最后寫了個(gè)測(cè)試，根據(jù)兩種不同的算法對(duì)比下時(shí)間，下面是測(cè)試結(jié)果：

?????? 余弦定理算法：doc1 與 doc2 相似度為：0.9954971, 耗時(shí)：22mm

?????? 距離編輯算法：doc1 與 doc2 相似度為：0.99425095, 耗時(shí)：322mm

?????? 可見效率有明顯提高，算法復(fù)雜度大致為：document1.length + document2.length。

?????? 原創(chuàng)blog，轉(zhuǎn)載請(qǐng)注明http://my.oschina.net/BreathL/blog/42477

自己實(shí)現(xiàn)文本相似度算法（余弦定理） - 呼吸的Java - 開源中國社區(qū)