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