I-Match

算法簡介

網頁查重算法是搜尋引擎判斷文章原創的一個重要手段。充分了解其算法有助於我們更好地使我們的文章看上去是“原創”的。其中I-MATCH算法[1]就是其中的一種。

算法的框架

1. 獲取文檔（或者是主體內容）

這個可以理解為直接抓取整個HTML頁面，除了用戶所見的文字以外，還有大量HTML格式標籤、JS等程式無法用於排名的內容。

2. 將文檔分解成token流，移除格式化的標籤

這個就是從HTML檔案中提取出去除標籤、程式的可用用於排名處理的網頁文字內容。如下：　<h2 class="post-title">　武漢seo:關於SEO平衡性的一腔犬吠</a></h2>

除去HTML代碼後就只有這么一行:　武漢seo:關於SEO平衡性的一腔犬吠

當然也可能會提取一下如METAT、ALT，連結錨文字等文字

3. 使用term的閾值（idf），保留有意義的tokens

這個的意思就是去除掉上述文字的一些高頻詞，如"的"，“地”，“得”之類的助詞，“阿”、“哈”，“呀”的感吧詞，還有“從在”“關於”“卻”之類的副詞和低頻詞，從而保留一些中頻有意義的詞。

4. 插入tokens到升序排列的排序樹中　將這些標籤排入到一個詞組的從低到高的頻率,放入SE的排列樹中。

5. 對每一個token，相加得到一個hash值，直到文檔結束為止　HASH值是根據檔案的內容的數據通過邏輯運算得到的數值，也就是上述標籤tokenS的值。

6. 將元組（doc_id,SHA hash) 插入到某一詞典中，如果詞典有衝突，這兩個文檔相似。

算法舉例

舉例：這裡有兩段網頁文字：　1.中國足球隊在米盧的率領下首次獲得世界盃決賽階段的比賽資格，新浪體育播報 。　2.米盧率領中國足球隊員首次殺入世界盃決賽階段，搜狐體育播報。　文檔(一)中　去掉高頻：中國，在，的，獲得，比賽，資格，新浪，體育，播報　去掉低頻：米盧　則剩下中頻詞有：足球隊，率領，首次，世界盃，決賽，階段　文檔(二)中　去掉高頻：中國，搜狐，體育，播報　去掉低頻：米盧，殺入　則剩下中頻詞有：率領，足球隊，首次，世界盃，決賽 ，階段　兩者是一模一樣，這就是相似性的存在。