用於網頁消重的方法和系統與流程

2023-06-09 01:57:31 1

本發明涉及一種網頁消重的方法和系統。

背景技術：

隨著網際網路的發展及其廣泛應用，網絡上的信息呈爆炸式增長，網際網路已經成為了人們獲取信息的重要來源。通常使用搜尋引擎來幫助人們快速找到所需要的信息，搜尋引擎方便了人們查找自己所需要的信息，節省了處理時間，已經成為了人們使用頻繁的網上服務。

然而，據中國網際網路信息中心統計報告顯示，重複結果太多是用戶在使用搜尋引擎時遇到的主要問題。據統計，網際網路上大約有30％左右的重複網頁是由於轉載造成的。網頁重複問題對搜尋引擎帶來了一定的影響，重複網頁不僅浪費了存儲空間，也增加了搜尋引擎的處理時間。同時搜尋引擎的檢索結果包含了很多內容重複的網頁，降低了檢索質量，所以網頁消重已經成為搜尋引擎中一項必不可少的工作。

網頁消重通常將網頁的內容(正文文本)作為消重對象，其基於內容的文本複製檢測。兩個網頁之間存在重複，表現為網頁的正文文本間內容完全相同或部分相同。網頁消重的核心任務是判斷網頁的內容之間的相似度，所謂相似度是指網頁的內容相同和相關的比例，內容間相似度越大，內容複製的可能性越大，相似度越小，內容複製的可能性越小。按照我們日常經驗，當內容的重複的部分大到一定的程度，我們才能判斷其存在重複。所以，在網頁消重中要對文本相似度定義一個閾值，只有相似度大於一定閾值才能判斷其存在重複現象。網頁消重技術一般不是將整個網頁作為處理對象的，而是從網頁中抽取足以代表該網頁的特徵，然後對這些特徵進行相似度的計算，關鍵 技術就是網頁的內容的特徵提取算法及特徵相似度比較算法。

當抽取出網頁的內容後，需要提取出內容的特徵。按照特徵提取的粒度可以有以下提取方法：

(1)按照詞(或者字)這個級別的粒度進行特徵提取

(2)按照整個文檔這個級別的粒度進行特徵提取

(3)粒度級別介於文檔和詞之間，比文檔粒度小，比詞粒度大

當兩篇網頁進行比較時，即是對提取出的特徵進行比較。粒度最大的極端情況是每個文檔用一個HASH函數編碼(比如MD5)，這樣只要編碼相同就說明文檔完全相同，但是粒度太大帶來的問題是對於細微的變化文檔無法判別，只能判斷是否完全相同，至於部分相同以及相同的程度無法判斷。

特徵比較算法：

根據提取出的特徵值來對網頁之間的相似度進行計算，如果大於系統預先設定的閾值，則可判斷是重複網頁。根據抽取特徵的類型不同，比較方法一般分為兩類：

(1)基於字符串比較

網頁提取出來的特徵為字符串類型，通過比較字符串之間的相似度(如採用最大公共子序列算法)來判斷網頁是否重複。

(2)基於向量空間模型比較

這類方法一般從內容中提取出特徵向量，最後採用點積、餘弦或者類似方式度量兩篇文檔的特徵向量，以此作為文檔相似度的依據。如基於詞頻向量的算法首先統計每篇文檔中各個單詞(字或詞)的出現次數，然後根據單詞頻度構成特徵向量，最後計算餘弦夾角來進行判斷。

基於特徵句的網頁消重算法

首先提取網頁的內容，對網頁的內容進行分詞，為了提取每個網頁的內容的特徵詞，考慮每個詞語的詞頻信息(Frequency)、位置信 息(Location)、是否在標題中出現(Title)以及其他一些特殊的標識性信息。綜合考慮上述四個選項，分別賦予不同的比例，計算得到特徵詞的權值。並從中找出權值最大的特徵詞。在網頁的內容中尋找該特徵詞第一次出現的位置，以其第一次出現所在的句子作為該網頁的特徵句。將兩篇網頁的比較轉換為兩個句子的最長公共子序列的比較。當匹配度達到設定的閾值時，則認為該網頁與重複網頁資料庫中的網頁重複，將該網頁與原網頁合併，如果整個網頁資料庫中都沒有與之重複的網頁，則將該網頁加入到網頁資料庫中。

基於標點的網頁消重算法

網頁的內容一般都會包含標點符號。基於標點的網頁消重算法就是利用標點符號出現在網頁文本中的特點，在文章中特定的位置提取出一些字符，將這些字符組成代表該字符串的字符串來唯一的標識網頁。然後比較字符串之間的相似度來判斷是否為重複網頁。

現有技術的網頁消重方法都具有缺陷。例如，基於特徵句的網頁消重算法，特徵的選取比較複雜，需要考慮較多的因素，同時特徵句的比較算法時間複雜度較高，當網頁規模達到幾十萬的時候，由於需要與網頁集合中的特徵句兩兩比較會導致時間複雜度急劇增加。基於標點的網頁消重算法只適用於網頁的內容含有標點符號，且內容不會改變的情況，如果網頁的內容發生變化(語句前後順序變化等)，會導致抽取的標點特徵字符串發生變化導致判斷錯誤。同時也存在比較特徵字符串時間複雜度高的問題。

現有方案的比較對象都是網頁的內容，如果網頁的內容提取不準確，存在網頁噪聲，會導致判斷準確度不高。基於特徵句的方法由於需要將待判斷的網頁特徵句與網頁集合中的特徵句集合兩兩比較，當集合規模較大時，時間複雜度會很高。基於標點的消重算法適用範圍有限，當網頁的內容的語句順序發生變化時，標點特徵字符串會發生較大的變化，導致準確度下降，同時由於也需要與網頁集合中的標點 特徵字符串集合兩兩比較，時間複雜度較高。

因此，期望提供一種改進的網頁消重的方法和系統。

技術實現要素：

為了解決現有技術中的上述缺點和問題中的至少一個而提出本發明。基於現有技術存在的缺點，本發明提供了一種的方法和系統。

根據本發明的一個方面，提供了一種用於網頁消重的方法，包括：通過分析網頁的HTML原始碼來提取所述網頁的內容；獲得代表所述網頁的內容的字頻特徵串，其中所述字頻特徵串包括主字頻特徵串以及輔特徵串；以及對所提取的字頻特徵串進行相似度計算。

可選地，提取網頁的內容包括以下中的一個或多個：對所述網頁的HTML原始碼進行預處理；對所述網頁進行分塊；對分塊的節點進行聚合；以及對分塊進行過濾。

可選地，對所述網頁的HTML原始碼進行預處理包括過濾掉不包含主題信息的標籤以及還原轉義字符。

可選地，對所述網頁進行分塊包括將經過預處理的HTML原始碼初始化為DOM樹，然後提取出DOM樹中的所有分塊節點。

可選地，對分塊的節點進行聚合包括將內節點、隱藏節點刪除、並且對具有相同顯示屬性的節點進行合併。

可選地，對分塊進行過濾包括計算分塊的語義屬性，然後找出所有分塊中語義屬性值最小的一個分塊。

可選地，所述主字頻特徵串包括所述網頁的內容中字頻大於給定 閾值的所有字。

可選地，所述主字頻特徵串不按照字頻從大到小進行排序。

可選地，所述輔特徵串包括所述主字頻特徵串中各個字的附加信息。

可選地，對所提取的字頻特徵串進行相似度計算包括消除停用詞的影響。

可選地，不刪除主字頻特徵串中的停用詞。

可選地，對所提取的字頻特徵串進行相似度計算包括：確定所述網頁的內容的長度和基準網頁的內容的長度是否都大於閾值；確定所述網頁的內容與所述基準網頁的內容中較小的內容長度與較大的內容長度的比值是否小於閾值；如果確定所述網頁的內容的長度和所述基準網頁的內容的長度中的一個大於閾值、或者如果確定所述網頁的內容與所述基準網頁的內容中較小的內容長度與較大的內容長度的比值小於閾值，則確定所述網頁的內容的輔特徵串與所述基準網頁的內容的輔特徵串的相關度；如果確定所述網頁的內容的長度和所述基準網頁的內容的長度都不大於閾值、並且如果確定所述網頁的內容與所述基準網頁的內容中較小的內容長度與較大的內容長度的比值不小於閾值，則確定所述網頁的內容的主字頻特徵串與所述基準網頁的內容的主字頻特徵串的相關度；以及如果所確定的相關度大於閾值，則確定所述網頁與所述基準網頁是重複網頁，否則為非重複網頁。

可選地，通過編輯距離來對所提取的字頻特徵串進行相似度計算。

根據本發明的另一個方面，提供了一種用於網頁消重的系統，包括：用於通過分析網頁的HTML原始碼來提取所述網頁的內容的裝置； 用於獲得代表所述網頁的內容的字頻特徵串的裝置，其中所述字頻特徵串包括主字頻特徵串以及輔特徵串；以及用於對所提取的字頻特徵串進行相似度計算的裝置。

可選地，所述提取所述網頁的內容的裝置包括以下中的一個或多個：用於對所述網頁的HTML原始碼進行預處理的裝置；用於對所述網頁進行分塊的裝置；用於對分塊的節點進行聚合的裝置；以及用於對分塊進行過濾的裝置。

可選地，用於對所述網頁的HTML原始碼進行預處理的裝置包括用於過濾掉不包含主題信息的標籤以及還原轉義字符的裝置。

可選地，用於對所述網頁進行分塊的裝置包括用於將經過預處理的HTML原始碼初始化為DOM樹，然後提取出DOM樹中的所有分塊節點的裝置。

可選地，用於對分塊的節點進行聚合的裝置包括用於將內節點、隱藏節點刪除、並且對具有相同顯示屬性的節點進行合併的裝置。

可選地，用於對分塊進行過濾的裝置包括用於計算分塊的語義屬性，然後找出所有分塊中語義屬性值最小的一個分塊的裝置。

可選地，所述主字頻特徵串包括所述網頁的內容中字頻大於給定閾值的所有字。

可選地，所述主字頻特徵串不按照字頻從大到小進行排序。

可選地，所述輔特徵串包括所述主字頻特徵串中各個字的附加信息。

可選地，用於對所提取的字頻特徵串進行相似度計算的裝置包括用於消除停用詞的影響的裝置。

可選地，不刪除主字頻特徵串中的停用詞。

可選地，用於對所提取的字頻特徵串進行相似度計算的裝置包括：用於確定所述網頁的內容的長度和基準網頁的內容的長度是否都大於閾值的裝置；用於確定確定所述網頁的內容與所述基準網頁的內容中較小的內容長度與較大的內容長度的比值是否小於閾值的裝置；用於如果確定所述網頁的內容的長度和所述基準網頁的內容的長度中的一個大於閾值、或者如果確定所述網頁的內容與所述基準網頁的內容中較小的內容長度與較大的內容長度的比值小於閾值，則確定所述網頁的內容的輔特徵串與所述基準網頁的內容的輔特徵串的相關度的裝置；用於如果確定所述網頁的內容的長度和所述基準網頁的內容的長度都不大於閾值、並且如果確定所述網頁的內容與所述基準網頁的內容中較小的內容長度與較大的內容長度的比值不小於閾值，則確定所述網頁的內容的主字頻特徵串與所述基準網頁的內容的主字頻特徵串的相關度的裝置；以及用於如果所確定的相關度大於閾值，則確定所述網頁與所述基準網頁是重複網頁，否則為非重複網頁的裝置。

可選地，通過編輯距離來對所提取的字頻特徵串進行相似度計算。

附圖說明

通過下面結合附圖進行的描述，本發明一些示範性實施例的上述和其他方面、特徵和優點對於本領域技術人員來說將變得顯而易見，其中：

圖1是根據本發明的一個實施例的網頁消重的方法的流程圖；

圖2是示出根據本發明的一個實施例的對網頁提取內容的一個示例過程的流程圖；以及

圖3是示出根據本發明的一個實施例的對字頻特徵串計算相關度 的過程的流程圖。

具體實施方式

提供參考附圖的下面描述以幫助全面理解本發明的示範性實施例。其包括各種細節以助於理解，而應當將它們認為僅僅是示範性的。因此，本領域普通技術人員應當認識到，可以對這裡描述的實施例做出各種改變和修改，而不會背離本發明的範圍和精神。同樣，為了清楚和簡明，省略了對公知功能和結構的描述。

圖1是根據本發明的一個實施例的網頁消重的方法的流程圖。

如圖1中所示，根據本發明的方法首先在步驟S110中通過分析網頁的HTML(超文本標記語言)原始碼來提取網頁的內容。

現有方案的比較對象都是網頁的內容，如果網頁的內容提取不準確，存在網頁噪聲，會導致判斷準確度不高。因為噪聲會影響網頁特徵的提取，從而使得特徵的比較出現誤差，造成誤判或者漏判，所以噪聲嚴重影響了網頁之間相似度的計算，從而導致噪聲的存在會對網頁消重的準確度產生影響。

在本文中，將與網頁的主題內容無關的信息稱之為「噪聲」。例如，在網頁中為了增加視覺效果上的美觀而使用的javascript、css等、為了商業利益而在網頁上呈現的廣告信息都可以被稱為「噪聲」。

噪聲的存在對搜尋引擎、Web文檔分類、信息提取等方面造成不利影響。例如，噪聲的存在不僅降低了處理的速度，還會影響處理結果的準確性。例如，在搜尋引擎中，網頁上的冗餘信息嚴重影響查詢詞與網頁之間的相關度計算。因為目前信息檢索都是通過用戶的查詢詞是否出現在文檔中，來判斷用戶的查詢詞是否和某篇文章相關，基本上不涉及語義和語法的分析，更加沒有邏輯上的推理處理，所以只 要查詢詞出現在文檔中，就認為文檔與該查詢相關，當網頁的內容沒有包含查詢相關詞條，而網頁中的噪聲(導航信息、廣告、授權信息等)卻包含了查詢相關詞條時，信息檢索系統可能會把與查詢無關的一些文檔返回給用戶，這樣的結果嚴重地影響了搜索質量。

根據本發明的一個實施例，在提取網頁的內容時，儘可能地過濾掉噪聲，從而消除噪聲對網頁消重的不利影響。

圖2示出了對網頁提取內容的一個示例過程的流程圖。

在步驟S210中，對網頁的HTML原始碼進行預處理。預處理例如可以包括過濾掉不包含主題信息的標籤以及還原轉義字符。

例如，SCRIPT、STYLE等標籤均不包含頁面主題信息，同時還會增加算法的時間空間複雜度，所以可以將這些標籤都過濾掉。此外，可以將諸如如&lt(<)、&quot(")等的轉義字符還原為本身代表的字符，例如可以將&lt還原為<、將&quot還原為"。如果不對轉義字符進行處理，那麼&quot將被認為是5個字符，而實際上它代表的只有一個字符(")，這會導致語義屬性的計算出現偏差。因此，對轉義字符進行處理可以提高計算的準確度。此外，預處理還可以將所有的英文字母全部轉化為小寫字母，當然也可以將所有的英文字母全部轉化為大寫字母。

為了進行預處理，可以首先將頁面的HTML原始碼讀入內存，以方便程序處理。

在步驟S220中，對網頁進行分塊。

網頁結構通常是按照導航區域、廣告區域、用戶交互區域、版權區域以及主題內容區域分塊的。本發明可以將網頁中的這些塊劃分開。

例如，可以將經過預處理的HTML代碼初始化為DOM樹，然後提取出DOM樹中的所有分塊節點。例如，可以將利用開源軟體HTML PARSER(HTML解析器)來將經過預處理的HTML代碼初始化為DOM樹，並且可以利用TABLE、P、TR、DIV等標籤作為分塊標籤。

在步驟S230中，對分塊的節點進行聚合。例如，可以將內節點、隱藏節點刪除、並且對具有相同顯示屬性的節點進行合併，來對分塊的節點進行聚合。

分塊的節點之間存在著嵌套關係。例如，一個DIV節點下可以包含其它DIV、P等子節點，子節點同樣可以包含其它的分塊節點。在本發明中，將包含其它分塊節點的節點稱為外節點，以及將不包含其它分塊節點的節點內節點。

本發明人發現內節點包含的文本文字一般較少，並且其內容都被包含其的外節點所包括，所以內節點相當於冗餘信息。因此，在本發明中對內節點進行刪除。此外，本發明可以將節點的style屬性含有hidden的節點也進行刪除。通過實驗發現，一個網頁的所提取的全部分塊節點一般為幾十至上百個，但是在刪除內節點、隱藏節點後，分塊的節點的數目大大降低，只有十幾個至幾十個。因此，通過刪除內節點和隱藏節點提高了算法的效率，降低了時間複雜度。

在網頁布局中，具有相同顯示屬性的節點都是屬於一個相對獨立的分塊(如導航區，廣告區等)。刪除內節點後，對每一個節點，找到其子節點，如果子節點的顯示屬性都是相同的，則刪除所有的子節點，保留該節點。這樣進一步減少了分塊，提高了算法效率。

此外，分塊的寬度具有比較重要的意義，主題區一般位於頁面中間且寬度較大，佔網頁寬度80％左右，而噪聲部分一般位於主題區的 兩側且寬度較窄，所以可以計算各個分塊節點的寬度屬性，並且將小於寬度閾值的分塊進行刪除。例如，可以將該閾值設置為80％，當然可以根據需要將該閾值設置為其它適當值。

通過上述處理，可以將分塊的數目降至最低，方便了以後的處理。

在步驟S240中，對分塊進行過濾。例如，可以通過計算分塊的語義屬性來對分塊進行過濾。可以計算分塊的語義屬性，然後找出所有分塊中語義屬性值最小的一個分塊，並將該分塊作為網頁的內容輸出。

此外，在計算分塊的語義屬性之前，可以判斷分塊中字符數目是否大於預設的最小值(即分塊包含的最少字符數目)，如果小於最小值，意味著是與主題無相關的信息，可以刪除該分塊。

語義屬性採用的是節點中連結文本的長度和非連結文本的長度之間的比值。因為網頁的內容與噪聲部分最顯著的區別就是：噪聲通常都是以超連結的形式進行表現的，而網頁的內容通常都是以非連結的形式表現的。計算分塊的語義屬性後進行主題相關性判斷，找出語義屬性值最小的一個分塊，將該分塊作為網頁的內容所屬的分塊，最後輸出該分塊的文本內容。計算公式如下：

公式(1)中，Topic(Ai)代表分塊Ai的語義屬性值。Link(Ai)代表該分塊Ai中所有節點的連結文本的長度之和，Word(Ai)代表該分塊Ai中所有節點的非連結文本的長度之和。公式(2)中，words(nodej)表示Ai分塊中子節點nodej的非連結文本長度。公式(3)中，Links(nodej)表示Ai分塊中子節點nodej的連結文本長度。在計算連結文本的長度和 非連結文本的長度的時候，可以去除空格、tab鍵等無意義的字符，使得語義屬性更加準確，提高算法的準確率。

雖然在圖2中示出了步驟S210-S240，但是可以對圖2增加其它步驟，或者從圖2刪除步驟。因此，對網頁提取內容可以包括步驟S210-S240中的一個或多個。

現在返回圖1，在步驟S120中，獲得代表網頁的內容的字頻特徵串，其中所述包括主字頻特徵串以及輔特徵串。

文本表示方法中應用最廣泛的是向量空間模型。在向量空間模型中，必須選定文本的特徵形式，在現有技術中特徵通常為詞。文本被表示成高維空間向量，其中每一維為一個特徵。這樣的方法需要對文本進行分詞，並計算詞的權值，最後計算向量之間的相似度。對中文進行分詞面臨能否正確分詞的難題，並且向量的高維度也增加了算法的時間複雜度。

基於此，根據本發明的用於網頁消重的方法和系統基於字頻。通過提取字頻能繞過能否正確分詞的難題，減少構造、維護詞表的時間，同時採用編輯距離樹對字頻特徵進行比較，降低了時間複雜度。

對於網頁內容來說，所使用的字的數量是相對小的。例如，對於字來說，國標GB2312一二級字庫中有字6763個，而常用的字就在這幾千個字中。也就是說，儘管網頁內容的長度難以控制，但字的數量是相對穩定的，用字頻表示文本能夠保證字對文本的覆蓋率。

在本發明中，字頻是指一個字的相對使用頻率，即一個字使用次數與所統計的內容的總字數的比例。如果在一篇2000字的文章中，「的」使用了78次，則「的」的頻率就是78/2000*100％＝3.9％。基於字頻來對網頁消重是基於以下的事實：不同文本之間的字頻特徵是不相同的。 為了處理方便，在本發明中，字頻也可以是指一個字的出現次數。

由於低字頻的字對內容的特徵的貢獻不大，故可以設定一個閾值，凡是字頻小於這個閾值的字去掉，從而減少特徵串的長度，降低算法所佔的時間、空間複雜度。在本發明中，可以將所有字頻大於給定閾值的字稱為網頁的主字頻特徵串。此外，將主特徵串中各個字的附加信息稱為輔特徵串。例如，可以將該閾值設定為3，當然也可以根據需要將該閾值設定為其它適當值。

可以提取網頁的內容(例如在步驟S110中獲得的)的字頻主特徵串(表示為S1)以及輔特徵串(表示為S2)。

例如，可以根據網頁的內容來統計各個字出現的次數，並且可以將出現次數大於閾值的字作為該網頁的主字頻特徵串。在確定主字頻特徵串之後，可以為主字頻特徵串中的每個字確定附加信息。一個字的附加信息例如可以是該字每次出現的位置附近特定位置的字。為了減少輔特徵串的長度，可以取該字附近一個字，例如緊到該字之前的一個字或緊接該字之後的一個，當然也可以取其它數量的字。

然後計算S1之間的相似度(如有必要再對S2進行比較)，通過與系統預先設定的閾值進行比較，從而判斷是否為重複網頁。該算法拋棄了從文章中固定位置或者依據固定標誌(如標點符號)提取特徵的方法，以字頻提取特徵串，適用範圍更廣。例如，假定在S1中包含「大」這個字，並且其一共出現了4次，則可以取「大」字每次出現位置的附近位置的字組成輔特徵串。輔特徵串S2保留了網頁的內容的文本結構，能進一步提高算法的準確率。因為對於不是重複網頁的內容來說，輔字頻特徵串相等的概率是非常小的，除非它們本來就是重複網頁。此外，輔特徵串可以按照該字出現的順序對附加信息進行保存。

本發明人已發現字頻以下的兩個特點：當一篇短的文本與一篇長 的文本進行相似度比較時，很有可能將不是重複網頁的網頁判斷為重複網頁。因為短文本文字太少，提取出的主字頻特徵串很有可能存在於長文本的主字頻特徵串中，特別是當相比較的網頁屬於相同分類的時候，從而造成誤判；當二個文本長度都比較大時，主字頻特徵串的相似度也會比較高，從而造成誤判。在本發明中，提出了輔字頻特徵串的概念，當兩個文本長度差別比較大或者當二者文本長度都比較大時，如果主字頻特徵串的相似度大於系統的閾值(例如，可以將該閾值設置為0.8，當然可以根據需要改閾值設置為其它適當值)，還可以進行輔字頻特徵串的比較。所以輔特徵串S2的存在，提高了字頻消重算法的準確率。

對於中文來說，可以以常用的6763個簡體中文字(GB2312)作為基準提取字頻。GB2312在計算機內部是用內碼表示的。GB2312規定，所有的國標碼字及符號組成一個94*94的方陣。在此方陣中，每一行稱為一個"區"，每一列稱為一個"位"。這個方陣實際上組成一個有94個區(編號由01到94)，每個區有94個位(編號由01到94)的字字符集。一個字所在的區號和位號的組合就構成了該字的"區位碼"。其中，高兩位為區號，低兩位為位號。這樣區位碼可以唯一地確定某一字或字符；反之，任何一個字或符號都對應一個唯一的區位碼，沒有重碼。所以可以把6763個簡體中文字分別編號為0-6762。除了6763個簡體中文字外，網頁一般還包含了數字、字母等非中文字，所以算法將10個數字編號為6763-6772，26個英文字母編號為6773-6798。

此外,還可以消除停用詞的影響。停用詞是指由於該關鍵字太常見、使用太頻繁，以至於在字頻特徵中經常出現。停用詞常見多是語言中的副詞、連詞、介詞，例如「是」、「的」、「啊」等等。由於停用詞幾乎在字頻特徵中都會出現，相當於字頻特徵中的不變部分，而字頻特徵是代表不同的網頁的，應該隨著網頁的不同而不同，字頻特徵應該是變化的，所以停用詞不適合作為代表網頁的字頻特徵，因此在比較主字頻特徵串的時候可以消除停用詞的影響，以提高消重的 準確率。然而，可以不需要刪除主字頻特徵串中的停用詞，因為停用詞的輔特徵串對於不同的網頁是不同的。輔字頻特徵串的作用就是保留內容的文本結構(順序)，此時停用詞的輔特徵串的存在較好地保留了文本結構。

在步驟S130中，對所提取的字頻特徵串進行相似度計算。

定義兩個網頁的相似性度量公式通常為公式(4)所示。

公式(4)中：A、B分別表示兩個網頁。B為基準網頁，要計算網頁A與網頁B的相似度。P(A)表示網頁A中的特徵集合，P(B)表示網頁B中的特徵集合，|P(A)∩P(B)|表示網頁A與網頁B中特徵相等的數目；|P(A)∪P(B)|表示網頁A與網頁B中特徵數目之和(重複的特徵只算一次)。

如果P(A)∩P(B)＝P(A)∪P(B)，即sim(A,B)＝1，則網頁A與網頁B完全重複

如果P(A)∩P(B)＝P(A)，P(A)∪P(B)＝P(B)，即sim(A,B)＝|P(A)|/|P(B)|，則網頁A是網頁B的子集。假設A的特徵只有B的1/2，則sim(A,B)＝0.5,當A的特徵只有B的1/3，則sim(A,B)≈0.33，當A的特徵只有B的8/9，則sim(A,B)≈0.89。從以上可以看出，相似度的跨度比較大，從0.33變化到0.89，這對閾值的設定十分不便。閾值過小，可能將不是重複的網頁判斷為重複網頁，閾值過大又容易將本來是重複網頁的判斷為不是重複網頁。

所以有必要對公式(4)進行改變。由於B是基準網頁，網頁相似度的判斷就是判斷網頁A中究竟有多少內容與B相同，所以可以公式 (4)改進為如下公式(公式5)：

對於字頻消重，P(A)表示網頁A中字頻特徵串，P(B)表示網頁B中字頻特徵串，|P(A)∩P(B)|表示網頁A與網頁B的字頻特徵串中公共字符串(相同的字)的長度，|P(A)|表示字頻特徵串的長度。相似度的值越大，說明這兩個網頁相同的成分越多。反之，說明這兩個網頁相同的成分越少。可以預先設定一個閾值，當大於閾值的時候，認為網頁存在重複的情況。

當A是B的子集的時候，P(A)∩P(B)＝P(A),sim(A,B)＝1,這與事實相符。網頁A是網頁B的子集，理所當然應該將A判斷成重複網頁，因為B已經包含了A的全部信息。

在對特徵串進行比較時，常規做法是對從網頁的內容中提取出來的特徵串按照字頻從高到低的順序進行排序，然後求出兩個特徵串的最長公共子序列來進行判斷。

在實驗中發現採用最長公共子序列進行字符串的比較時，當比較的兩個網頁Pa、Pb為部分重複(相當於Pa是Pb子集的關係)時，它們之間的相似度sim(A,B)在0.14-0.38之間波動。因為最長公共子序列對順序有嚴格的要求，而當兩個網頁的內容部分重複的時候，字頻順序(從高到低)可能有很大的出入，最長公共子序列也會有較大的變化，導致求得的相似度sim(A,B)較小。

如果將系統相似度閾值設為0.14-0.38之間，當比較的兩個網頁(不重複)的字頻特徵串的長度懸殊時，它們的相似度sim(A,B)也極有可能落在0.14-0.38這個區間內，造成誤判。而且求最長公共子序列算法的時間複雜度為O(nm)，n、m分別為相比較的兩個字符串的長度。而 一個網頁的字頻特徵串長度平均是上百的(n>100,m>100)，那麼nm>10000，時間複雜度較大。

基於上述發現，本發明對字頻特徵串(主特徵串)的比較不採用最長公共子序列的比較方法。在提取網頁的字頻特徵的時候，不對字頻主特徵串進行排序，均保留它們在GB2312中的順序。這樣減少了對字頻進行排序的步驟，提高了算法的效率。

在本發明中，通過直接計算兩個特徵串相同的字的數目來確定字頻特徵串(主特徵串)的相似度。根據GB2312的規定，每個簡體字都有其對應的編號，所以可以通過查表的方式快速得到計算結果。為了進一步提高算法的效率，字頻特徵串(主特徵串)可以僅包含GB2312中的一級字。因為GB2312包含的6763個字的使用覆蓋率可達99.99％，而常用的一級字的使用覆蓋率即可達到99.9％，因此，字頻特徵串可以只限定在GB2312的3755個一級字中。

通過直接計算兩個特徵串相同的字數目來確定字頻特徵串(主特徵串)的相似度可以在效率上比最大公共子序列的算法更高，平均速度提高了5倍之多，並且隨著比較次數的增多，直接比較算法效率更有優勢。

提取主、輔特徵串後，需要與網頁集合中的主、輔特徵串進行比較。如果不採取優化措施的話，不可避免的需要根據以下的過程進行兩兩比較，從而導致時間複雜度較高。

假設要比較的一個網頁為PX，其主字頻特徵串、輔特徵串分別為S1、S2；

已經消重的網頁集為U(P1,P2,......,Pn)，其中P1,P2,......,Pn為網頁中的網頁。

(1)讀取集合U中的一個網頁Pi，首先進行是否完全重複的判斷。 先比較PX與Pi的主字頻特徵串是否相等。如相等，判斷為重複網頁，算法結束。否則轉2。

(2)如果PX、Pi的內容的長度差異較大或者兩者都較大時，轉3。如果PX、Pi的內容的長度差異不大(且長度都較小)，轉4。

(3)計算出PX、Pi的主特徵串中相同的字(設Px中這些相同字的輔特徵串的長度和為length(Px))，然後計算PX、Pi中每個相同字的輔特徵串中相同的字數目，得到其長度和為L2，如果L2/length(Px)>預先設定的閾值，則可以判斷PX、Pi為重複網頁，算法結束，否則轉步驟5。例如，可以將該閾值設置為0.8，當然可以根據需要將該閾值設置為其它適當值。

(4)比較PX與Pi的主字頻特徵串相同的字數目，得到長度為L1，如果L1/length(S1)>預先設定的閾值，判斷為重複網頁，否則轉5。例如，可以將該閾值設置為0.8，當然可以根據需要將該閾值設置為其它適當值。

(5)繼續判斷集合U中的下一個網頁，如還有未判斷的網頁，重複步驟1，否則認為集合中沒有重複的網頁，予以保留，同時將該網頁加入到集合中。

由算法得知，待判斷的網頁需要與網頁集合中的網頁進行兩兩比較,而且由於按順序的比較網頁集合中的網頁，平均每次需要比較的次數為(n+1)/2,而其中的一些比較次數是無用的，這導致該算法時間複雜度較高。

為了減少與網頁集合中的主、輔特徵串比較次數，本方案採用了編輯距離的方法。下面詳細介紹：

字符串A到B的編輯距離是指：只用插入、刪除和替換三種操作，最少需要多少步可以把A變成B。例如，從FAME到GATE需要兩步(兩次替換)，從GAME到ACM則需要三步(刪除G和E再添加C)。

編輯距離有如下性質，令d(x,y)表示字符串x到y的距離，那麼顯然：

(1)d(x,y)＝0若且唯若x＝y

(2)d(x,y)＝d(y,x)

(3)d(x,y)+d(y,z)>＝d(x,z)

具體到字頻特徵串比較，本發明的方法根據主字頻特徵串之間的編輯距離來構造編輯距離樹，構造過程如上所述。由於主字頻特徵串沒有按照字頻從大到小進行排序(均保留它們在GB2312中的順序)，所以特徵串中字的順序對編輯距離的計算沒有影響。假設有兩個字頻特徵串為T1、T2，Commlength(T1,T2)＝r,其中commonlength(T1,T2)表示T1、T2相同的字數目，那麼T1、T2之間的編輯距離：

D(T1,T2)＝(T1.length-r)>(T2.length-r)？T1.length-r:T2.length-r；

例如：T1＝大皮中T2＝大年其中

則d(T1,T2)＝(3-2)>(4-2)？(3-2):(4-2)＝2，則T1與T2之間的編輯距離為2。編輯過程如下：首先將T1中『皮』替換為『年』，然後添加一個字『其』，需要兩步變換。

編輯距離樹特點：

設待比較網頁的字頻特徵串為X，編輯距離樹的根節點為Y，Y的子節點為Z。下面所指的公共字符串均指二個特徵串之間相同的字數目。

已知：X與Y主字頻特徵串之間的公共字符串為L(X,Y)，Y與Z主字頻特徵串之間的編輯距離為D。

結論：X與Z主字頻特徵串之間的公共字符串長度L(X,Z)<＝L(X,Y)+D

證明如下：因為Y與Z主字頻特徵串之間的編輯距離為D，意味著Y經過D步變換就能變成Z。而變換有三種：

插入：考慮極端情況，插入Y的D個字都包含在X中，那麼L(X,Z)＝L(X,Y)+D；

刪除：考慮極端情況，被刪除的D個字(Y中)不在X與Y的公 共字符串中，那麼L(X,Z)＝L(X,Y)

替換：考慮極端情況，新的D個字(替換Y中除X與Y之間的公共字符串的D個字)都包含在X中，那麼L(X,Z)＝L(X,Y)+D

綜上，X與Z之間的公共字符串長度L(X,Z)M*X.length(M為預先定義的閾值)。而L(X,Z)最大值為L(X,Y)+D,如果L(X,Y)+D<M*X.length，那麼Z肯定不與X相似，此時D<M*X.length-L(X,Y)。所以通過判斷Y與其子節點Z之間的編輯距離D，只有當D大於M*X.length-L(X,Y)時，子節點Z代表分支中的各個節點才有可能與X相似，所以對於所有與根節點編輯距離D小於M*X.length-L(X,Y)的子節點都不需要判斷，這樣減少了比較次數，使得算法效率比直接兩兩比較有了提高。

設要比較的網頁為PX，它的主、輔特徵串分別為S1、S2，root是初始化為編輯距離樹的根節點，M為預先設定的相似度閾值。例如，可以將該閾值設置為0.8，當然可以根據需要將該閾值設置為其它適當值。

(1)PX與root的主特徵串的相同字數目為L；考慮Root中編輯距離大於M*S1.length-L的子節點，如果存在這樣的子節點轉(2)。如沒有，則非重複網頁，將S1，S2添加到編輯距離樹中，返回false，算法結束。

(2)循環判斷編輯距離大於M*S1.length-L的每個子節點，對節點進行判斷(參見上面介紹的不採用編輯距離樹的過程)，如該節點判斷為重複網頁，則返回true，算法結束；否則root＝該子節點，轉(1)。

(3)如沒有節點滿足重複網頁的條件，則將S1、S2遞歸添加到編輯距離樹中，返回false，算法結束。

圖3示出了根據本發明的一個實施例的對字頻特徵串計算相關度的過程的流程圖。

在步驟S310中，確定目標網頁P的內容的長度和基準網頁PR的內容的長度是否都大於閾值。例如，可以將該閾值設置為500，當然可以根據需要將該值設置為其它值。

在步驟S320中，確定目標網頁P的內容與基準網頁PR的內容中較小的內容長度與較大的內容長度的比值是否小於閾值。例如，可以將該值設置為0.3，當然可以根據需要將該值設置為其它適當值。

如果在步驟S310中確定目標網頁P的內容的長度和基準網頁PR的內容的長度中的一個大於閾值、或者如果在步驟S320中確定所述比值小於閾值，則在步驟S330中，確定目標網頁P的內容的輔特徵串的相關度。

如果在步驟S310中確定目標網頁P的內容的長度和基準網頁PR的內容的長度都不大於閾值、並且如果在步驟S320中確定所述比值不小於閾值，則在步驟S340中，確定目標網頁P的內容的主字頻特徵串的相關度。

如果在步驟S340中確定的相關度大於閾值，則確定目標網頁P與基準網頁PR是重複網頁，否則為非重複網頁。

相對於現有技術，根據本發明的方法降低了特徵串比較的時間複雜度，同時輔特徵字符串的存在提高了正確率。

此外，本發明還可以涉及與網頁消重的方法相對應的用於網頁消重的系統。

雖然本說明書包含許多特定實施方式細節，但是不應當將這些細節解釋為對任何發明或可以主張的內容的範圍的限制，而應當解釋為 對可以特定於特定發明的特定實施例的特徵的描述。還可以將在本說明書中在分離的實施例的情境中描述的某些特徵組合在單個實施例中實現。相反地，也可以將在單個實施方式的情境中描述的各個特徵分離地在多個實施方式中實現或在任何適當的子組合中實現。此外，儘管可能在上面將特徵描述為在某些組合中起作用，甚至最初主張如此，但是可以在一些情況下將來自所主張的組合的一個或多個特徵從組合中刪去，並且可以將所主張的組合指向子組合或者子組合的變體。

類似地，雖然在附圖中以特定次序描繪了操作，但是不應當將這理解為需要以所示的特定次序或者以連續次序執行這樣的操作、或者需要執行所有圖示的操作才能達到期望的結果。在某些情況下，多任務以及並行處理可以是有利的。此外，不應當將在上述實施例中的各種系統組件的分離理解為在所有實施例中均需要這樣的分離，而應當理解的是，通常可以將所描述的程序組件和系統集成到一起成為單個軟體產品或封裝為多個軟體產品。

電腦程式(也稱作程序、軟體、軟體應用、腳本或代碼)可以以任何形式的程式語言編寫，所述程式語言包括編譯或解釋語言、或者說明性或過程語言，並且其可以以任何形式部署，包括作為獨立程序或作為模塊、組件、子程序或適於在計算環境中使用的其它單元。電腦程式沒有必要對應於文件系統中的文件。可以將程序存儲在保持其它程序或數據的文件(例如，存儲在標記語言文檔中的一個或多個腳本)的一部分、專用於討論中的程序的單個文件或者多個協調文件(例如，存儲一個或多個模塊、子程序或部分代碼的文件)中。

上述具體實施方式，並不構成對本發明保護範圍的限制。本領域技術人員應該明白的是，取決於設計要求和其他因素，可以發生各種各樣的修改、組合、子組合和替代。任何在本發明的精神和原則之內所作的修改、等同替換和改進等，均應包含在本發明保護範圍之內。