張紅霞 郭小粉

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

一、算法

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

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

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

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

二、關(guān)鍵詞提取算法

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

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

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

（2）搜索正文關(guān)鍵詞。對解析得出的標(biāo)題和正文，首先經(jīng)過分詞、去停用詞之后形成一系列的詞串，其中標(biāo)題分詞后形成的詞串我們稱為標(biāo)題關(guān)鍵詞集，正文分完詞后形成的詞串我們稱為正文詞集。采用基于窗口搜索的方式尋找正文詞集中與標(biāo)題關(guān)鍵詞集相關(guān)度高的詞（稱為正文關(guān)鍵詞）?；诖翱谒阉鞯姆绞剿阉髡年P(guān)鍵的思路是：正文中如果幾個詞經(jīng)常與標(biāo)題關(guān)鍵詞在同一窗口中共同出現(xiàn)，則認(rèn)為它們與標(biāo)題關(guān)鍵詞在表達該文檔上相關(guān)度很高，即它們是正文關(guān)鍵詞。將所有的標(biāo)題關(guān)鍵詞和正文關(guān)鍵詞統(tǒng)稱為該網(wǎng)頁文檔的關(guān)鍵詞。

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

三、實驗結(jié)果

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

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

混淆錯誤率計算公式：

四、實驗結(jié)果分析

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

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

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

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

參考文獻

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

（作者單位：河南農(nóng)業(yè)職業(yè)學(xué)院）