搜索引擎網(wǎng)頁(yè)去重算法分析
- 威海搜索引擎工作原理 威海搜索引擎工作原理
- 2598
相關(guān)統(tǒng)計(jì)數(shù)據(jù)表明：互聯(lián)網(wǎng)上近似重復(fù)的網(wǎng)頁(yè)的數(shù)量占網(wǎng)頁(yè)總數(shù)量的比例高達(dá)29%，完全相同的網(wǎng)頁(yè)大約占網(wǎng)頁(yè)總數(shù)量的22%.研究表明，在一個(gè)大型的信息采集系統(tǒng)中，30%的網(wǎng)頁(yè)是和另外70%的網(wǎng)頁(yè)完全重復(fù)或近似重復(fù)的。
即：互聯(lián)網(wǎng)的網(wǎng)頁(yè)中相當(dāng)高的比例的網(wǎng)頁(yè)內(nèi)容是近似相同或完全相同的!
搜索爬蟲抓取會(huì)產(chǎn)生網(wǎng)頁(yè)重復(fù)的類型：
1.多個(gè)URL地址指向同一網(wǎng)頁(yè)以及鏡像站點(diǎn)
如：www.sina.com 和www.sina.com.cn
指向同一個(gè)站點(diǎn)。
2. 網(wǎng)頁(yè)內(nèi)容重復(fù)或近似重復(fù)
如抄襲、轉(zhuǎn)摘的內(nèi)容，垃圾信息等
網(wǎng)頁(yè)內(nèi)容近似重復(fù)檢測(cè)的兩種應(yīng)用場(chǎng)合：
一：在用戶搜索階段
目標(biāo)是根據(jù)與用戶給定的查詢?cè)~找到已有索引列表中近似重復(fù)的文檔，并排序輸出。
二：爬蟲抓取發(fā)現(xiàn)階段
對(duì)一個(gè)新的網(wǎng)頁(yè)，爬蟲程序通過網(wǎng)頁(yè)去重算法，最終決定是否對(duì)其索引。
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第1張
搜索引擎架構(gòu)
近似重復(fù)網(wǎng)頁(yè)類型，根據(jù)文章內(nèi)容和網(wǎng)頁(yè)布局格式的組合分為4種形式：
一：兩篇文檔在內(nèi)容和布局格式上毫無區(qū)別，則這種重復(fù)稱為完全重復(fù)頁(yè)面。
二：兩篇文檔內(nèi)容相同，但布局格式不同，則這種重復(fù)稱為內(nèi)容重復(fù)頁(yè)面。
三：兩篇文檔有部分重要的內(nèi)容相同，并且布局格式相同，則這種重復(fù)稱為布局重復(fù)頁(yè)面。
四：兩篇文檔有部分重要內(nèi)容相同，但布局格式不同，則這種重復(fù)稱為部分重復(fù)頁(yè)面。
重復(fù)網(wǎng)頁(yè)對(duì)搜索引擎的不利影響：
正常情況下，非常相似的網(wǎng)頁(yè)內(nèi)容不能或只能給用戶提供少量的新信息，但在對(duì)爬蟲進(jìn)行抓取、索引和用戶搜索 會(huì)消耗大量的服務(wù)器資源。
重復(fù)網(wǎng)頁(yè)對(duì)搜索引擎的好處：
如果某個(gè)網(wǎng)頁(yè)重復(fù)性很高，往往是其內(nèi)容比較比較受歡迎的一種體現(xiàn)，也預(yù)示著該網(wǎng)頁(yè)相對(duì)比較重要。應(yīng)予以優(yōu)先收錄。當(dāng)用戶搜索時(shí)，在輸出結(jié)果排序時(shí)，也應(yīng)給與較高的權(quán)重。
重復(fù)文檔的處理方式：
1.刪除
2.將重復(fù)文檔分組
近似重復(fù)網(wǎng)頁(yè)舉例：
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第2張
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第3張
近似重復(fù)網(wǎng)頁(yè)舉例
搜索引擎近似重復(fù)檢測(cè)流程：
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第4張
搜索引擎近似重復(fù)檢測(cè)流程
通用網(wǎng)頁(yè)去重算法框架：
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第5張
通用網(wǎng)頁(yè)去重框架
SimHash文檔指紋計(jì)算方法
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第6張
SimHash文檔指紋計(jì)算方法
說明：
1)從文檔中提取具有權(quán)值的 特征集合來表示文檔。如：假設(shè)特征都是由詞組成的，詞的權(quán)值由詞頻TF 來確定。
2)對(duì)每一個(gè)詞，通過哈希算法生成N位(通常情況是64位或更多)的二進(jìn)制數(shù)值,如上圖，以生成8位的二進(jìn)制值為例。每個(gè)詞都對(duì)應(yīng)各自不同的二進(jìn)制值。
3)在N維(上圖為8維)的向量V中，分別對(duì)每維向量進(jìn)行計(jì)算。如果詞相應(yīng)的比特位的二進(jìn)制數(shù)值為1，則對(duì)其特征權(quán)值進(jìn)行加法運(yùn)算;如果比特位數(shù)值為0，則進(jìn)行減法運(yùn)算，通過這種方式對(duì)向量進(jìn)行更新。
4)當(dāng)所有的詞都按照上述處理完畢后，如果向量V中第i維是正數(shù)，則將N位的指紋中第i位設(shè)置為1，否則為0。
Jacccard相似性計(jì)算方法：
搜索引擎網(wǎng)頁(yè)去重算法分析 搜索引擎 好文分享 第7張
Jacccard相似性計(jì)算方法
如上圖，A和B代表2個(gè)集合，集合C代表集合A和B相同的部分。 A集合包含5個(gè)元素，B集合包含4個(gè)元素，而兩者相同的元素有2個(gè)，即集合C的大小是2. Jaccard計(jì)算兩個(gè)集合相同的元素占總元素的比例。
如圖中，集合A和集合B共有7個(gè)不同的元素，相同元素個(gè)數(shù)2個(gè)，所以集合A和集合B的相似性為：2/7
在實(shí)際應(yīng)用中，集合A 和 集合B 的特征都會(huì)經(jīng)過哈希計(jì)算，轉(zhuǎn)化成N位(64位甚至更多)的二進(jìn)制數(shù)值，從而將集合A和B的相似性比較轉(zhuǎn)化為二進(jìn)制數(shù)值的比較，稱為“海明距離”的比較。兩個(gè)位數(shù)相同(如均為64位)相同位置上不同的二進(jìn)制數(shù)值的個(gè)數(shù)稱為“海明距離”。
對(duì)給定的文檔A，假設(shè)經(jīng)過特征抽取–哈希指紋運(yùn)算后的二進(jìn)制數(shù)值是：1 0 0 0 0 0 1 0
對(duì)給定的文檔B, 假設(shè)經(jīng)過特征抽取—哈希指紋運(yùn)算后的二進(jìn)制數(shù)值是：0 0 1 0 0 0 0 1
經(jīng)過比較，文檔A 和 B的 第1位、第3位、第7位、第8位四個(gè)位置的數(shù)值不同，即海明距離為4. 兩個(gè)文檔的二進(jìn)制位數(shù)不同的個(gè)數(shù)越多，海明距離越大。海明距離越大，說明兩個(gè)文檔不相似性越大，反之，則越小。
不同搜索引擎可能會(huì)以不同的海明距離值 來判斷兩個(gè)網(wǎng)頁(yè)內(nèi)容是否近似重復(fù)。相關(guān)分析認(rèn)為，一般情況下，對(duì)一個(gè)64位的二進(jìn)制數(shù)值來說，將海明距離<=3作為判斷是否近似重復(fù)的標(biāo)準(zhǔn)比較合理.
作者：AlbertTan
來源：盧松松博客
