（計算機系統(tǒng)結(jié)構(gòu)專業(yè)論文）nutch搜索引擎中網(wǎng)頁排序技術(shù)的研究.pdf

iiti t l l1 1iil 9 0 3 1 原創(chuàng)性聲明 本人聲明：所呈交的學(xué)位論文是在導(dǎo)師指導(dǎo)下完成的，研究工作所取得的成果和 相關(guān)知識產(chǎn)權(quán)屬廣西大學(xué)所有，本人保證不以其它單位為第一署名單位發(fā)表或使用本 論文的研究內(nèi)容。除已注明部分外，論文中不包含其他人已經(jīng)發(fā)表過的研究成果，也 不包含本人為獲得其它學(xué)位而使用過的內(nèi)容。對本文的研究工作提供過重要幫助的個 人和集體，均已在論文中明確說明并致謝。 論文作者簽名：糾口年占月2b 日 學(xué)位論文使用授權(quán)說明 本人完全了解廣西大學(xué)關(guān)于收集、保存、使用學(xué)位論文的規(guī)定，即： 按照學(xué)校要求提交學(xué)位論文的印刷本和電子版本： 學(xué)校有權(quán)保存學(xué)位論文的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)； 學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文； 在不以贏利為目的的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉績?nèi)容。 請選擇發(fā)布時間： d 即時發(fā)布口解密后發(fā)布 ( 保密論文需注明，并在解密后遵守此規(guī)定) 論文作者簽名：、彳勿沙例導(dǎo)師簽名輟糾留年占月三汨 n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 摘要 隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，搜索引擎已經(jīng)成為人們獲取網(wǎng)絡(luò)信息的 主要工具。研究搜索引擎網(wǎng)頁排序的目的是從眾多搜索結(jié)果中將內(nèi)容相關(guān) 和權(quán)威的網(wǎng)頁排在前面，幫助用戶迅速定位需要的網(wǎng)絡(luò)資源。網(wǎng)頁排序算 法直接影響到搜索引擎信息檢索的準確率和用戶使用滿意度。n u t c h 是基于 j a v a 實現(xiàn)的開源搜索引擎。通過對n u t c h 進行深入研究，指出其目前存在 的兩大問題，其一是沒有實現(xiàn)p a g e r a n k 算法，影響了最終排序效果；其二 是對中文進行單字切分，影響了查詢結(jié)果準確率。 首先，針對目前n u t c h 搜索引擎中沒有實現(xiàn)網(wǎng)頁p a g e r a n k 計算的問題， 利用m a p r e d u c e 并行計算模型處理大數(shù)據(jù)集的優(yōu)勢，在n u t c h 機群系統(tǒng)上 設(shè)計和實現(xiàn)了基于m a p r e d u c e 的p a g e r a n k 分布式并行算法。實驗結(jié)果表 明：處理的數(shù)據(jù)量越大，機群中的節(jié)點越多，計算p a g e r a n k 的效率越高； 另外，該分布式并行算法具有較好的可擴展性。然后，針對目前n u t c h 對 中文進行單字切分的問題，加入了j e 中文分詞器對n u t c h 的中文分詞進行 改進。在分析和研究經(jīng)典p a g e r a n k 算法原理的基礎(chǔ)上，通過設(shè)置控制站外 與站內(nèi)鏈接的比重因子對該算法進行了改進。為了改善n u t c h 基于l u c e n e 的網(wǎng)頁綜合排序模型，將改進后的p a g e r a n k 算法因子融入到n u t c h 網(wǎng)頁評 分計算公式當(dāng)中。實驗表明，改進后n u t c h 明顯提高了查詢結(jié)果的準確率， 改善了中文網(wǎng)頁的排序效果。 關(guān)鍵詞：n u t c h 搜索引擎網(wǎng)頁排序p a g e r a n k 算法 中文分詞 m a p r e d u c e 并行模型 r e s e a r c ho fw e bp a g e sr a n k i n g i nn u t c hs e a r c he n g i n e a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to fi n t e r n e tt e c h n i q u e ，s e a r c he n g i n eh a s b e c o m et h em a i nt o o lf o rp e o p l et oo b t a i nn e t w o r ki n f o r m a t i o n t h er e s e a r c h g o a lo fw e bp a g e sr a n k i n gi n s e a r c he n g i n ei sp u t t i n gt h er e l a t e da n d a u t h o r i t a t i v ew e bp a g e si nt h ef r o n to fm a n ys e a r c hr e s u l t sa n dh e l p i n gu s e rt o l o c a t et h en e t w o r kr e s o u r c er a p i d l y t h ei n f o r m a t i o nr e t r i e v a la c c u r a c yo f s e a r c h a n du s e r ；a t i s f a c t i o n f f e c t e db yt h ew e brankingsearch e n g i n ea n du s e rs a t l s t a c t l o n i sa t t e c t e at h ew e dp a g e s y a l g o r i t h md i r e c t l y n u t c hi sa no p e ns o u r c es e a r c he n g i n eb a s e do n j a v a n u t c h h a sb e e nr e s e a r c h e di nd e t a i l p r e s e n t l y ，t h e r ea r et w od e f e c t si nn u t c h f i r s t l y ， t h ep a g e r a n ka l g o r i t h mi sn o ti m p l e m e n t e d ，s ot h eq u a l i t yo fw e bp a g e s r a n k i n gi si n f l u e n c e d s e c o n d l y ，t h ec h i n e s ei n d i v i d u a lc h a r a c t e rs e g m e n t a t i o n i su s e d ，s ot h ea c c u r a c yo fs e a r c hr e s u l t si sa f f e c t e d f i r s t ，i nv i e wo ft h ed e f e c ti nn u t c hw h i c hh a sn o tr e a l i z e dt h ep a g e r a n k c o m p u t a t i o n ，t h es u p e r i o r i t yo fp r o c e s s i n gl a r g ed a t a s e t sb a s e d o nm a p r e d u c e i su t i l i z e d ，a n dt h em a p r e d u c e b a s e dp a g e r a n kd i s t r i b u t i o n a lp a r a l l e l a l g o r i t h m i s d e s i g n e d a n di m p l e m e n t e do nn u t c h c o m p u t e c l u s t e r s e x p e r i m e n t ss h o wt h a t t h em o r ep r o c e s s i n gd a t aa n dc l u s t e rn o d e sa r e ，t h e i h i g h e re f f i c i e n c yo fc o m p u t i n gp a g e r a n ki s ；m o r e o v e r , t h i s d i s t r i b u t i o n a l p a r a l l e la l g o r i t h mi s o fg o o ds c a l a b i l i t y n e x t ，i nv i e wo ft h ed e f e c ti nn u t c h w h i c hu s e sc h i n e s ei n d i v i d u a lc h a r a c t e rs e g m e n t a t i o n ，j ec h i n e s es e g m e n t a t i o n i sa d d e dt o i m p r o v ec h i n e s es e g m e n t a t i o n i nn u t c h a i t e rt h ec l a s s i c a l p a g e r a n ka l g o r i t h mi sa n a l y z e da n ds t u d i e d ，t h i sa l g o r i t h mi si m p r o v e db y s e t t i n gf a c t o rw h i c hc o n t r o l st h ep r o p o r t i o no fo u t s i d el i n k sa n di n s i d el i n k s i n o r d e rt oi m p r o v et h ew e bp a g e sr a n k i n gs y n t h e t i c a lm o d e lb a s eo nl u c e n ei n n u t c h ，t h ei m p r o v e dp a g e r a n kf a c t o ri s a d d e di n t ot h en u t c hw e bp a g e s s c o r i n gf o r m u l a e x p e r i m e n t ss h o w t h a tt h ea c c u r a c yo fs e a r c hr e s u l t si sr a i s e d a n dt h er a n k i n gq u a l i t yo fc h i n e s ew e bp a g e si si m p r o v e do b v i o u s l ya f t e rt h e i m p r o v e m e n t i nn u t c h k e yw o r d s ：n u t c hs e a r c he n g i n e ；w e bp a g e sr a n k i n g ；p a g e r a n ka l g o r i t h m ； c h i n e s es e g m e n t a t i o n ；m a p r e d u c ep a r a l l e lm o d e l 目錄 摘要i a 】i i s t r a c t i i i 第一章緒論1 1 1 論文研究背景1 1 2 搜索引擎簡述2 1 3 搜索引擎網(wǎng)頁排序算法的研究現(xiàn)狀。3 1 3 1 搜索引擎排序技術(shù)的研究發(fā)展3 1 3 2 基于鏈接分析的改進算法5 1 3 3 搜索引擎綜合排序模型6 1 4 論文研究的目的和意義7 1 5 論文的主要工作和組織結(jié)構(gòu)7 第二章n u t c h 搜索引擎相關(guān)技術(shù)介紹9 2 1l u c e n e 與n u t c h 9 2 2m a p r e d u c e 并行計算模型1 1 2 3 分布式文件系統(tǒng)h d f s 1 4 2 4n u t c h 中的并行計算與機群部署1 4 2 4 1n u t c h 中的分布式并行計算：1 4 2 4 2n u t c h 機群的部署與配置1 5 2 5 本章小結(jié)1 6 第三章n u t c h 中p a g e r a n k 算法的并行實現(xiàn)- 17 3 1 引言17 3 2p a g e r a n k 算法原理。1 7 3 2 1 隨機沖浪模型。1 7 3 2 2p a g e r a n k 算法特性與迭代計算實驗18 3 3 基于m a p r e d u c e 的p a g e r a n k 并行算法2 0 3 4 實驗與分析2 2 3 4 1 構(gòu)建機群系統(tǒng)環(huán)境2 2 3 4 2 實驗結(jié)果與分析2 2 3 5 本章小結(jié)2 5 第四章n u t c h 中網(wǎng)頁排序效果的改進與實現(xiàn)2 6 4 1 引言2 6 4 2 對p a g e r a n k 算法的改進2 7 4 3 對n u t c h 中文分詞的改進2 8 4 3 1 中文分詞技術(shù)2 8 4 3 2 在n u t c h 中加入j e 中文分詞器2 9 4 4 對n u t c h 網(wǎng)頁綜合評分算法的改進3 0 4 4 1n u t c h 中基于l u c e n e 的網(wǎng)頁評分算法3 0 4 4 2o p i c 算法31 4 4 3 改進n u t c h 網(wǎng)頁評分公式。3 2 4 5 實驗與分析3 3 4 5 1t o p n 查準率對比3 3 4 5 2 排序效果對比3 4 4 6 本章小結(jié)3 5 第五章總結(jié)與展望3 6 5 1 總結(jié)3 6 5 2 展望3 6 參考文獻3 8 剄c 謝4 l 攻讀碩士學(xué)位期間參加的科研項目4 2 攻讀碩士學(xué)位期間發(fā)表錄用的學(xué)術(shù)論文4 2 廣西大學(xué)碩士掌位論文n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 1 1 論文研究背景 第一章緒論 隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)中的站點數(shù)量飛速增加，包含的各種信息資源豐 富巨大，網(wǎng)絡(luò)與人們的生活和工作密不可分。無論是進行網(wǎng)絡(luò)購物還是在線遠程教育， 不管是查詢資料信息還是朋友聊天交流，相應(yīng)的網(wǎng)絡(luò)服務(wù)都層出不窮，滿足了人們多方 面的生活需求。但是，面對如此巨大的網(wǎng)絡(luò)信息庫，人們?nèi)绾慰焖儆行У貜闹蝎@得對自 己的工作和生活有價值的信息呢? 搜索引擎技術(shù)的誕生，就很好地解決了人們檢索網(wǎng)絡(luò) 信息的難題。w e b 搜索引擎從1 9 9 4 年開始出現(xiàn)，到現(xiàn)在已經(jīng)有十幾年的歷史了，誕生 了不少使用廣泛的商業(yè)搜索引擎，如g o o s e 、百度和雅虎等，用戶可以盡情享受搜索 引擎帶來的快捷與便利。因此，搜索引擎已經(jīng)成為人們獲取網(wǎng)絡(luò)信息的一種最重要的手 段，也成為計算機科學(xué)領(lǐng)域研究的熱點川。 搜索引擎最初只能檢索十幾萬個w e b 頁面，而現(xiàn)在已經(jīng)可以檢索上百億個頁面， 并且檢索量還在逐年上升。隨著可檢索頁面量的不斷增大，用戶將會獲得更多的搜索結(jié) 果。雖然搜索引擎公司聲稱其可檢索頁面范圍仍不能覆蓋整個因特網(wǎng)，但是從目前現(xiàn)有 的檢索頁面中返回的結(jié)果數(shù)據(jù)看，頁面量已經(jīng)很多了，而用戶是不可能對如此多的檢索 頁面都逐一瀏覽的。根據(jù)美國搜索引擎營銷專業(yè)服務(wù)商i p r o s p e c t 發(fā)布的搜索引擎用戶 使用習(xí)慣情況調(diào)查報告顯示【2 】，超過8 0 的用戶不會去瀏覽3 頁以后的檢索結(jié)果，而超 過一半的用戶只會瀏覽搜索引擎檢索結(jié)果中的第一頁。由此可知，用戶一般只關(guān)注搜索 引擎檢索結(jié)果中排在前面的頁面。因此，提高搜索引擎檢索結(jié)果頁面的準確率是非常重 要的，尤其是排在前面幾頁的檢索結(jié)果。 搜索引擎的目標就是幫助用戶快速定位所需要的資源，并按一定的形式把搜索結(jié)果 呈現(xiàn)給用戶。那么，如何從眾多的檢索結(jié)果頁面中將最相關(guān)和權(quán)威的頁面排在最前面， 就成了搜索引擎需要解決的問題之一。當(dāng)用戶在搜索引擎查詢頁面輸入查詢詞進行檢索 時，總是希望能及時迅速檢索出最想要的結(jié)果，并且這些結(jié)果能排在搜索結(jié)果中的最前 面。因此，搜索引擎檢索結(jié)果的排序效果好壞直接影響到用戶能否方便快捷地獲取所需 的信息資源，同時也直接關(guān)系到用戶使用該搜索引擎的滿意程度【3 】。而決定排序效果的 是搜索引擎的網(wǎng)頁排序算法，算法設(shè)計的好壞直接影響著搜索引擎信息檢索的準確率和 用戶使用滿意度，故排序算法是搜索引擎最核心的部分之一，也是決定搜索引擎成敗的 關(guān)鍵，因此成為當(dāng)前搜索引擎研究領(lǐng)域中的熱門話題。 目前，如g o o s e 和百度等這些商業(yè)搜索引擎，由于技術(shù)和利益方面的保密性，其 中的網(wǎng)頁排序算法涉及商業(yè)機密，人們無法知曉。但是，開源搜索引擎n u t c h 4 的誕生， 為廣大學(xué)者研究搜索引擎提供了很好的選擇，可對其中基本的網(wǎng)頁排序算法技術(shù)進行研 p - 西大學(xué)碩士學(xué)位論文n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 究和改進，以達到更好的排序效果。 1 2 搜索引擎簡述 現(xiàn)代搜索引擎的祖先，是由加拿大m c g i l l 大學(xué)計算機學(xué)院的a l a ne m t a g e 等三名 學(xué)生在1 9 9 0 年發(fā)明的a r c h i e ，它是第一個在互聯(lián)網(wǎng)中自動索引匿名f t p 網(wǎng)站文件的程 序，但搜集的信息資源不是網(wǎng)頁，因此還不是真正意義上的搜索引擎。簡單地說，搜索 引擎( s e a r c he n g i n e ) 是指利用某種計算機程序按照特定的策略對互聯(lián)網(wǎng)信息進行搜集， 然后將組織和處理后的信息按一定的方式顯示給用戶，為用戶提供檢索服務(wù)的系統(tǒng)【5 】。 搜索引擎的工作原理大致可分為四個階段，即網(wǎng)頁爬取、網(wǎng)頁預(yù)處理、網(wǎng)頁索引和 用戶檢索【6 1 。 1 、在網(wǎng)頁爬取階段，搜索引擎利用網(wǎng)頁爬行程序s p i d e r ( 也稱為網(wǎng)絡(luò)蜘蛛) ，順著網(wǎng) 頁中的超鏈接連續(xù)不斷地對網(wǎng)頁進行抓取，直到滿足一定的條件才停止抓取。從互聯(lián)網(wǎng) 有關(guān)超鏈接的理論上講，如果從某個范圍的網(wǎng)頁集合開始出發(fā)進行搜集，就能獲取到互 聯(lián)網(wǎng)中絕大部分的網(wǎng)頁。 2 、在網(wǎng)頁預(yù)處理階段，主要對爬取到的大量網(wǎng)頁進行去重去噪、分詞處理、網(wǎng)頁 鏈接分析、網(wǎng)頁重要程度的計算等工作，并調(diào)用相關(guān)的文檔解析器將非格式化的網(wǎng)頁文 檔轉(zhuǎn)化成格式化的文檔。 3 、在網(wǎng)頁索引階段，對己格式化的網(wǎng)頁文檔進行信息提取工作，例如網(wǎng)頁的u r l 、 頁面中的關(guān)鍵詞及其位置信息、網(wǎng)頁的生成時間以及網(wǎng)頁之間的鏈接關(guān)系等，然后用這 些相關(guān)信息來建立網(wǎng)頁索引數(shù)據(jù)庫文件。 4 、在用戶檢索階段，首先用戶在搜索入口頁面輸入查詢詞，然后搜索引擎的檢索 程序從索引文件庫中找到與該查詢詞匹配的網(wǎng)頁，并按照一定的網(wǎng)頁排序算法將搜索結(jié) 果呈現(xiàn)給用戶，搜索結(jié)果中除了提供網(wǎng)頁標題和u r l 之外，還會顯示一些與網(wǎng)頁有關(guān) 的摘要信息等，方便用戶查詢到所需的網(wǎng)頁。 搜索引擎主要分為三類，即目錄索引搜索引擎、全文索引搜索引擎和元搜索引擎【_ 7 1 。 1 、目錄索引是以人工或半自動方式進行信息搜集后，由人工對搜集到的信息進行 整理并形成摘要，接著將摘要信息存放到預(yù)先確定好的分類當(dāng)中。從嚴格意義上來說， 目錄索引不能算作真正的搜索引擎，它只是按照一定的目錄分類羅列出網(wǎng)站鏈接而已， 用戶可以不用進行關(guān)鍵詞查詢，而只需在分類目錄去尋找所需要的信息即可，其中最具 代表性的是雅虎和新浪分類目錄搜索。 2 、全文索引搜索引擎是真正意義上的搜索引擎，它們利用網(wǎng)絡(luò)蜘蛛程序爬取互聯(lián) 網(wǎng)的網(wǎng)頁信息，然后建立相應(yīng)的索引數(shù)據(jù)庫，并能根據(jù)用戶的查詢詞對索引庫中進行檢 索，找到與查詢詞相匹配的記錄，接著按一定的排列順序返回給用戶相應(yīng)結(jié)果，g o o g l e 和百度就屬于此類的典型代表。 3 、元搜索引擎也叫集合型搜索引擎，它們沒有自己的數(shù)據(jù)庫，而是將用戶的查詢 廣西大學(xué)碩士學(xué)位論文n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 請求同時發(fā)送給多個搜索引擎，然后對返回的結(jié)果進行去重和排序等處理后呈現(xiàn)給用 戶。國外著名的元搜索引擎有v i v i s i m o 、d o g p i l e 和i n f o s p a c e 等，國內(nèi)元搜索引擎的典 型代表是搜星搜索引擎。 1 3 搜索引擎網(wǎng)頁排序算法的研究現(xiàn)狀 1 3 1 搜索引擎排序技術(shù)的研究發(fā)展 在當(dāng)今信息化社會，互聯(lián)網(wǎng)遍布整個世界，搜索引擎也在高速發(fā)展，越來越多的網(wǎng) 民使用搜索引擎提供的檢索服務(wù)，讓搜索引擎成為互聯(lián)網(wǎng)的熱點之一。根據(jù)c n n i c 調(diào) 查顯示【8 】= 在網(wǎng)民使用的網(wǎng)絡(luò)服務(wù)中，搜索引擎所占比例由一年前的5 7 8 上升到6 8 5 ；在網(wǎng)民獲得新網(wǎng)站途徑中，搜索引擎所占比例由一年前的7 5 6 上升到8 7 5 ； 在網(wǎng)民獲取網(wǎng)絡(luò)信息方法中，搜索引擎所占比例由一年前的6 3 8 增長到7 2 6 。從搜 索引擎的發(fā)展變化可以看出，搜索引擎的排序技術(shù)成為其決定因素和劃分標準。g o o g l e 因為擁有其發(fā)明的p a g e r a n k 排序技術(shù)，成為全世界使用最廣泛的搜索引擎；百度因為 擁有其獨創(chuàng)的超鏈接分析排序技術(shù)，成為全球最知名的中文搜索引擎。 因此，如果按照排序技術(shù)劃分【9 】，搜索引擎可分為如下三類： l 、基于詞頻統(tǒng)計排序的搜索引擎 這種搜索引擎是由情報檢索理論發(fā)展過來的，該理論認為網(wǎng)頁出現(xiàn)檢索詞的頻率越 高，位置越重要，則網(wǎng)頁和檢索詞的相關(guān)性越好。詞頻加權(quán)的方法有以下幾種，即絕對 詞頻或相對詞頻加權(quán)、基于詞分辨值加權(quán)和反詞頻加權(quán)等。例如，對某個詞在網(wǎng)頁中出 現(xiàn)的頻率來給定權(quán)值，其中可對出現(xiàn)頻率高的詞賦予較低的初始值，而對出現(xiàn)頻率低的 詞賦予較高的初始值。詞位置加權(quán)中的權(quán)值與檢索詞在頁面中出現(xiàn)的位置和版式有關(guān)， 網(wǎng)頁和檢索詞的相關(guān)度由權(quán)值大小來決定。其中，詞的位置可以包括網(wǎng)頁的標題、網(wǎng)頁 的摘要、正文的標題或內(nèi)容、錨文本等，版式是指網(wǎng)頁的字體類型、字號大小、文字粗 細等等。例如，可對網(wǎng)頁標題或摘要中出現(xiàn)的詞以及對網(wǎng)頁中字號較大或加粗的詞賦予 較大的權(quán)值等。 詞頻統(tǒng)計具有簡易實用的優(yōu)點，是目前發(fā)展最成熟的技術(shù)之一，并成為搜索引擎排 序技術(shù)的基礎(chǔ)。缺點是沒有充分利用網(wǎng)頁特性，也許會出現(xiàn)這樣一種情況，兩個網(wǎng)頁的 詞頻相同，但它們的質(zhì)量卻天差地別。另外，也會出現(xiàn)某些網(wǎng)站故意在網(wǎng)頁中堆積大量 關(guān)鍵詞來提高網(wǎng)頁排名的作弊行為，目前，搜索引擎的設(shè)計者已經(jīng)采取了很多措施來對 這種作弊行為進行治理和處罰。 2 、基于鏈接分析排序的搜索引擎 這種搜索引擎是由文獻引用思想發(fā)展而來，該思想中認為一篇好論文的標準是被許 多高質(zhì)量的論文引用，引用次數(shù)越多就說明該論文越好越權(quán)威。于是，網(wǎng)頁鏈接分析也 借鑒了文獻引用的思想，認為一個好網(wǎng)頁的標準是被許多高質(zhì)量的網(wǎng)頁鏈接，鏈接次數(shù) 越多就說明該網(wǎng)頁越好越重要。1 9 9 8 年誕生了兩個基于超鏈接分析的經(jīng)典網(wǎng)頁排序算 n u t c h 拽索引擎中網(wǎng)頁排序技術(shù)的研究 法，分別由l a r r yp a g e 和s e r g e yb r i n 提出的p a g e r a n k 算法以及由k l e i n b e r g 提出的h i t s 算法，它們又分別被應(yīng)用到g o o s e 搜索引擎以及i b m 的c l e v e r 智能系統(tǒng)中。 p a g e r a n k 算法【1 0 】體現(xiàn)了“民主選舉”的思想。首先，該算法認為網(wǎng)頁x 鏈向網(wǎng)頁y 即表示x 給y 投了一票，然后統(tǒng)計出每個網(wǎng)頁的得票數(shù)，票數(shù)越多的網(wǎng)頁就被認為是 重要權(quán)威的網(wǎng)頁。另外，除了統(tǒng)計網(wǎng)頁的得票數(shù)( 鏈接數(shù)) 外，還要考慮選票的“含金量”， 即為某網(wǎng)頁投票的網(wǎng)頁是否重要權(quán)威，可想而知，權(quán)威網(wǎng)頁就如權(quán)威人物一樣，投出的 票自然具有較高的價值，獲得這些選票的網(wǎng)頁的重要性自然也提高了。因此，某網(wǎng)頁要 想取得“選舉”的勝利，就必須獲得很多的投票數(shù)( 鏈接數(shù)) ，并且選票的質(zhì)量( 投票網(wǎng)頁的 權(quán)威性1 越高越好。 p a g e r a n k 算法如公式( 1 1 ) 所示【1 1 】，其中p r ( 是網(wǎng)頁【，的p a g e r a n k 值，p r ( z i ) 是 鏈向網(wǎng)頁u 的網(wǎng)頁v i 的p a g e r a n k 值，c ( 功是網(wǎng)頁所的鏈出數(shù)量，d 為阻尼系數(shù)( 脈1 ) 。 p r ( u ) = ( 1 一d ) + d ( 尸r ( k ) c ( k ) + p r ( v 2 ) c ( v j ) + + 尸尺( 圪) c ( 圪) )( 1 1 ) 由此可知：( 1 ) p a g e r a n k 計算對象是單個網(wǎng)頁，網(wǎng)頁u 的p a g e r a n k 值主要由鏈向 u 的所有網(wǎng)頁的p a g e r a n k 遞歸值確定；( 2 ) 如果網(wǎng)頁m 的鏈出數(shù)越多，則網(wǎng)頁u 受到 所鏈接的影響就越小：( 3 ) p r ( 是所有p r ( v i ) x t 力i 而求得，因此網(wǎng)頁u 的入鏈越多，p r ( 的值越大：( 4 ) 阻尼系數(shù)d 值設(shè)置為0 到1 ，一般取值0 8 5 ，它可以削弱其它網(wǎng)頁對網(wǎng)頁 u 的鏈入貢獻值。 h i t s 算法【1 2 】將網(wǎng)頁分成具有相互加強作用的兩類，一類是具有較高價值的權(quán)威網(wǎng) 頁( a u t h o r i t y ) ，依賴于鏈向它的網(wǎng)頁：另一類是指向較多權(quán)威網(wǎng)頁的中心網(wǎng)頁( h u b ) ，依 賴于它鏈向的網(wǎng)頁。該算法主要包括兩個過程：( 1 ) 生成網(wǎng)頁鏈接子圖，即根據(jù)查詢詞 從檢索結(jié)果中取前n 個網(wǎng)頁構(gòu)成根集s ，向s 中添加被s 引用和引用s 的網(wǎng)頁擴充成 集合t ，利用t 中的網(wǎng)頁以及網(wǎng)頁間的鏈接構(gòu)成網(wǎng)頁鏈接子圖g ：( 2 ) 計算網(wǎng)頁的a u t h o r i t y 和h u b 值，首先把g 中各網(wǎng)頁的a u t h o r i t y 和h u b 值初始化為1 ，然后進行i o 操作迭代 計算并作規(guī)范化處理，直到結(jié)果收斂獲得各網(wǎng)頁的a u t h o r i t y 和h u b 值?？傊槍δ硞€ 查詢詞，h i t s 算法通過迭代計算方法找到價值( a u t h o r i t y ) 高的網(wǎng)頁，可以取得較好的 查全率，并輸出一組較大權(quán)威值和中心值的網(wǎng)頁。 鏈接分析排序算法的優(yōu)點是在詞頻統(tǒng)計的基礎(chǔ)上更注重排序結(jié)果的重要性和權(quán)威 性。但是，也出現(xiàn)了某些網(wǎng)頁設(shè)計者為了提高在搜索引擎的排名，利用對網(wǎng)頁進行鏈接 添加、鏈接交換或者鏈接欺騙等手段進行作弊的現(xiàn)象，從而導(dǎo)致用戶很難搜索到一些內(nèi) 容質(zhì)量高卻沒有很多鏈接的網(wǎng)頁。另外，鏈接分析的算法缺點是純粹地基于鏈接分析來 發(fā)現(xiàn)權(quán)威網(wǎng)頁，而沒有充分考慮網(wǎng)頁的具體內(nèi)容，存在所謂的“主題漂移( t o p i cd r i f t ) ”l i 刊 問題，即算法的結(jié)果中往往包含一些相互鏈接密度較高但在內(nèi)容上卻偏離了查詢主題的 網(wǎng)頁。 3 、基于智能化排序的搜索引擎 到目前為止，大多數(shù)商業(yè)搜索引擎都是在基于詞頻統(tǒng)計和鏈接分析排序技術(shù)的基礎(chǔ) 廣西大學(xué)碩士學(xué)位論文 n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 上進行不斷完善和優(yōu)化，并在朝著智能化排序的方向發(fā)展【1 4 1 。百度提出的競價排名服務(wù) 是收費排名的一種，先由客戶為自己的網(wǎng)頁向百度購買關(guān)鍵字排名，然后百度對該網(wǎng)頁 的點擊量進行計費【1 5 , 1 6 。但是，收費排名的結(jié)果排序缺乏真實性并有失公正性，不能算 是智能化排序。 真正意義上的智能化排序應(yīng)包括如下幾個方面 i7 】：個性化排序、基于語義排序、基 于主題排序以及智能去重排序等。其中，個性化排序是通過用戶反饋來提高排序準確性， 在搜索引擎不斷“學(xué)習(xí)”到用戶的行為模式后，使其越來越滿足用戶的需求?；谡Z義排 序時通過運用自然語言識別和人工智能等多方面的技術(shù)把關(guān)鍵詞級別映射到概念級別， 并結(jié)合上下文內(nèi)容分析和近義詞、同義詞、多義詞處理技術(shù)，不斷增加對檢索詞和網(wǎng)頁 之間的語義相關(guān)度的理解和分析?；谥黝}排序則使排序結(jié)果更趨向于某個主題，是垂 直搜索引擎技術(shù)中的關(guān)鍵。智能去重排序是自動識別檢索結(jié)果中重復(fù)的網(wǎng)頁或網(wǎng)站，然 后進行智能過濾和去重。另外，基于多媒體信息的檢索排序技術(shù)也是搜索引擎未來要發(fā) 展的方向。 1 3 2 基于鏈接分析的改進算法 為了有效的抑制基于鏈接分析算法的“主題漂移”現(xiàn)象，出現(xiàn)了一些基于超鏈接和內(nèi) 容的網(wǎng)頁排序算法，在鏈接分析的基礎(chǔ)上引入網(wǎng)頁內(nèi)容信息的影響因素，它們都是在 p a g e r a n k 算法和h i t s 算法兩個經(jīng)典的算法基礎(chǔ)上進行改進的。 1 、h i l l t o p 算法【1 8 】是2 0 0 1 年由g o o g l e 的工程師b h a r a t 對p a g e r a n k 算法進行的改 進。該算法更注重計算來自具有相同主題的網(wǎng)頁鏈接，認為主題相同或相關(guān)的網(wǎng)頁之間 的鏈接比主題不相關(guān)的鏈接價值要更高。例如，如果某網(wǎng)頁是有關(guān)“體育”的，那么對于 那些鏈入該網(wǎng)頁的有關(guān)“體育”的網(wǎng)頁鏈接就比有關(guān)“軍事”的網(wǎng)頁鏈接的貢獻價值要大 些。影響主題的網(wǎng)頁稱為專家網(wǎng)頁，這些網(wǎng)頁決定被鏈接網(wǎng)頁的權(quán)重得分。另外，h i l t o p 算法有效解決了某些試圖通過增加大量無效鏈接來提高網(wǎng)頁排名的作弊問題。 2 、c a t e g o r y r a n k 算法f 1 9 】將分類技術(shù)融入到排序算法中，在加入類別信息后能獲得 更加準確的排序結(jié)果，它克服了p a g e r a n k 算法與查詢詞無關(guān)的缺點，具有讓相同或者 相似類別的網(wǎng)頁更加相關(guān)的優(yōu)點。該算法從三方面把分類技術(shù)應(yīng)用到搜索引擎的排名當(dāng) 中：( 1 ) 對每一個鏈接，把所鏈接網(wǎng)頁的類別信息加權(quán)到p a g e r a n k 值中，轉(zhuǎn)變成基于鏈 接的c a t e g o r y r a n k 算法；( 2 ) 在所有網(wǎng)頁中，計算每種類別的c a t e g o r y r a r t k 向量；( 3 ) 對用戶查詢關(guān)鍵詞進行分類，結(jié)合查詢記錄以及個人愛好等信息來獲取用戶的興趣類 別，并根據(jù)離線計算結(jié)果來提高網(wǎng)頁排名的準確性?？傊?，該算法同時考慮了鏈接的類 別相關(guān)性和網(wǎng)頁的類別差異，最后把每個網(wǎng)頁的類別信息都集成進來。 3 、s p a g e r a n k 算澍2 0 ，2 1 】提出在鏈接分析的基礎(chǔ)上加入相關(guān)的語義信息權(quán)重，產(chǎn)生 針對某個主題的重要網(wǎng)頁。該算法指出p a g e r a n k 算法不是面向某個主題的缺陷，引入 相關(guān)度分析，著重研究與利用一個由大量主題相關(guān)的網(wǎng)頁群指向的網(wǎng)頁p a g e r a n k 值比 一個由少量主題相關(guān)的網(wǎng)頁群指向的網(wǎng)頁p a g e r a n k 值高的現(xiàn)象。另外，把s p a g e r a n k 廣西大掌碩士掌位論文 n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 算法和h i t s 算法結(jié)合起來形成f p a g e r a n k 算法，用于迭代計算網(wǎng)頁的h u b 和a u t h o r i t y 值，該算法基本思想是出站鏈接多的網(wǎng)頁具有較高的h u b 值，而入站鏈接多的網(wǎng)頁具有 較高的a u t h o r i t y 值。當(dāng)上網(wǎng)瀏覽者對某個網(wǎng)頁感到厭倦時，一般會選擇出度或入度大的 網(wǎng)頁繼續(xù)瀏覽，所以這些網(wǎng)頁應(yīng)比隨機瀏覽的網(wǎng)頁具有更高的得分。 4 、融入鏈接相關(guān)度p a g e r a n k 算法的【2 2 ，2 3 】認為網(wǎng)頁中各個鏈接不是平等的，而是存 在競爭的。為了實現(xiàn)鏈接之間的競爭性，該算法對鏈接標題內(nèi)容( 錨文本) 和其所指向網(wǎng) 頁的內(nèi)容進行相關(guān)度計算。算法基本思想是：( 1 ) 如果網(wǎng)頁x 鏈向網(wǎng)頁y ，鏈接標題內(nèi) 容與網(wǎng)頁y 內(nèi)容相關(guān)度越高，x 對y 的貢獻越大；( 2 ) 把所有對網(wǎng)頁y 有貢獻的網(wǎng)頁 p a g e r a n k 值相加求和作為y 的p a g e r a n k 值。該算法在保持p a g e r a n k 算法計算效率基 礎(chǔ)上，進一步改善了網(wǎng)頁評分，并在智能和語義排序方面做出了新的嘗試。 5 、a r c 算法【2 4 】是由i b m 的c l e v e r 研究小組提出，它是在h i t s 算法的基礎(chǔ)上考 慮了網(wǎng)頁鏈接錨文本信息對網(wǎng)頁排序的影響。h i t s 算法在計算a u t h o r i t y 和h u b 值時， 平等對待網(wǎng)頁之間的各個鏈接，而事實上每個鏈接的重要性是不相同的。該算法充分利 用了鏈接錨文本和搜索主題之間的相關(guān)度來給予鏈接不同的重要性，并根據(jù)各鏈接的重 要性權(quán)值重新構(gòu)建一個矩陣，取代原來的網(wǎng)頁鏈接子圖鄰接矩陣來計算網(wǎng)頁的a u t h o r i t y 和h u b 值。 6 、a v e r a g e 算法【2 5 】和s i m 算法f 2 6 】分別由j g e v r e y 和s r u g e r 提出的基于超鏈接和 內(nèi)容的網(wǎng)頁排序算法。它們與h i t s 算法的不同之處在于：( 1 ) 在向搜索引擎提交查詢詞 并獲取網(wǎng)頁根集的過程中，h i t s 算法忽略了每個頁面與查詢詞的相似度s i m i l a r i t y 值， 只是利用網(wǎng)頁鏈接信息來計算網(wǎng)頁的a u t h o r i t y 和h u b 值。但是，a v e r a g e 和s i m 算法卻 利用了s i m i l a r i t y 值來計算網(wǎng)頁的a u t h o r i t y ：( 2 ) 在對網(wǎng)頁的a u t h o r i t y 和h u b 值進行迭代 計算時，h i t s 算法需要迭代計算若干次直到結(jié)果收斂，而a v e r a g e 算法和s i m 算法只 需考慮相鄰網(wǎng)頁對結(jié)果的影響，它們的迭代計算次數(shù)僅為l 。 1 3 3 搜索引擎綜合排序模型 搜索引擎綜合排序模型是建立在現(xiàn)有的排序算法和技術(shù)基礎(chǔ)之上，將現(xiàn)有的排序技 術(shù)優(yōu)化并結(jié)合起來應(yīng)用到搜索引擎排序模型中。國外對綜合排序模型已有不少研究，在 國內(nèi)北京大學(xué)的天網(wǎng)搜索引擎項目在綜合排序模型方面做出了理論和實驗的探索，并在 天網(wǎng)中建t w e b g a t h e r t 2 1 7 】的排序模型，該模型包含三個重要因素：網(wǎng)頁內(nèi)容、網(wǎng)頁鏈 接、用戶行為，它們共同決定網(wǎng)頁的最終權(quán)重。 ( 1 ) 網(wǎng)頁內(nèi)容。一個關(guān)鍵詞的權(quán)重由網(wǎng)頁標簽權(quán)重、網(wǎng)頁大小權(quán)重和關(guān)鍵詞頻率權(quán)重 構(gòu)成。在經(jīng)典的t f * i d f 算法中加入文件長度因子，并賦予頻繁出現(xiàn)在規(guī)模小的網(wǎng)頁集中 的關(guān)鍵詞更高的權(quán)重。 。 ( 2 ) 網(wǎng)頁鏈接。在網(wǎng)頁鏈接中只考慮異網(wǎng)站鏈接數(shù)目，并賦予新網(wǎng)頁一定的權(quán)重補償， 因為新網(wǎng)頁剛開始的點擊量往往較少。 ( 3 ) 用戶行為。當(dāng)用戶輸入查詢詞并獲得搜索結(jié)果后，先查看網(wǎng)頁的摘要信息，當(dāng)用 n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 戶找到與查詢相關(guān)的摘要時，就點擊其超鏈接來訪問網(wǎng)頁。通常用戶只會瀏覽搜索結(jié)果 中的前幾頁，因此較難被瀏覽和點擊并排在后面的搜索結(jié)果，應(yīng)給這些后面的結(jié)果相應(yīng) 的權(quán)重補償。 在計算最終網(wǎng)頁權(quán)重時，w e b g a t h e r 采用了綜合指數(shù)法對網(wǎng)頁內(nèi)容基本權(quán)值、鏈接 權(quán)值以及用戶評價權(quán)值三個指標進行加權(quán)求和，即人為指定加權(quán)因子的比例，帶有一定 的主觀因素。總之，w e b g a t h e r 模型考慮到了三種主要的相關(guān)性排序技術(shù)并加以綜合， 在每一種相關(guān)性排序技術(shù)中，又給出了具體的方法并進行優(yōu)化，是一個相對完備的綜合 模型【2 8 1 。 1 4 論文研究的目的和意義 目前，搜索引擎已經(jīng)成為人們獲取網(wǎng)絡(luò)信息的主要工具。其中，搜索引擎網(wǎng)頁排序 算法決定了搜索引擎的成敗，是商業(yè)搜索引擎的關(guān)鍵部分與核心機密，因此成為廣大學(xué) 者研究的熱點之一。 研究搜索引擎網(wǎng)頁排序的目的就是從很多搜索結(jié)果中將內(nèi)容相關(guān)和權(quán)威的網(wǎng)頁排 在前面呈現(xiàn)給用戶，幫助用戶迅速地定位所需要的資源。目前的搜索引擎利用詞頻和詞 位置統(tǒng)計排序技術(shù)來解決網(wǎng)頁內(nèi)容與查詢的相關(guān)性問題，利用p a g e r a n k 和h i t s 等鏈接分 析排序算法來解決判定網(wǎng)頁權(quán)威性問題。在大量的網(wǎng)頁搜索結(jié)果中，如果只采用內(nèi)容相 關(guān)性排序算法，則仍會得到大量的結(jié)果并無法保障網(wǎng)頁的重要性；如果只采用鏈接分析 排序算法，則會存在主題漂移等問題并無法保證查詢結(jié)果的相關(guān)性【2 9 】。因此，只有通過 設(shè)計實現(xiàn)搜索引擎網(wǎng)頁綜合排序模型，才能滿足用戶對查詢結(jié)果的相關(guān)性和權(quán)威性的綜 合需求。 由于商業(yè)搜索引擎的網(wǎng)頁排序算法是核心機密，無法得知其中的實現(xiàn)細節(jié)，而j a v a 開源代碼實現(xiàn)的n u t c h 搜索引擎卻為學(xué)者研究提供了很好的選擇。但是，由于n u t c h 開發(fā) 目的是以搜索引擎技術(shù)交流為主，功能實現(xiàn)方面與商業(yè)搜索引擎存在一定的差距，目前 只實現(xiàn)了一個基本的綜合排序模型，包含基于內(nèi)容相關(guān)性分析以及簡單的網(wǎng)頁鏈接分析 排序算法，并沒有實現(xiàn)經(jīng)典的p a g e r a n k 算法，而通常的p a g e r a n k 串行算法在計算大量網(wǎng) 頁p a g e r a n k 值時也存在效率低下的問題。因此，為了使n u t c h 更好地滿足搜索引擎的實 際應(yīng)用要求，在n u t c h q b 設(shè)計并實現(xiàn)一種高效的p a g e r a n k 并行算法，然后進一步改進它 的綜合排序模型，這樣做具有一定的研究意義和較高的實用價值。 1 5 論文的主要工作和組織結(jié)構(gòu) 論文的主要工作如下： 1 、分析了國內(nèi)外搜索引擎網(wǎng)頁排序算法的發(fā)展現(xiàn)狀，研究基于鏈接分析排序算法， 重點對經(jīng)典的p a g e r a n k 算法進行深入研究，熟悉其計算原理與實現(xiàn)方法，分析算法的 缺點與不足。 n u t c h 搜索引擎中網(wǎng)頁排序技術(shù)的研究 2 、熟悉開源搜索引擎n u t c h 的組成結(jié)構(gòu)，研究其基于m a p r e d u c e 的并行計算模型 以及分布式文件系統(tǒng)h d f s ，并對其基于l u c e n e 的網(wǎng)頁綜合排序模型進行深入研究， 分析模型中存在的不足。 3 、針對目前n u t c h 搜索引擎中沒有實現(xiàn)p a g e r a n k 計算的問題，利用m a p r e d u e e 并行計算機制處理大數(shù)據(jù)集的優(yōu)勢，在n u t c h 機群系統(tǒng)上設(shè)計和實現(xiàn)了基于m a p r e d u e e 的p a g e r a n k 分布式并行算法。實驗結(jié)果表明：處理的數(shù)據(jù)量越大，機群中的節(jié)點越多， 計算p a g e r a n k 的效率越高；另外，該分布式并行算法具有較好的可擴展性。 4 、針對目前n u t c h 對中文進行單字切分的問題，加入了j e 中文分詞器對n u t c h 的 中文分詞進行改進。在分析和研究經(jīng)典p a g e r a n k 算法原理的基礎(chǔ)上，通過設(shè)置控制站 外與站內(nèi)鏈接的比重因子對該算法進行了改進。為了改進n u t c h 基于l u c e n e 的網(wǎng)頁綜 合排序模型，將改進后的p a g e r a n k 算法因子融入到n u t c h 網(wǎng)頁評分計算公式當(dāng)中。實 驗表明，改進后n u t c h 明顯提高了查詢結(jié)果的準確率，改善了中文網(wǎng)頁的排序效果。 論文共分為5 章，各章節(jié)主要內(nèi)容如下： 第一章緒論。簡述了搜索引擎的分類與基本原理，主要介紹了搜索引擎網(wǎng)頁排序 算法的研究現(xiàn)狀，引出了論文的研究意義和主要工作。 第二章n u t c h 搜索引擎技術(shù)介紹。介紹了l u c e n e 與n u t c h 的關(guān)系，并對n u t c h 的 組成與工作流程進行了簡單說明，并介紹n u t c h 中的m a p r e d u c e 并行算法思想以及分 布式文件系統(tǒng)h d f s ，最后介紹n u t c h 中的的并行計算機制與機群部署。 第三章n u t c h 中p a g e r a n k 算法的并行實現(xiàn)。介紹p a g e r a n k 的迭代計算原理并通 過簡單實驗進行驗證，然后詳細介紹了在n u t c h 中基于m a p r e d u e e 的p a g e r a n k 并行算 法實現(xiàn)過程，通過實驗說明該算法有效提高了p a g e r a n k 的計算效率。 第四章n u t c h 中