[[177348]]

緣起：

(1)原創(chuàng)不易，互聯(lián)網(wǎng)抄襲成風(fēng)，很多原創(chuàng)內(nèi)容在網(wǎng)上被抄來抄去，改來改去

(2)百度的網(wǎng)頁庫非常大，爬蟲如何判斷一個(gè)新網(wǎng)頁是否與網(wǎng)頁庫中已有的網(wǎng)頁重復(fù)呢?

這是本文要討論的問題(盡量用大家都能立刻明白的語言和示例表述)。

一、傳統(tǒng)簽名算法與文本完整性判斷

問題拋出：

(1)運(yùn)維上線一個(gè)bin文件，將文件分發(fā)到4臺(tái)線上機(jī)器上，如何判斷bin文件全部是一致的?

(2)用戶A將消息msg發(fā)送給用戶B，用戶B如何判斷收到的msg_t就是用戶A發(fā)送的msg?

思路：

一個(gè)字節(jié)一個(gè)字節(jié)的比對(duì)兩個(gè)大文件或者大網(wǎng)頁效率低，我們可以用一個(gè)簽名值(例如md5值)代表一個(gè)大文件，簽名值相同則認(rèn)為大文件相同(先不考慮沖突率)

回答：

(1)將bin文件取md5，將4臺(tái)線上機(jī)器上的bin文件也取md5，如果5個(gè)md5值相同，說明一致

(2)用戶A將msg以及消息的md5同時(shí)發(fā)送給用戶B，用戶B收到msg_t后也取md5，得到的值與用戶A發(fā)送過來的md5值如果相同，則說明msg_t與msg相同

結(jié)論：md5是一種簽名算法，常用來判斷數(shù)據(jù)的完整性與一致性

md5設(shè)計(jì)原則：兩個(gè)文本哪怕只有1個(gè)bit不同，其md5簽名值差別也會(huì)非常大，故它只適用于“完整性”check，不適用于“相似性”check。

新問題拋出：

有沒有一種簽名算法，如果文本非常相似，簽名值也非常相似呢?

二、文本相似性的簽名算法

上文提出的問題，可以用局部敏感哈希LSH(Locality Sensitive Hash)解決，局部敏感哈希是一類文本越相似，哈希值越相似的hash算法，有興趣的同學(xué)自行百度，這里分享一下minHash的思路。

問題的提出：什么是minHash?

回答：minHash是局部敏感哈希的一種，它常用來快速判定集合的相似性，也常用于檢測網(wǎng)頁的重復(fù)性，其思路為，用相同的規(guī)則抽取集合中的少部分元素代表整個(gè)集合，如果少部分元素的重合度很高，非常可能整個(gè)集合的重復(fù)度也很高。

舉例：待判定的集合為A{1, 7, 5, 9, 3, 11, 15, 13}

已有的集合為：

B{10, 8, 2, 4, 6, 0, 1, 16},

C{100, 700, 500, 900, 300, 1100, 1500,1300},

D{1, 3, 2, 4, 6, 5, 8, 7}

假設(shè)使用部分元素代替全體集合的規(guī)則為：集合內(nèi)元素進(jìn)行排序，取值最小的4個(gè)(這個(gè)過程有信息損失，我們可以認(rèn)為是一個(gè)hash過程)

處理結(jié)果為：

A{1, 3, 5, 7}

B{0, 1, 2, 4} => A與B有1個(gè)元素相同

C{100, 300, 500, 700} => A與C有0個(gè)元素相同

D{1, 2, 3, 4} => A與D有2個(gè)元素相同

判斷結(jié)論：我們認(rèn)為集合A與集合D是最相似的

這個(gè)例子有點(diǎn)2，但基本能說明整體思路，實(shí)際在執(zhí)行的過程中：

(1)我們可以使用更多的元素來代表集合，以提高準(zhǔn)確性(例如，將上例中的4個(gè)元素代表集合升級(jí)為8個(gè)元素代表集合)

(2)我們可以使用更多的hash函數(shù)來代表集合，以提高準(zhǔn)確性(例如，上例除了“排序后取值最小的4個(gè)元素代表集合”，還可以增加一個(gè)哈希函數(shù)“排序后取值***的4個(gè)元素代表集合”)

(3)minHash可以量化評(píng)判相似度，亦可以評(píng)判網(wǎng)頁是否重復(fù)(一個(gè)分類問題)，設(shè)定相似度閾值，高于閾值為重復(fù)，低于閾值為不重復(fù)

(4)實(shí)際排重過程中，網(wǎng)頁庫中的哈希值都可以提前計(jì)算，只有待判定的集合或者網(wǎng)頁的哈希值需要臨時(shí)計(jì)算

三、minHash與長文本重復(fù)度檢測有什么關(guān)系

目前看來沒什么關(guān)系，但如果我們能將每一個(gè)長文本用一個(gè)集合來表示，就能將長文本的相似度用minHash來解決了。

問題的提出：如何將長文本轉(zhuǎn)化為集合?

回答：我去，分詞不是就可以么

舉例：待判定的長文本為A{我是58沈劍，我來自58到家}

已有網(wǎng)頁庫集合為：

B{我是一只來自58的狼}

C{58到家，服務(wù)到家}

D{這事和我沒關(guān)系，我是湊數(shù)的}

使用分詞將上述文本集合化：

A{我，58，沈劍，來自，到家}

B{我，58，來自，狼}

C{58，服務(wù)，到家}

D{事，我，湊數(shù)，關(guān)系}

判斷結(jié)論：當(dāng)當(dāng)當(dāng)當(dāng)，轉(zhuǎn)化為集合后，可以快速判斷A與B的相似度***，當(dāng)然實(shí)際執(zhí)行過程中，除了分詞還得考慮詞頻，用這種方法對(duì)長文本進(jìn)行相似度檢測，準(zhǔn)確率非常高(文本越長越準(zhǔn))

四、還有沒有更有效的方法

使用上述方法進(jìn)行文本相似度檢測，需要進(jìn)行中文分詞，詞頻統(tǒng)計(jì)，哈希值計(jì)算，相似度計(jì)算，計(jì)算量微大。

然而，抄襲成風(fēng)，一字不改的風(fēng)氣，讓技術(shù)有了更廣闊的優(yōu)化空間，贊!

怎么優(yōu)化呢?

不再進(jìn)行分詞，而是進(jìn)行“分句”，用標(biāo)點(diǎn)符號(hào)把長文按照句子分開，使用N個(gè)句子集合(例如一篇文章中5條最長的句子作為簽名，注意，長句子比短句子更具有區(qū)分性)作為文章的簽名，在抄襲成風(fēng)的互聯(lián)網(wǎng)環(huán)境下，此法判斷網(wǎng)頁的重復(fù)度能大大降低工程復(fù)雜度，并且準(zhǔn)確度也異常的高。

五、結(jié)論

在抄襲成風(fēng)的互聯(lián)網(wǎng)環(huán)境下，采用“分句”的方式，用5條最長的網(wǎng)頁內(nèi)容作為網(wǎng)頁的簽名，能夠極大的降低排重系統(tǒng)復(fù)雜度，提高排重準(zhǔn)確率，不失為一種好的選擇。

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】