張紅霞 郭小粉

引言：本文提出了一種基于關鍵詞提取的網頁去重算法。該算法考慮了文本的內容信息，其基本思路是：首先解析網頁，提取每篇網頁文檔的標題關鍵詞，以基于窗口搜索的方式尋找正文中與標題關鍵詞相關度高的其它關鍵詞以構成該項篇網頁文檔的關鍵詞集，并根據(jù)關鍵詞集中的所有關鍵詞為網頁文檔建立倒排表，文檔去重就是計算兩篇文檔的關鍵詞重疊率，如果重疊率高于某個閡值時，認為兩篇文檔內容重疊。該算法的優(yōu)點是考慮了正文中與主題相關度高的非高頻詞，避免了僅使用統(tǒng)計值依賴高頻詞去重的缺陷。

一、算法

目前對于網頁去重的研究方法主要有基于聚類的方法、排除相同URL方法、基于特征碼的方法等。

（l）基于聚類的方法是基于網頁的文本內容進行的，它以6763個漢字作為向量的基，文本的漢字字頻就構成了代表網頁的向量。通過計算向量的夾角決定是否是相同網頁。這種方法的優(yōu)點是簡單，容易實現(xiàn)。缺點就是對大規(guī)模網頁聚類的類別數(shù)目大，難以確定，計算量大；只利用字頻信息，沒有利用文本的結構信息；實時性差，對于新網頁需要重新聚類以決定是否重復。因此，在實際應用中難以適用。

（2）排除相同URL方法是各種元搜索引擎去重的主要方法。這種方法主要分析來自不同搜索引擎的網頁URL，相同的URL認為是相同的網頁，然后去重。這種方法的優(yōu)點也是簡單，容易實現(xiàn)，可去除一部分相同的網頁。其缺點是只利用了URL信息未利用網頁的文本內容，不能對轉載造成的重復網頁去除。

（3）基于特征碼的方法是利用標點符號多數(shù)出現(xiàn)在網頁文本中的特點，以句號兩邊各五個漢字作為特征碼來唯一地標識網頁。因為特征碼的精確匹配可以與先進的檢索系統(tǒng)聯(lián)系起來，去重效率較高。

二、關鍵詞提取算法

本文提出的網頁去重算法是基于關鍵詞提取的去重算法，該算法考慮了文本的內容信息，其基本思路是：首先解析網頁，提取每篇網頁文檔的標題關鍵詞，以基于窗口搜索的方式尋找正文中與標題關鍵詞相關度高的其它關鍵詞，文檔去重就是計算兩篇文檔的關鍵詞重疊率，如果重疊率高于某個闌值時，認為兩篇文檔內容重疊。

概括地說，基于關鍵詞比較的網頁去重算法分三步實現(xiàn)：解析網頁，從每個網頁中提取標題和正文內容。以標題關鍵詞為種子點，以基于窗口搜索的方式查找正文中的關鍵詞。計算兩篇網頁文檔的關鍵詞重疊率以確認兩網頁是否重復。

（l）網頁解析。W亡b網頁與普通文本相似，但其有自身的特點，這為網頁分析提供了一些線索。

（2）搜索正文關鍵詞。對解析得出的標題和正文，首先經過分詞、去停用詞之后形成一系列的詞串，其中標題分詞后形成的詞串我們稱為標題關鍵詞集，正文分完詞后形成的詞串我們稱為正文詞集。采用基于窗口搜索的方式尋找正文詞集中與標題關鍵詞集相關度高的詞（稱為正文關鍵詞）。基于窗口搜索的方式搜索正文關鍵的思路是：正文中如果幾個詞經常與標題關鍵詞在同一窗口中共同出現(xiàn)，則認為它們與標題關鍵詞在表達該文檔上相關度很高，即它們是正文關鍵詞。將所有的標題關鍵詞和正文關鍵詞統(tǒng)稱為該網頁文檔的關鍵詞。

（3）計算關鍵詞重疊率。文檔去重的過程就是比對兩篇文檔的所有關鍵詞，為了避免文檔間的兩兩對比，本文通過建立關鍵詞倒排表，文檔中的每一個關鍵詞都在關鍵詞倒排表中查詢出現(xiàn)的文檔號，并求交集。

三、實驗結果

實驗所用的數(shù)據(jù)是四大門戶網站（sina，sohu，163，263）的娛樂體育新聞，為了驗證上述算法，本文分別采用文獻叫中算法（以下稱Forman算法）、文獻中的算法（以下稱lyer算法）和本文算法從去重效果和速度兩個方面做了比較。

評價去重效果時有兩種情況：一種將不相同的兩篇文檔判定為相同文檔，本文稱為混淆錯誤 CE（Confused Error），另一種是將相同的兩篇文檔判定為不相同，本文將這種判定錯誤稱為排斥錯誤 EE（Exclusive Error）。

混淆錯誤率計算公式：

四、實驗結果分析

Forman算法是基于文檔內容進行對比的方法，當文檔中相同的文檔塊經hash映射后（這里采用MDS）相同的個數(shù)超過一定范圍則認為文檔相似，否則不相似。實驗中如果兩篇文檔分塊后做hash，如果80%的哈希值相同，則認為這兩篇文檔是重復文檔。Iyer算法是基于關鍵詞提取的用于論文剽竊檢測的算法，同樣認為樹結構中有80%的哈希值相同，則認為兩篇文檔是重復文檔。

從表2中可以看出，F(xiàn)orman算法的混淆錯誤率很低，因為該算法對文檔相似的檢驗很嚴格，排斥錯誤率高是由于只根據(jù)語句判定相似，而沒有考慮文本所表達的含義。Iyer算法混淆錯誤率較低，排斥錯誤率高的原因是當樹的上層剪枝錯誤時去重算法失效。本文算法混淆錯誤率比Forman算法和Iyer算法高的原因是還存在不同的文檔判定為相同文檔的可能性，但由于本文算法在提取關鍵詞充分考慮了文檔正文所表達的含義，排斥錯誤率低。從綜合評價指標F來看本文算法比其它兩種算法效果更好。

為了對上述方法進行運行速度的比較，本文建立了大小為124個文檔，1191個文檔和10287個文檔三個數(shù)據(jù)集。表3為去重判定時間比較。

從表3中可以看出，F(xiàn)orman算法運行所需時間最多，因為所有的文檔都要進行分段后計算哈希值，計算后還要進行哈希值比較，因此耗時多。Iyer算法雖然對文檔中每句話都抽取關鍵詞，但是由于組成樹狀結構，比對過程中可以剪枝，因此速度稍快。本文算法以標題中的詞為種子點只考慮與標題詞相關的詞生成的詞匯集，去掉大量與主題無關的信息，因此速度較快。從實驗結果可看出，在去重效果和運行速度上本文算法都具有一定的優(yōu)勢。

參考文獻

[1]張海軍，潘偉民，木妮娜，欒靜. 一種自定義順序的字符串排序算法[J]. 小型微型計算機系統(tǒng).2012（09）.

（作者單位：河南農業(yè)職業(yè)學院）