基于Hash算法實現(xiàn)搜索引擎中重復(fù)WEB頁面的消除

1、 郵局訂閱號:82-946360元/年技術(shù)創(chuàng)新軟件時空PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注楊海東:碩士生基于Hash 算法實現(xiàn)搜索引擎中重復(fù)WEB 頁面的消除Elim inated Duplicate Search WEB pages with Hash algorithm(南京信息工程大學(xué)楊海東葉小嶺張穎超Yang,Haidong Ye ,Xiaoling Zhang,Yingchao摘要:搜索引擎已經(jīng)成為互聯(lián)網(wǎng)用戶進入網(wǎng)絡(luò)的一個重要入口。但目前搜索引擎的結(jié)果還存在著許多有待改進的地方。本文從搜索引擎返回結(jié)果中存在的重復(fù)頁面入手,解決如何消除重復(fù)頁面,并對其將來的發(fā)展進行了進一步

2、探討。關(guān)鍵詞:網(wǎng)絡(luò)蜘蛛;搜索引擎;散列函數(shù);WEB 中圖分類號:TP394文獻標(biāo)識碼:AAbstract:As an important enterance to Internet,search Engine has also existed some shortcoming in gernal.This article discussedhow to eliminate duplicate web pages with Hash algorithm and described its future.Key words:WEB Crawl,Search Engine,HASH,WEB文章編號:

3、1008-0570(200609-3-0299-031引言Internet 已經(jīng)成為一所巨大的信息資源寶庫。但是如何使用這個包含了一百多億個WEB 頁面的寶庫,成為互聯(lián)網(wǎng)用戶面臨的一個難題,搜索引擎的出現(xiàn)與發(fā)展解決了這一問題。經(jīng)過十幾年的發(fā)展,搜索引擎在收集頁面的數(shù)量及質(zhì)量都有了很大提高,已經(jīng)成為眾多互聯(lián)網(wǎng)用戶進入網(wǎng)絡(luò)的一個重要入口。搜索引擎技術(shù)也成為最具活力和最有發(fā)展前途的技術(shù)之一。但同時我們也要注意到,搜索引擎也存在下列有待發(fā)展的地方:(1檢索的結(jié)果集中還存在相當(dāng)數(shù)量的重復(fù)頁面。這種重復(fù)包括兩種形式:一是同一站點出于保護自身的原因,在不同的域注冊了相同主機名的域名,實際上是指向同一IP 地

4、址。二是大型的網(wǎng)站為了方便不同地區(qū)的用戶訪問,或者緩解大量用戶對同一服務(wù)器訪問造成的壓力,在不同的地理位置安裝物理服務(wù)器,形成鏡像站點。(2收集頁面的數(shù)量有待提高。目前使用量最大的搜索引擎google 收集了40多億WEB 頁面,Yahoo 也稱收集了45億頁面。絕對數(shù)字雖然龐大,但這在互聯(lián)網(wǎng)上120多億的頁面中只占40%不到。需要開發(fā)更強有力的網(wǎng)絡(luò)蜘蛛程序,基于鏈接進行網(wǎng)絡(luò)遍歷的方式還需要改進甚至革新。(3排序的結(jié)果還不能讓用戶非常滿意。更合理的排序方法一直是搜索引擎網(wǎng)站努力改進的方向。影響排序結(jié)果的因素有兩個:排序技術(shù)與商業(yè)因素。排序技術(shù)上,目前傳統(tǒng)的排序算法如PageRank 、HITS

5、 等算法都或多或少地存在一些缺陷,新的排序算法和主題相關(guān)性檢索正在進入到搜索服務(wù)領(lǐng)域。由于現(xiàn)在搜索引擎是免費提供給用戶使用,要依靠提供廣告服務(wù)或競價排名,以維持網(wǎng)站的正常運行,這樣在結(jié)果頁面中會出現(xiàn)相關(guān)的廣告內(nèi)容或者購買競價排名企業(yè)的網(wǎng)站。上述(2、(3點,需要有新的技術(shù)出現(xiàn),第一點可以在現(xiàn)有基礎(chǔ)上進行改進。本文將討論基于Hash 算法消除在搜索引擎數(shù)據(jù)庫中的重復(fù)鏈接。2散列(Hash 算法Hash 算法,在中文中又叫散列算法、雜湊算法等,是將任意長度的字符串作為輸入生成,經(jīng)過n 次迭代運算后生成固定長度的字符串的一種算法。Hash 算法是現(xiàn)代密碼學(xué)的核心,在數(shù)字簽名、身份認(rèn)證和口令鑒別等多個

6、安全領(lǐng)域都有應(yīng)用。在本文中,Hash 算法用來生成每個網(wǎng)頁的識別序列,在生成的序列唯一性方面要求很高,但對于安全性考慮較少,因而采用單向的Hash 算法。為了節(jié)省空間,同時又滿足系統(tǒng)的要求,Hash 結(jié)果的位數(shù)取128bit 。統(tǒng)計結(jié)果表明:如hash(m的長度為128位(bit時,則任意兩個分別為M1,M2的輸入報文具有完全相同的h(m的概率為10-24,即近于零的重復(fù)概率。它較人類指紋的重復(fù)概率10-19還要小5個數(shù)量級。而當(dāng)我們?nèi)ash(m為384(bit乃至1024(bit時,則更是不大可能重復(fù)了。目前Internet 中約有WEB 頁130億個,超級鏈接約600億(1011<

7、<1024。因而128bit 的Hash 序列位數(shù)在現(xiàn)在及未來的一段時間內(nèi)完全可以滿足要求。299-技術(shù)創(chuàng)新中文核心期刊微計算機信息(管控一體化2006年第22卷第9-3期 360元/年郵局訂閱號:82-946現(xiàn)場總線技術(shù)應(yīng)用200例軟件時空2.1單向Hash 函數(shù)的定義及性質(zhì)映射對所有的,容易計算,但其逆過程,給定要求出在計算上是困難的,該函數(shù)稱為單向函數(shù)。單向的Hash 函數(shù)除了具有Hash 函數(shù)動態(tài)輸入、固定輸出、碰撞機率低的特點外,還具有下列三個特性:1不可逆性,已知,經(jīng)過數(shù)次非線性運算和迭代運算后,求計算困難。雖然最新文獻表明,Hash 算法已經(jīng)可以進行逆運算求出m 值,但本文

8、使用Hash 函數(shù)的目的是為了使序列具有唯一的值,對其安全性不作要求;2防偽造性,已知,求使計算困難,這一特性被應(yīng)用在數(shù)字簽名等安全應(yīng)用中;3初值敏感性,中m 的每一字符都與的每一bit 相關(guān),初值每個字符的變動,都將對結(jié)果值c 產(chǎn)生明顯影響。2.2Hash 值的構(gòu)造Hash 函數(shù)的構(gòu)造方法在很多文章和書籍里都有介紹。以MD5算法為例,它以512位作為分組(不滿足的條件的需要對信息對行擴充,使得INFO mod 512=448來處理信息,每一分組又分32個子分組,經(jīng)過四次主循環(huán)進行非線性函數(shù)運算,加快其雪崩效應(yīng),最后得到固定長度的128位Hash 序列。用Hash 函數(shù)可以生成MD5加密序列、

9、SHA 序列等多種形式,對于本文來說,序列的作用是進行唯一性驗證。因此采用常用的MD5算法生成定長且唯一的Hash 序列,本文中所有的Hash 序列均為MD5序列。2.3初值敏感性驗證對于上百億個WEB 頁面來說,為了能唯一標(biāo)識一個頁面,兩個URL 有細微的差別,其Hash 序列都應(yīng)該有大的變化,而且不同的URL 生成的序列應(yīng)該有極低的碰撞機率。下面構(gòu)造三個相似的URL 序列,利用Hash 函數(shù)將其轉(zhuǎn)化成MD5序列,列表如下:表1三個相似URL Hash 序列的對比表1表明:對于單向散列函數(shù),初始值微小的變化會使Hash 結(jié)果以很大的幅度變化,同時128位(32個十六制位不同的排列組合能夠產(chǎn)生

10、大的空間來容納碰撞的產(chǎn)生。3網(wǎng)絡(luò)蜘蛛對重復(fù)記錄的消除對于普通的頁面重復(fù),解決的方法主要依靠網(wǎng)絡(luò)蜘蛛的爬行算法在遍歷網(wǎng)絡(luò)結(jié)點時解決。這種解決方法類似于數(shù)據(jù)結(jié)構(gòu)的圖的遍歷問題,但WEB 中存在著不同于理論上圖的問題,主要體現(xiàn)在兩個方面,一是同一個IP 地址對應(yīng)著不同的域名,如有些大型商業(yè)網(wǎng)站為了保護自己的知識產(chǎn)權(quán),會在不同的域中注冊相同或相似的域名,這樣在處理時,網(wǎng)絡(luò)蜘蛛會把URL 形式不同,但卻指向同一主機的路徑和文件的鏈接當(dāng)成兩個不同的頁面進行處理,在存在上百億頁面的Internet 上會造成大量的重復(fù)。二是把一個網(wǎng)站的鏡像(即同一個網(wǎng)站為了提供給不同地區(qū)的用戶快速訪問,分別就近設(shè)立了內(nèi)容完全

11、相同但IP 不同的站點當(dāng)成不同的網(wǎng)站進行訪問,也造成搜索引擎返回頁面資源的極大浪費。因此應(yīng)當(dāng)設(shè)計一個算法或結(jié)構(gòu)以避免出現(xiàn)上述兩種情況。3.1網(wǎng)絡(luò)中異名同址頁面結(jié)點的消除對異名同址的URL 進行唯一性標(biāo)識。設(shè)有下面URL (以南京信息工程大學(xué)為例: (18/ggb/index.asp(2通過DNS 可知,域名 對應(yīng)的IP 地址即為8,在 這個域名啟用前, (3與前兩個URL 也是等效的。上述三個URL 實際上是指向同一鏈接,在搜索引擎的數(shù)據(jù)庫中沒有必要放置三條記錄來標(biāo)識它們。對于這種情況,將域名轉(zhuǎn)化成IP 序列就可以得出唯一的ID

12、值,得到一個序列:“http:/+IP 地址+路徑”。如上例中,通過DNS 系統(tǒng)取得URL 中字符串 的實際IP 地址8,則由主機的IP 地址和路徑構(gòu)成字符串8/ggb/index.asp 的Hash 序列為:D41D8CD98F00B204E9800998ECF8427E (3式經(jīng)過轉(zhuǎn)換也得到同樣結(jié)果。3.2對同名異址的網(wǎng)頁進行唯一性標(biāo)識同名(或近似異址的在情況在Interne 中表現(xiàn)為鏡像站點的分布。在許多文獻中將鏡像站點歸為不同站點。但在實際應(yīng)用中,對于鏡像站點的訪問只要其中一個就行了。對3.1中的例子,需要將IP 轉(zhuǎn)化為域

13、名,得到形如“http:/+域名+路徑”的形式,則 的Hash 序列為:00F4CC7599310F795FB4B19B6A13CCA9這樣在存儲URL 的數(shù)據(jù)庫結(jié)構(gòu)中就增加兩個字段:IP_ID 和Name_ID ,對應(yīng)著IP 和域名的序列,每搜索到一個URL ,都將域名部分和IP 部分進行相互轉(zhuǎn)化,與存放在兩個字段中的值進行比較。如果IP 地址相同,并不是簡單地丟棄,而是將URL 以增量的方式添加在存放URL 的字段后,相同域名的URL 可以直300- 郵局訂閱號:82-946360元/年技術(shù)創(chuàng)新軟件時空PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注接丟棄。在存儲介質(zhì)容量劇增且價格下降的今

14、天,這種以空間換效率的做法是可以接受的。這兩個序列通過一定的算法在遍歷網(wǎng)絡(luò)時生成,每個頁面的ID 長度固定且必須唯一。對于相似的鏡像站點(,bbs2. 的識別,需要依賴于網(wǎng)絡(luò)蜘蛛的智能性,即判斷URL 的相似程度及其父URL,如果URL 的相似度和內(nèi)容的相似度都高于設(shè)定的閾值,則認(rèn)為這些站點互為鏡像。3.3多線程網(wǎng)絡(luò)蜘蛛HASH 函數(shù)處理單個線程的網(wǎng)絡(luò)蜘蛛效率很低,在實際應(yīng)用中很少。為了能快速地收集URL 并進行處理,網(wǎng)絡(luò)蜘蛛往往采用多線程技術(shù)。這就需要線程之間相互協(xié)調(diào),實現(xiàn)負(fù)載的均衡,同時每個線程遵循上述單線程的規(guī)則。一個或幾個線程負(fù)責(zé)一個域的搜索,如讓10個線程負(fù)責(zé) 域的搜索。在搜索的過程

15、中如果鏈接指向某線程負(fù)責(zé)域外的其它域,則將任務(wù)交給相關(guān)線程ID 。這樣分配的另外一個好處就是:線程i 在寫入數(shù)據(jù)時不需要鎖定整個數(shù)據(jù)庫,只需要鎖定部分區(qū)域就行了,其它線程可以正常工作。每個線程在將數(shù)據(jù)寫入數(shù)據(jù)庫前,都要檢查該值是否已經(jīng)存在于數(shù)據(jù)庫中。在大型商用搜索引擎中不但使用多線程技術(shù),而且還需要多臺計算機并行地抓取WEB 頁面,這就要求除了選性能好的Hash 函數(shù)外,還要考慮負(fù)載的均衡性,這涉及到分布式系統(tǒng)的設(shè)計,此處不作論述。4結(jié)束語搜索引擎發(fā)展至今,有許多關(guān)鍵的技術(shù)需要改進。在大規(guī)模的搜索引擎設(shè)計過程中,可供用戶使用的資源的收集與存放至關(guān)重要,合理的結(jié)構(gòu)不但能提高檢索的效率,還能顯著提

16、高檢索的速度。因此本文從去除重復(fù)的鏈接入手,結(jié)合目前的信息安全與加密手段,提出了用Hash 算法生成固定長度的字符串來解決這一問題的方法,來提高數(shù)據(jù)庫的效用。閆宏飛等人的利用天網(wǎng)( 進行了實驗,數(shù)據(jù)表明:互聯(lián)網(wǎng)中實際存在的重復(fù)頁面占了相當(dāng)?shù)谋戎?。一個小的改進都會搜索引擎的效率產(chǎn)生不可忽視的影響。在Internet 還存在著這樣一種重復(fù)鏈接:由于相互引用而造成的內(nèi)容上的重復(fù)。它們屬于不同的網(wǎng)站,頁面的主體部分基本相同。這種重復(fù)雖然一定程度上浪費了網(wǎng)絡(luò)資源,但它還有存在的必要性,因為目前的網(wǎng)絡(luò)還不穩(wěn)定,經(jīng)常有HTTP404(Not found 錯誤發(fā)生,或者有些頁面下載過慢,多個相似頁面資源可以互

17、相補充,將資源提供給用戶。因此這類重復(fù)暫時不進行去重操作。搜索引擎經(jīng)過幾代的發(fā)展,已經(jīng)在向更高的智能化邁進,但是在收集頁面數(shù)量、結(jié)果的排序及個性化方面還存在若干有待革新改進的地方,搜索引擎市場的競爭也日趨激烈,搜索引擎的發(fā)展還有很長的一段路要走。本文的創(chuàng)新之處在于:利用Hash 結(jié)果的固定長度和極低的碰撞機率,提出用IP 地址的Hash 值和URL 的Hash 值來進行頁面資源唯一性的確定,并給出了實例進行說明。這種方法在一定規(guī)模的模擬系統(tǒng)中取得了良好的效果。參考文獻:1Marc Najork,Janet L.Wiener.Breadth-first search crawling yield

18、s high-quality pages.Proceedings of the 10th international World Wide Web Conference,Hong Kong,May 1-5,20012Soumen Chakrabarti,Matin van de Berg.Focused crawling:a new approach to topic-specific Web resource discovery.http:/www.E.3Chau,M.,Zeng,D.,and Chen,H.:Personalized Spiders for Web Search and Analysis.In Proceedings of the 1st ACM-IEEE Joint Conference on Digital Libraries,Roanoke,Virginia,USA,Jun 2001.4周先存,侯整風(fēng).一種基于ELGaml 簽名和零知識證明的身份認(rèn)證方案.微計算機信息,2004.5:1145王曉宇,周傲英.萬維網(wǎng)的鏈接結(jié)構(gòu)分析及其應(yīng)用綜述.軟件學(xué)報,2003.10:110-1226閆宏飛,李曉明.關(guān)于中國Web 的大小、形狀和結(jié)構(gòu).計算機研究與發(fā)展,2002.8:63-727張瀚,王秀峰等.基于時空混沌的單向Hash