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

2、探討。關鍵詞:網絡蜘蛛;搜索引擎;散列函數;WEB 中圖分類號:TP394文獻標識碼: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 已經成為一所巨大的信息資源寶庫。但是如何使用這個包含了一百多億個WEB 頁面的寶庫,成為互聯網用戶面臨的一個難題,搜索引擎的出現與發展解決了這一問題。經過十幾年的發展,搜索引擎在收集頁面的數量及質量都有了很大提高,已經成為眾多互聯網用戶進入網絡的一個重要入口。搜索引擎技術也成為最具活力和最有發展前途的技術之一。但同時我們也要注意到,搜索引擎也存在下列有待發展的地方:(1檢索的結果集中還存在相當數量的重復頁面。這種重復包括兩種形式:一是同一站點出于保護自身的原因,在不同的域注冊了相同主機名的域名,實際上是指向同一IP 地

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

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

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

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

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

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

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

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

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

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

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

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

16、IP 地址的Hash 值和URL 的Hash 值來進行頁面資源唯一性的確定,并給出了實例進行說明。這種方法在一定規模的模擬系統中取得了良好的效果。參考文獻: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周先存,侯整風.一種基于ELGaml 簽名和零知識證明的身份認證方案.微計算機信

17、息,2004.5:1146閆宏飛,李曉明.關于中國Web 的大小、形狀和結構.計算機研究與發展,2002.8:63-727張瀚,王秀峰等.基于時空混沌的單向Hash 函數構造.物理學報,2005.9:40-459李曉明,鳳旺森.兩種對URL 的散列效果很好的函數.軟件學報,2004.2:179-185:48-49作者簡介:楊海東(1973-,男,漢族,碩士生,江蘇淮安人,主要從事網絡算法與技術研究;葉小嶺(1964-,女,滿族,副教授,碩士生導師,主要從事網絡系統安全、研究領域為優化方法與最優控制;張穎超(1960-,男,漢族,江蘇徐州人,教授,碩士生導師,研究領域為系統控制和仿真、網絡控制技術等。Biography: