本文關(guān)鍵詞：搜索引擎去重算法的研究與實現(xiàn)，由筆耕文化傳播整理發(fā)布。

搜索引擎去重算法的研究與實現(xiàn)

一.什么是無效信息

搜索引擎作為一項網(wǎng)絡(luò)應(yīng)用，已經(jīng)成為人們查詢信息的重要工具之一，它可以使人們從Intemet大量紛雜的信息中，找到與主題相關(guān)的信息，為人們查詢信息提供了方便。但是由于中文自身的特點，目前的搜索引擎存在著很多的問題，它只解決了信息查詢的問題，而從信息資源覆蓋面、檢索精度、信息的輸出方式等許多方面來看，檢索結(jié)果的查全率和查準率不是很高，將Web挖掘技術(shù)應(yīng)用到搜索引擎領(lǐng)域，將會給用戶提供一個高效、準確的Web檢索工具。目前，Web用戶主要是使用搜索引擎在互聯(lián)網(wǎng)上檢索信息，但目前的搜索引擎往往返回給用戶成千上萬個檢索到的頁面，且其中很大一部分是重復(fù)的或與用戶檢索要求不相關(guān)的內(nèi)容。這些內(nèi)容被認為是無效信息。

二.搜索引擎的分類

結(jié)合互聯(lián)網(wǎng)信息的特點，搜索引擎形成了三個不同的類型：

1、全文檢索搜索引擎：全文搜索引擎是名副其實的搜索引擎，國外具代表 性的有Google(http：／／www．google．com)、yahoo(http：／／search．yahoo．tom)、AllTheWeb(http：／／www．a(chǎn)lltheweb．tom)等， 國內(nèi)著名的有百度(http：／／www．Baidu．com)、中搜(http：／／www．zhongsou．com)。它們都是通過從互聯(lián)網(wǎng)上提取的各個網(wǎng)站的信息(以網(wǎng)頁文字為主)而建立的數(shù)據(jù)庫，檢索與用戶查詢條件匹配的相關(guān)記錄，然后按一定的排列順序?qū)⒔Y(jié)果返回給用戶，也是目前常規(guī)意義上的搜索引擎。

2、目錄搜索引擎：目錄索引雖然有搜索功能，但在嚴格意義上算不上是真正的搜索引擎，僅僅是按目錄分類的網(wǎng)站鏈接列表而己。用戶完全可以不用進行關(guān)鍵分類目錄也可找到需要的信息。國外比較著名的目錄索引搜索引擎有yahoo(http：／／www．yahoo．com)Open Directory Project(DMOZ)(http：／／www．dmoz．tom／)、LookSmart(http：／／www．100ksmart．com)等。國內(nèi)的搜狐(http：／／www．sohu．com)、新浪(http：／／www．sina．com)、網(wǎng)易(http：／／www．163．com)搜索也都具有這一類功能。

3、元搜索引擎：元搜索引擎在接受用戶查詢請求時，同時在其它多個引擎上進行搜索，并將結(jié)果返回給用戶。著名的元搜索引擎有Dogpile(http：／／www．dogpile．corn)、Vivisimo(http：／／www．vivisimo．com)等，國內(nèi)元搜索引擎中具代表性的有搜星搜索引擎(http：／／www．soseen．corn／)，優(yōu)客搜索(http：／／www．yok．com)。在搜索結(jié)果排列方面，有的直接按來源引擎排列搜索結(jié)果，如Dogpile，有的則按自定的規(guī)則將結(jié)果重新排列組合，如Vivisimo。

4、其他的像新浪(http：／／search．sina．corn．cn)、網(wǎng)易(http：／／search．163．com)、A9(http：／／www．A9．com)等搜索引擎都是調(diào)用其它全文檢索搜索引擎，或者在其搜索結(jié)果的基礎(chǔ)上做了二次開發(fā)。

三.搜索引擎的缺陷

據(jù)MORI民意調(diào)查，只有18％的用戶表示總能在網(wǎng)上查到需要的信息，68％ 的用戶對搜索引擎很失望，28％的用戶表示還可以，4％的用戶不知道�？傊� 搜索引擎在準、全、新、快等方面還存在著嚴重的缺陷和問題，需要加以完善。

目前搜索引擎存在的缺陷或者說問題，可以歸納為以下幾個方面：

1、從信息的完備性來看

目前搜索引擎的數(shù)據(jù)庫規(guī)模和覆蓋面是極其有限的。美國科學(xué)期]：lJNature 的一篇報告中指出，最大的搜索引擎也只能覆蓋現(xiàn)在網(wǎng)頁資源的16％，美國NEC 研究所的SreveLawrence和C1LeeCiles兩位博士研究表明，現(xiàn)在的搜索引擎漏掉大約84％的網(wǎng)頁信息。在這一方面存在的主要問題是：①搜索引擎之間缺乏協(xié)作和聯(lián)合。各個搜索引擎都有自己一套的分類體系、標引方法、索引方法、數(shù)據(jù)庫結(jié)構(gòu)和檢索界面，缺乏統(tǒng)一的規(guī)范性的控制，因此，各搜索引擎之間的數(shù)據(jù)資源的兼容性和互操作性差，缺乏資源共享的基礎(chǔ)。同時又由于各搜索引擎之間沒有分工合作，因此，各搜索引擎的數(shù)據(jù)資源交叉重復(fù)現(xiàn)象嚴重。②缺乏大型、集成、綜合性的元搜索引擎，而垂直搜索引擎發(fā)展不快，許多專業(yè)性的搜索引擎對搜索目標、服務(wù)對象、主題范圍及類型等定位模糊。③許多有實力的大型的搜索引擎(女IGoogle和百度等)仍在盲目追求數(shù)據(jù)庫規(guī)模，提供的信息服務(wù)都很大眾化，缺乏深度以及個性化，查準率不高。④忽視對tEWeb信息資源的收集。

2、從查全率和查準率來看

據(jù)權(quán)威機構(gòu)統(tǒng)計，因特網(wǎng)上約有100多億個網(wǎng)頁，而世界上目前搜索量最大 的Google也只能搜索33億網(wǎng)頁，就是說再大的搜索引擎也不可能使查全率達到 100％。而且據(jù)excite統(tǒng)計，只有不到1％的用戶會看200條以后的結(jié)果，幾乎100％的用戶不會查看超過1000條的結(jié)果[71。就是說對于大多數(shù)用戶來說，查全率是次要的，而查準率則更具有意義。在這一方面存在的主要問題是：①對于多數(shù)檢索課題而言，不是輸出的檢索結(jié)果過載，記錄數(shù)量達到成千上萬條，給用戶的相關(guān)性判斷帶來困難：就是零輸出或輸出量太少，造成過分的漏檢。②由于網(wǎng)站或網(wǎng)頁的標引類型、標引深度、索引方法等的不規(guī)范，多數(shù)搜索引擎又不支持概念檢索，因而直接影響檢索詞的選擇、匹配和檢索結(jié)果的輸出格式，從而影響了查準率。③由于目前各種搜索引擎是按即定的相關(guān)度對檢索結(jié)果進行排序的，而各種檢索引擎對相關(guān)度參數(shù)的選擇、計量和算法又各異，這就難免不與用戶的檢索目標相沖突，因而會人為地影響到查全率和查準率。④在檢索功能方面的主要缺陷是關(guān)鍵詞檢索和主題分類檢索不能有機的結(jié)合起來，多數(shù)搜索引擎不提供概念檢索(即主題檢索)，對自然語言理解力差，而檢索式的構(gòu)造難度大，更難提供多媒體檢索�？傊@一切都影響著搜索引擎的檢索效率和效果。

3、從信息的輸出方式來看

據(jù)專家測評，目前主要的搜索引擎返回的相關(guān)結(jié)果其比率不足45％。據(jù)估計，當(dāng)鍵入1個關(guān)鍵詞后，在百度搜索的結(jié)果中總會有70％"-'80％的無用信息，有時是100％的無用【引。在這一方面存在的主要問題是：①關(guān)鍵詞檢索輸出的結(jié)果相關(guān)度排序方式單一，不能根據(jù)用戶需要來選擇信息輸出的排序方法。②主題分類檢索輸出的往往只是網(wǎng)站，而不能快速準確地提供網(wǎng)頁信息。用戶登錄到相關(guān)網(wǎng)站后又往往找不到所需要的信息無功而返。③不論是關(guān)鍵詞檢索，還是主題分類檢索，信息輸出的結(jié)果顯示格式簡單，不能向用戶提供相關(guān)的更好的途徑和信息。④數(shù)據(jù)更新速度慢，更新周期長，對于網(wǎng)上已不存在的網(wǎng)頁不能及時刪除，因而出現(xiàn)死鏈較多，而且也不加以說明，浪費用戶的寶貴時間。⑤網(wǎng)站、網(wǎng)頁經(jīng)常處于動態(tài)的變化之中，新的頁面不斷涌現(xiàn)，舊的頁面不斷消亡，如果不及時維護，那么索引庫中就會存留著許多無用的信息，就會導(dǎo)致成千上萬條沒有經(jīng)過篩選與排序的記錄被輸出。

4、從界面的友好性來看

有人估計，83％的網(wǎng)站含有商業(yè)廣告，只有6％的網(wǎng)站含有科學(xué)和教育的內(nèi) 容�？蒲腥藛T和普通大眾受到搜索引擎提供的同樣的信息待遇，兩者都面臨著信 息不對121的困惑【8】。在這一方面存在的主要問題是：①可供用戶選擇搜索條件和搜索結(jié)果的功能不多，多數(shù)搜索引擎沒有類型、范圍限定。②多數(shù)搜索引擎是面向主題檢索，而不是面向用戶檢索，不能重復(fù)利用用戶檢索過的成果，更不能對特定的用戶進行定題跟蹤服務(wù)。③對自然語言理解有限，用戶必須自己構(gòu)造檢索式來表達檢索命題。由于各搜索引擎關(guān)鍵詞檢索所采用的符號及其含義、分類檢索所建立的類目體系及使用規(guī)則各不相同，因此給用戶構(gòu)造檢索式帶來了困難。④網(wǎng)站簡介不規(guī)范，有些太簡，弄不清網(wǎng)站所包含信息的內(nèi)容和范圍，有些太繁，，如霧里看花，難識廬山真面目，還有些網(wǎng)站簡介誤導(dǎo)用戶進入它的廣告世界。⑤網(wǎng)頁的幫助系統(tǒng)許多等于虛設(shè)，起不到幫助的作用，有的只是常識介紹，更是缺乏透明度。總之，搜索引擎當(dāng)前存在的主要問題是：①查全率低。由于數(shù)據(jù)庫規(guī)模偏小，對網(wǎng)絡(luò)信息覆蓋不全，因而搜索引擎收錄信息的完備性差，導(dǎo)致查全率低，用戶檢索不到理想的信息。②查準率低。由于搜索引擎對網(wǎng)站網(wǎng)頁標引不規(guī)范、對自然語言理解差、對索引數(shù)據(jù)庫維護不及時等因素，導(dǎo)致查準率低，大量無用信息或不相關(guān)信息困繞著廣大用戶。

四無效信息的粒度

五.除無效信息的方法及優(yōu)缺點

1.關(guān)鍵字提取技術(shù)分析

關(guān)鍵詞提供了文檔內(nèi)容的概要信息，它們被使用在很多數(shù)據(jù)挖掘的應(yīng)用中。 關(guān)鍵字提取是一項重要的文本檢索技術(shù)，在Web頁檢索、文檔聚類、文檔摘要 提取、文本挖掘等方面都有廣泛的應(yīng)用19,101。正確地提取關(guān)鍵字可以讓我們在大量的文檔中快速地選出所需要的文檔。近年來，隨著大量文檔的電子化，關(guān)鍵字提取的需求也就越來越大。例如，當(dāng)我們?yōu)g覽一個網(wǎng)頁而希望快速了解其內(nèi)容時，就可以通過提取關(guān)鍵字來實現(xiàn)。目前，針對英文的關(guān)鍵詞提取的研究已經(jīng)取得的較多的研究成果，方法也比較成熟。但是中文不同于英文，中文詞與詞之間沒有明顯的界限，存在一個分詞的問題，致使中文關(guān)鍵詞提取相對于英文困難些，這就使得中文信息檢索的效率在一定程度上被限制了。

1.1關(guān)鍵字提取算法

關(guān)鍵字提取算法可分為兩類：基于訓(xùn)練集的關(guān)鍵字提取策略和不需要訓(xùn)練集 的關(guān)鍵字提取策略【l51。基于訓(xùn)練集的方法將關(guān)鍵字提取視為分類問題，通過將文檔中出現(xiàn)的詞語劃分到關(guān)鍵字類或非關(guān)鍵字類，再從關(guān)鍵字類中選擇若干個詞語作為關(guān)鍵字，該類算法由Peter．D．Tumey首次提出，其技術(shù)已日趨成熟。

不需要訓(xùn)練集的算法，可分為以下四類：基于統(tǒng)計的方法，如頻率統(tǒng)計；基 于詞語圖的方法，如KeyGraph；基于詞語網(wǎng)絡(luò)的方法，如中介性指標

(BCBetweennessCentrality)；基于SWN的方法；上述四種方法都是建立在詞頻統(tǒng)計基礎(chǔ)上�；诮y(tǒng)計的方法簡單快速，能夠提取高頻詞語，卻忽略對文檔具有重要意義但出現(xiàn)頻率不高的詞語，因此提取的關(guān)鍵字具有片面性�；谠~語圖的方法需要設(shè)定的參數(shù)過多，如頂點數(shù)、邊數(shù)等，因而常造成邊界上的取舍問題，影響算法的穩(wěn)定性和精度�；赟WN的方法是以平均距離長度為關(guān)鍵字提取依據(jù)，而SWN理論以連通圖為基礎(chǔ)，故對非連通的文檔結(jié)構(gòu)圖，無法衡量頂點的重要性，也無法正確地提取文檔關(guān)鍵字。

1.2TF*IDF方法

文本的形式化表示一直是搜索引擎、自動文摘以及文本檢索等信息檢索領(lǐng)域 關(guān)注的基礎(chǔ)性問題�？臻g向量模型(Space Vector Model)qb的TF木IDF文本表示是該領(lǐng)域里得到廣泛應(yīng)用并且取得較好效果的一種文本表示方法。特征詞權(quán)重用以說明該特征詞在描述網(wǎng)頁文檔內(nèi)容時所起的作用的重要程度【16】。特征詞權(quán)重計算的目的就是要準確描述網(wǎng)頁信息，所以權(quán)重計算的好壞直接影響網(wǎng)頁信息描述的準確性。目前，比較成熟的方法就是使用TF*IDF來計算權(quán)重。該方法主要考慮以下三個因素：

特征詞頻率tf(term frequency)．該特征詞在此網(wǎng)頁文檔中出現(xiàn)的頻率。

特征詞倒排文檔頻率idf(inverse document frequency)：該特征詞在網(wǎng)頁文檔 集合中分布情況的量化，常用的計算方法是l。g(％+0．01)。其中Ⅳ為網(wǎng)頁文檔集合中的文檔數(shù)目；n七為出現(xiàn)過該特征詞的網(wǎng)頁文檔數(shù)目。

歸一化因子(normalization factor)：對各個分量進行標準化。

特征詞權(quán)重的優(yōu)缺點。

(1)從表2．1可以看出，T4和T5分別在一個且僅在一個文檔中出現(xiàn)，雖

然出現(xiàn)的文檔頻率不高，但仍分別在各自的文檔中作為最能區(qū)別文檔的特征詞。

(2)Tl從表2．1顯示，在文檔textl和text2中出現(xiàn)頻率都是最高的，而且

出現(xiàn)頻率相等。因此，對于區(qū)別文檔來說，T1不起任何作用，但是在兩個文檔 中T1的權(quán)重均大于T3的權(quán)重。這樣的結(jié)果暴露出TF*IDF方法的缺點。 TF*IDF方法雖然考慮特征詞在文檔集合中分布情況，很大程度上提高了文

檔表示的準確性。然而，它并沒有考慮特征詞在文檔中的分布比例，而且對于網(wǎng) 頁文檔的特殊性，也沒有考慮特征詞分布的位置。

2.網(wǎng)頁去重算法分析

隨著互聯(lián)網(wǎng)的發(fā)展，越來越多的網(wǎng)頁出現(xiàn)在互聯(lián)網(wǎng)上。隨之帶來的問題是網(wǎng) 頁內(nèi)容的大量重復(fù)。去除重復(fù)網(wǎng)頁不但可以減少相似的搜索結(jié)果，減輕用戶的閱 讀負擔(dān)，還可以壓縮搜索引擎的索引空間，提高搜索引擎的檢索效率。如何快速、 準確地去除重復(fù)網(wǎng)頁，成為搜索引擎研究領(lǐng)域一個亟待解決的問題。針對網(wǎng)絡(luò)中大量數(shù)據(jù)重復(fù)的現(xiàn)狀，當(dāng)前，提出的網(wǎng)頁查重的方法比較多，但大體分為兩大類：基于分類的方法、排除相同URL方法以及基于特征碼的方法。本文就目前常用的網(wǎng)頁去重算法進行介紹，并對其效率、準確率、召回率做了細致的分析。

2.1 SCAM算法

SCAM算法是由斯坦福大學(xué)提出的用于復(fù)制檢測和剽竊檢測的一種算法。SCAM的方法受到了信息檢索技術(shù)的啟示，是一種基于詞頻統(tǒng)計的方法。SCAM方法可以檢測出2篇文檔之間相似處所在的位置，所使用的方法就是計算出每篇文檔的詞頻，將文檔用詞頻向量的方法表示出來，再計算2個詞頻向量之間的距離，在一定的范圍之內(nèi)就判斷為相似的文檔，由于同時還保留了該詞的位置信息，所以同時也可以查找出到底文章的哪個部分是相似的。具體講就是，SCAM首先統(tǒng)計文檔中各個單詞出現(xiàn)的次數(shù)，然后按照信息檢索中常用的倒排索引存儲法(inverted

index storage)存儲文檔與詞頻信息。最后，SCAM參照向量空間模型VSM(vector space model)提出了相關(guān)頻率模型RFM(relative frequency model)，用以度量文檔相似性。向量空間模型一般采用點積或者余弦公式來度量相似性，而相關(guān)頻率模型其實是對余弦公式進行了改動，試圖提高文件復(fù)制檢測精度。

2.2.基于特征串的網(wǎng)頁去重算法

  本文關(guān)鍵詞：搜索引擎去重算法的研究與實現(xiàn)，由筆耕文化傳播整理發(fā)布。