場(chǎng)景
這是我在2015年3月份做的畢業(yè)設(shè)計(jì)，當(dāng)時(shí)在《數(shù)學(xué)之美》上看到這個(gè)用余弦定理計(jì)算相似度的算法，于是想著可以用它來(lái)計(jì)算兩篇文章的相似度，因?yàn)槲野l(fā)現(xiàn)好多同學(xué)寫(xiě)論文直接上百度復(fù)制粘貼，其實(shí)有時(shí)候我也是_，于是我想寫(xiě)個(gè)程序能夠判斷同學(xué)的文章是不是從百度抄來(lái)的，抄了百分之幾，于是就做了這個(gè)畢業(yè)設(shè)計(jì)。最后拿到了學(xué)校的優(yōu)秀畢業(yè)設(shè)計(jì)。
整個(gè)流程：
- 獲得學(xué)生的論文，包含標(biāo)題和內(nèi)容兩個(gè)部分。標(biāo)題為關(guān)鍵字，構(gòu)造百度搜索的URL，然后去抓取前 n 頁(yè)的網(wǎng)頁(yè)內(nèi)容。提取出漢字。
- 對(duì)漢字進(jìn)行過(guò)濾，去掉標(biāo)點(diǎn)，虛詞等等，再進(jìn)行中文分詞。
- 拿下載的文章和學(xué)生的文章，一篇一篇的計(jì)算相似度，找出相似度最高的前幾篇，超過(guò)一個(gè)閾值，比如60%，就認(rèn)為是抄襲了。
實(shí)現(xiàn)細(xì)節(jié)：
- 文本爬蟲(chóng)，多線程抓取網(wǎng)頁(yè)內(nèi)容，把網(wǎng)上的文章下載到緩沖區(qū)，一個(gè)線程把緩沖區(qū)寫(xiě)到磁盤，其實(shí)就是多個(gè)生產(chǎn)者，一個(gè)消費(fèi)者的模型。
- 中文分詞，看了一下結(jié)巴分詞，最后還是自己實(shí)現(xiàn)了一個(gè)最大正向匹配的分詞算法，下載了一個(gè)包含22萬(wàn)個(gè)常用和專業(yè)詞的字典。
- 計(jì)算兩篇文章的相似度，這個(gè)是本文下面重點(diǎn)要說(shuō)的。
相似度計(jì)算
由上面的過(guò)程，我把一篇文章切成一個(gè)一個(gè)的詞了，像這樣
我正在寫(xiě)代碼
中文分詞后
我 / 正在 / 寫(xiě) / 代碼
然后我有一個(gè)包含 22 萬(wàn)個(gè)詞語(yǔ)的字典，它的結(jié)構(gòu)像這樣，按拼音首字母排序（假設(shè)啊，數(shù)據(jù)都是假設(shè)的）
| 唯一index | 詞語(yǔ) |
|---|---|
| 哎 | 0 |
| 愛(ài)情 | 1 |
| 愛(ài)人 | 2 |
| ... | ... |
| 我 | 30 |
| 代碼 | 50 |
| 寫(xiě) | 70 |
| ... | ... |
| 正在 | 99 |
| ... | ... |
| 作業(yè) | 22000 |
在字典里面分別查找 {"我", "正在", "寫(xiě)", "代碼"} 對(duì)應(yīng)的 index
查找前
我 / 正在 / 寫(xiě) / 代碼
查找后變成了
30 / 99 / 70 / 50
詞典有22萬(wàn)個(gè)詞，我開(kāi)一個(gè)長(zhǎng)度為22萬(wàn)的數(shù)組array，記錄詞頻
array[30] = 1 // 表示“我”出現(xiàn)了1次，出現(xiàn)了100次就賦值100
array[99] = 1
array[70] = 1
array[50] = 1
其實(shí)有很多地方是 0 的，用稀疏數(shù)組保存省空間，轉(zhuǎn)換后變成
array = {0, 0, 0, 0, 0, 0, 0, ... 0, 1, 0, ..., 0, 1, 0, ...0}
array 長(zhǎng)度 22000
{我正在寫(xiě)代碼} == {0, 0, 0, 0, 0, ..., 0, 1, 0, ..., 0}
到此，一篇文章就被轉(zhuǎn)化成了一個(gè)維度是22000的向量了，儲(chǔ)存在 array 中。
余弦定理
應(yīng)該是高中的數(shù)學(xué)書(shū)上講過(guò)余弦定理（其實(shí)我也忘的差不多了_），書(shū)上有這個(gè)式子
2篇文章就是2個(gè)向量，2個(gè)向量可以計(jì)算夾角來(lái)判斷相似度。計(jì)算文章相似度就可以轉(zhuǎn)化為計(jì)算兩個(gè)N維向量的夾角。
如果兩個(gè)向量夾角很小，cos值接近1，說(shuō)明他們很相似。
如果兩個(gè)向量夾角是90度，cos值為0，說(shuō)明他們不相似，是正交的。
如果 cos 為 1，說(shuō)明兩篇文章的詞頻是一模一樣的，即出現(xiàn)了一樣的詞語(yǔ)，但語(yǔ)序可能不一樣。
如果 cos 為 0，說(shuō)明兩篇文章沒(méi)有一樣詞語(yǔ)，是正交的，一個(gè)相同的詞都沒(méi)有。
這樣就可以判斷兩篇文章有多相似了，可以得出一個(gè)[-1, 1]之間的值，來(lái)判斷是否抄襲，改變語(yǔ)序，調(diào)換段落也是沒(méi)用的_。
