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

1、 郵局訂閱號(hào):82-946360元/年技術(shù)創(chuàng)新軟件時(shí)空PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注楊海東:碩士生基于Hash 算法實(shí)現(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)用戶進(jìn)入網(wǎng)絡(luò)的一個(gè)重要入口。但目前搜索引擎的結(jié)果還存在著許多有待改進(jìn)的地方。本文從搜索引擎返回結(jié)果中存在的重復(fù)頁面入手,解決如何消除重復(fù)頁面,并對其將來的發(fā)展進(jìn)行了進(jìn)一步

2、探討。關(guān)鍵詞:網(wǎng)絡(luò)蜘蛛;搜索引擎;散列函數(shù);WEB 中圖分類號(hào):TP394文獻(xiàn)標(biāo)識(shí)碼: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文章編號(hào):

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

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

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

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

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

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

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

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

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

12、或近似異址的在情況在Interne 中表現(xiàn)為鏡像站點(diǎn)的分布。在許多文獻(xiàn)中將鏡像站點(diǎn)歸為不同站點(diǎn)。但在實(shí)際應(yīng)用中,對于鏡像站點(diǎn)的訪問只要其中一個(gè)就行了。對3.1中的例子,需要將IP 轉(zhuǎn)化為域名,得到形如“http:/+域名+路徑”00F4CC7599310F795FB4B19B6A13CCA9這樣在存儲(chǔ)URL 的數(shù)據(jù)庫結(jié)構(gòu)中就增加兩個(gè)字段:IP_ID 和Name_ID ,對應(yīng)著IP 和域名的序列,每搜索到一個(gè)URL ,都將域名部分和IP 部分進(jìn)行相互轉(zhuǎn)化,與存放在兩個(gè)字段中的值進(jìn)行比較。如果IP 地址相同,并不是簡單地丟棄,而是將URL 以增量的方式添加在存放URL 的字段后,相同域名的URL

13、可以直300- 郵局訂閱號(hào):82-946360元/年技術(shù)創(chuàng)新軟件時(shí)空PLC 技術(shù)應(yīng)用200例您的論文得到兩院院士關(guān)注接丟棄。在存儲(chǔ)介質(zhì)容量劇增且價(jià)格下降的今天,這種以空間換效率的做法是可以接受的。這兩個(gè)序列通過一定的算法在遍歷網(wǎng)絡(luò)時(shí)生成,每個(gè)頁面的ID 長度固定且必須唯一。bbs2. 的識(shí)別,需要依賴于網(wǎng)絡(luò)蜘蛛的智能性,即判斷URL 的相似程度及其父URL,如果URL 的相似度和內(nèi)容的相似度都高于設(shè)定的閾值,則認(rèn)為這些站點(diǎn)互為鏡像。3.3多線程網(wǎng)絡(luò)蜘蛛HASH 函數(shù)處理單個(gè)線程的網(wǎng)絡(luò)蜘蛛效率很低,在實(shí)際應(yīng)用中很少。為了能快速地收集URL 并進(jìn)行處理,網(wǎng)絡(luò)蜘蛛往往采用多線程技術(shù)。這就需要線程之間

14、相互協(xié)調(diào),實(shí)現(xiàn)負(fù)載的均衡,同時(shí)每個(gè)線程遵循上述單線程的規(guī)則。一個(gè)或幾個(gè)線程負(fù)責(zé)一個(gè)域的搜索,如讓10個(gè)線程負(fù)責(zé) 域的搜索。在搜索的過程中如果鏈接指向某線程負(fù)責(zé)域外的其它域,則將任務(wù)交給相關(guān)線程ID 。這樣分配的另外一個(gè)好處就是:線程i 在寫入數(shù)據(jù)時(shí)不需要鎖定整個(gè)數(shù)據(jù)庫,只需要鎖定部分區(qū)域就行了,其它線程可以正常工作。每個(gè)線程在將數(shù)據(jù)寫入數(shù)據(jù)庫前,都要檢查該值是否已經(jīng)存在于數(shù)據(jù)庫中。在大型商用搜索引擎中不但使用多線程技術(shù),而且還需要多臺(tái)計(jì)算機(jī)并行地抓取WEB 頁面,這就要求除了選性能好的Hash 函數(shù)外,還要考慮負(fù)載的均衡性,這涉及到分布式系統(tǒng)的設(shè)計(jì),此處不作論述。4結(jié)束語在Internet 還

15、存在著這樣一種重復(fù)鏈接:由于相互引用而造成的內(nèi)容上的重復(fù)。它們屬于不同的網(wǎng)站,頁面的主體部分基本相同。這種重復(fù)雖然一定程度上浪費(fèi)了網(wǎng)絡(luò)資源,但它還有存在的必要性,因?yàn)槟壳暗木W(wǎng)絡(luò)還不穩(wěn)定,經(jīng)常有HTTP404(Not found 錯(cuò)誤發(fā)生,或者有些頁面下載過慢,多個(gè)相似頁面資源可以互相補(bǔ)充,將資源提供給用戶。因此這類重復(fù)暫時(shí)不進(jìn)行去重操作。搜索引擎經(jīng)過幾代的發(fā)展,已經(jīng)在向更高的智能化邁進(jìn),但是在收集頁面數(shù)量、結(jié)果的排序及個(gè)性化方面還存在若干有待革新改進(jìn)的地方,搜索引擎市場的競爭也日趨激烈,搜索引擎的發(fā)展還有很長的一段路要走。本文的創(chuàng)新之處在于:利用Hash 結(jié)果的固定長度和極低的碰撞機(jī)率,提出用

16、IP 地址的Hash 值和URL 的Hash 值來進(jìn)行頁面資源唯一性的確定,并給出了實(shí)例進(jìn)行說明。這種方法在一定規(guī)模的模擬系統(tǒng)中取得了良好的效果。參考文獻(xiàn):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 簽名和零知識(shí)證明的身份認(rèn)證方案.微計(jì)算機(jī)信

17、息,2004.5:1146閆宏飛,李曉明.關(guān)于中國Web 的大小、形狀和結(jié)構(gòu).計(jì)算機(jī)研究與發(fā)展,2002.8:63-727張瀚,王秀峰等.基于時(shí)空混沌的單向Hash 函數(shù)構(gòu)造.物理學(xué)報(bào),2005.9:40-459李曉明,鳳旺森.兩種對URL 的散列效果很好的函數(shù).軟件學(xué)報(bào),2004.2:179-185:48-49作者簡介:楊海東(1973-,男,漢族,碩士生,江蘇淮安人,主要從事網(wǎng)絡(luò)算法與技術(shù)研究;葉小嶺(1964-,女,滿族,副教授,碩士生導(dǎo)師,主要從事網(wǎng)絡(luò)系統(tǒng)安全、研究領(lǐng)域?yàn)閮?yōu)化方法與最優(yōu)控制;張穎超(1960-,男,漢族,江蘇徐州人,教授,碩士生導(dǎo)師,研究領(lǐng)域?yàn)橄到y(tǒng)控制和仿真、網(wǎng)絡(luò)控制技術(shù)等。Biography: