齊寧:搜索引擎知識 網頁查重技術

對於搜索引擎來說,重復的網頁內容是非常有害的。重復網頁的存在意味著這些網頁就要被搜索引擎多處理一次。更有害的是搜索引擎的索引制作中可能會在索引庫裡索引兩份相同的網頁。當有人查詢時,在搜索結果中就會出現重復的網頁鏈接。所以無論是從搜索體驗還是系統效率檢索質量來說這些重負網頁都是有害處的。

網頁查重技術起源於復制檢測技術,即判斷一個文件內容是否存在抄襲、復制另外一個或多個文件的技術。

1993年Arizona大學的Manber(Google現副總裁、工程師)推出瞭一個sif工具,尋找相似文件。1995年Stanford大學的Brin(Sergey Brin,Google創始人之一)和Garcia-Molina等人在數字圖書觀工程中首次提出文本復制檢測機制COPS(Copy Protection System)系統與相應算法[Sergey Brin et al 1995]。之後這種檢測重復技術被應用到搜索引擎中,基本的核心技術既比較相似。

網頁和簡單的文檔不同,網頁的特殊屬性具有內容和格式等標記,因此在內容和格式上的相同相似構成瞭4種網頁相似的類型。
1、兩個頁面內容格式完全相同。
2、兩個頁面內容相同,但格式不同。
3、兩個頁面部分內容相同並且格式相同。
4、兩個頁面部分重要相同但格式不同。

實現方法:

網頁查重,首先將網頁整理成為一個具有標題和正文的文檔,來方便查重。所以網頁查重又叫文檔查重。文檔查重一般被分為三個步驟,一、特征抽取。二、相似度計算和評價。三、消重。

1.特征抽取
我們在判斷相似物的時候,一般是才能用不變的特征進行對比,文件查重第一步也是進行特征抽取。也就是將文檔內容分解,由若幹組成文檔的特征集合表示,這一步是為瞭方面後面的特征比較計算相似度。
特征抽取有很多方法,我們這裡主要說兩種比較經典的算法,I-Match算法、Shingle算法。
I-Match算法是不依賴於完全的信息分析,而是使用數據集合的統計特征來抽取文檔的主要特征,將非主要特征拋棄。
Shingle算法通過抽取多個特征詞匯,比較兩個特征集合的相似程度實現文檔查重。

2.相似度計算和評價
特征抽取完畢後,就需要進行特征對比,因網頁查重第二步就是相似度計算和評價。
I-Match算法的特征隻有一個,當輸入一篇文檔,根據詞匯的IDF值(逆文本頻率指數,Inverse document frequency縮寫為IDF)過濾出一些關鍵特征,即一篇文章中特別高和特別低頻的詞匯往往不能反應這篇文章的本質。因此通過文檔中去掉高頻和低頻詞匯,並且計算出這篇文檔的唯一的Hash值(Hash簡單的說就是把數據值映射為地址。把數據值作為輸入,經計算後即可得到地址值。),那些Hash值相同的文檔就是重復的。

Shingle算法是抽取多個特征進行比較,所以處理起來比較復雜一些,比較的方法是完全一致的Shingle個數。然後除以兩個文檔的Shingle總數減去一致的Shingle個數,這種方法計算出的數值為Jaccard 系數,它可以判斷集合的相似度。Jaccard 系數的計算方法集合的交集除以集合的並集。

3.消重
對於刪除重復內容,搜索引擎考慮到眾多收錄因素,所以使用瞭最簡單的最實用的方法。先被爬蟲抓取的頁面同時很大程度也保證瞭優先保留原創網頁。

網頁查重工作是系統中不可缺少的,刪除瞭重復的頁面,所以搜索引擎的其他環節也會減少很多不必要的麻煩,節省瞭索引存儲空間、減少瞭查詢成本、提高瞭PageRank計算效率。方便瞭搜索引擎用戶。

本文首發 齊寧網絡營銷策劃 轉載請註明作者信息。謝謝!
齊寧 MSN: i@qining.org