（計算機應(yīng)用技術(shù)專業(yè)論文）中文搜索引擎robot技術(shù)研究與實現(xiàn).pdf

中文搜索引擎r o b o t 技術(shù)研究與實現(xiàn) 何淑慶( 計算機應(yīng)用技術(shù)) 指導(dǎo)教師：李村合( 教授) 摘要 r o b o t 是搜索引擎的關(guān)鍵技術(shù)之一，它已經(jīng)發(fā)展為- - n 涉及人工智 能、計算機網(wǎng)絡(luò)、分布式處理、數(shù)據(jù)庫、數(shù)據(jù)挖掘、自然語言處理等多 領(lǐng)域的理論和技術(shù)。隨著w e b 信息的爆炸式增長和人們對信息服務(wù)要求 的提高，人們期待r o b o t 的搜集性能越來越強。當(dāng)前提高r o b o t 性能最 有效的方法是采用分布式技術(shù)，但是這會產(chǎn)生一些新的問題，如u r l 劃分策略、u r l 匹配方式、負載平衡、擴展性和健壯性等?；诜植际?技術(shù)的研究，給出了一個基于u r l 分級散列機制的中文w e b 信息搜集 系統(tǒng)( 簡稱u c h s 系統(tǒng)) ，為了解決上述問題，在該系統(tǒng)中運用了新的 設(shè)計方案、u r l 劃分策略和匹配算法；針對中文w e b 信息搜集這一特點， 提到了一些有價值的搜索策略和方法。首先介紹了課題的研究背景、意 義和研究內(nèi)容，給出了全文的組織結(jié)構(gòu)。其次對搜索引擎及其關(guān)鍵部分 r o b o t 技術(shù)進行了全面的分析研究，從搜索引擎的歷史、分類、工作原 理、評價標(biāo)準(zhǔn)和發(fā)展趨勢等五個方面對搜索引擎作了全面的闡述。再次 從種類、搜索策略、更新策略等問題入手重點分析了r o b o t 技術(shù)，并指 出當(dāng)前r o b o t 技術(shù)面臨的問題。在此基礎(chǔ)上，給出了u c h s 系統(tǒng)。針對 采用分布式技術(shù)帶來的新問題，提出了基于u r l 分級散列定位和匹配的 方案，并為之設(shè)計了兩種適用于中文w e b 信息搜集的u r l 散列函數(shù)。 為了進一步提高中文w e b 信息搜集的性能，提出了基于域名的u r l 過 濾技術(shù)、基于首頁內(nèi)容的中文網(wǎng)站識別技術(shù)、基于首頁的搜索策略和基 于內(nèi)容變化度的更新策略等技術(shù)和策略?；谏鲜鲅芯砍晒?，給出了 u c h s 系統(tǒng)的設(shè)計模型以及實現(xiàn)中的相關(guān)技術(shù)，并通過j a v a 語言測試其 具體性能。實驗結(jié)果表明，u c h s 系統(tǒng)具有很好的u r l 匹配性能和負載 均衡性能。最后總結(jié)全文工作，指出了該文的創(chuàng)新點和下一步的研究工 作，并展望了r o b o t 技術(shù)的發(fā)展方向。 關(guān)鍵詞：搜索引擎，r o b o t ，分布式，中文w e b 信息，u c h s 系統(tǒng) s t u d ya n di m p l e m e n t a t i o no fr o b o tf o rc h i n e s es e a r c h e n g i n e h e s h u - q i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g ) ，) d i r e c t e db yp r o f e s s o rl ic u n - h e a b s t r a c t r o b o ti so d eo ft h ek e yc o m p o n e n t so fs e a r c he n g i n e s ，w h i c hi sc l o s e l y r e l a t e dt om a n yf i e l d ss u c ha sa r t i f i c i a li n t e l l i g e n c e , c o m p u t e rn e t w o r k s , d i s t r i b u t e dp r o c e s s i n g ，d a t a b a s e ，d a t am i n i n ga n dn a t u r a ll a n g u a g ep r o c e s s i n g w i t ht h ee x p l o s i v eg r o w t ho fw e bi n f o r m a t i o na n dt h er i s eo fd e s i r ef o r i n f o r m a t i o ns e r v i c e ，p e o p l ea r el o o k i n gf o r w a r dt oe n h a n c i n gt h ea b i l i t yo f t h ei n f o r m a t i o nc o l l e c t i n g t oa c h i e v et h i s g o a l ，t h ei m p l e m e n to ft h e d i s t r i b u t e dt e c h n o l o g yi st h em o s ta v a i l a b l ew a yf o rt h em o m e n t ，h o w e v e r , i t a l s ob r i n g sa b o u ts o m en e wp r o b l e m s m a i n l yi n c l u d i n gu r ld i v i s i o n s t r a t e g y , u r lm a t c h i n g ，l o a db a l a n c i n g , e x p a n s i o na n dr o b u s t b a s e do n d i s t r i b u t e dt e c h n i c a lr e s e a r c h , t h i s p a p e rd e s i g n s t h ec h i n e s ew e b i n f o r m a t i o nc o l l e c t i n gs y s t e mb a s e do nt h ep r o j e c to f h a s h i n gc l a s s i f i c a t i o n s u r l ( u c h ss y s t e m ) ，i no r d e rt os o l v et h ea b o v ep r o b l e m s ，t h e r ea r en e w d e s i g np r o p o s a l ，u r ld i v i s i o ns t r a t e g ya n du r lm a t c h i n ga l g o r i t h mi nt h i s s y s t e m ；i th a sm e n t i o n e ds e m ev a l u a b l es e a r c hs t r a t e g i e sa n dt h em e t h o d si n v i e wo fc o l l e c t i n gc h i n e s ew e bi n f o r m a t i o n a tf i r s t , t h i sp a p e ri n t r o d u c e s t h eb a c k g r o u n da n ds i g n i t i c a n c eo ft h et o p i ca n dt h er e s e a r c hc o n t e n t ，f i s t s t h eo r g a n i z a t i o n a ls t r u c t u r eo ft h ep a p e r s e c o n d , i tm a k e sc o m p r e h e n s i v e a n a l y s i st o s e a r c he n g i n e sa n dr o b o to fi t sc r i t i c a lt e c h n o l o g y , m a k e s c o m p r e h e n s i v ee l a b o r a t i o nt os e a r c he n g i n e si nf i v ea s p e c t s ：t h eh i s t o r y ，t h e c l a s s i f i c a t i o n , t h ep r i n c i p l eo fw o r k , t h ee v a l u a t i o nc r i t e r i aa n dt h et e n d e n c y t h e ni t a n a l y z e sr o b o tt e c h n o l o g yw i t he m p h a s i si nt h r e ea s p e c t s ：t y p e ， s e a r c hs t r a t e g ya n du p d a t es t r a t e g y , a n dp o i n t e so u tt h es h o r t a g eo fr o b o t o nt h eb a s i so ft h i s ，t h eu c h ss y s t e mf o r c o l l e c t i n g c h i n e s ew e b i n f o r m a t i o ni sd e s i g n e d r e s p o n s et ot h ep r o b l e mi nu s i n gt h ed i s t r i b u t e d t e c h n o l o g y ，t h ed e s i g no f u c h ss y s t e mi sb a s e d o nt h ep r o j e c to f p o s i t i o n i n g a n dm a t c h i n go n h a s h i n gc l a s s i f i c a t i o n su r l ，a n dd e s i g n st w ou r lh a s h i n g f u n c t i o n sf o ri t t oi m p r o v et h ea b i l i t yo fr o b o t , s o m en e ws t r a t e g i e sa n d t e c h n o l o g i e sa r ed e s i g n e d , i n c l u d i n gf i l t e rb a s e do rd o m a i n , r e c o g n i z eb a s e d o nh o m ep a g e , s e a r c hs t r a t e g yb a s e do nh o m ep a g ea n du p d a t e ds t r a t e g y b a s e do nt h em t eo f c h a n g i n gc o n t e n t s b a s e do nt h ea b o v er e s e a r c hr e s u l t s ， t h em o d e lo fu c h ss y s t e mi s d e s i g n e da n dt h er e l a t e dt e c h n o l o g yo f i m p l e m e n t a t i o n si sa n a l y z e d , a n di t sc a p a b i l i t yi st e s t e db yp r o g r a m m i n g t h ee x p e r i m e n t a ld a t ai n d i c a t e dt h a t , t h eu c h ss y s t e mh a sb e t t e r p e r f o r m a n c e si nt w of i e l d s ：u r lm a t c h i n ga n dl o a db a l a n c i n g f i n a l l y ，i t p o i n t e so u tt h ei n n o v a t i o n sa n df u l 恤o rr e s e a r c hw o r k , a n df o r e c a s t st h e t r e n d o f r o b o tt e c h n o l o g y k e yw o r d s ：s e a r c he n g i n e ，r o b o t , d i s t r i b u t e d , c h i n e s ew e b i n f o r m a t i o n , u c h ss y s t e m 獨創(chuàng)性聲明 本人聲明所呈交的論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取 得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論 文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得中國 石油大學(xué)或其它教育機構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作 的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示了 謝意。 簽名：! 墨塑塞2 0 0 6 年0 4 月0 1 日 關(guān)于論文使用授權(quán)的說明 本人完全了解中國石油大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即； 學(xué)校有權(quán)保留送交論文的復(fù)印件及電子版，允許論文被查閱和借閱；學(xué) ?？梢怨颊撐牡娜炕虿糠謨?nèi)容，可以采用影印、縮印或其他復(fù)制手 段保存論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 學(xué)生簽名：! 要塑壅伽年斗月；。 日 導(dǎo)師簽名：豸瞼伽。6 年4 -月弓d 日 中國石油大學(xué)( 華東) 碩士論文第1 章前言 第l 章前言 1 1 課題的背景 隨著i n t e m e t 信息的爆炸性增長，搜索引擎作為一種網(wǎng)絡(luò)信息導(dǎo)航的 工具，它的地位日益重要。數(shù)據(jù)顯示2 0 0 4 年中國8 0 的互聯(lián)網(wǎng)用戶使用 搜索引擎，用戶數(shù)量為8 0 0 0 萬，根據(jù)數(shù)據(jù)推測到2 0 0 7 年中國將有9 1 的互聯(lián)網(wǎng)用戶使用搜索引擎，而用戶數(shù)量達到2 0 5 億【”。當(dāng)前，對搜索 引擎的研究越來越深入，搜索引擎也由最初的f t p 上的文件搜索演變?yōu)?今天各種特色的搜索引擎，如面向?qū)ｎ}的搜索引擎、基于個性化的搜索 引擎、基于移動代理的搜索引擎等i 卅。查準(zhǔn)率是評價搜索引擎的一個重 要指標(biāo)舊，隨著n t e m e t 信息量的增長，它的重要性不斷提升。因此當(dāng)前 圍繞搜索引擎的研究多數(shù)將目標(biāo)放在提高它的查準(zhǔn)率上，主要研究集中 在信息檢索，信息聚類、相關(guān)性計算、數(shù)據(jù)挖掘、人工智能等方面，以 便使人們獲得更理想的查詢結(jié)果。另一方面，為了緩解了i n t e r n e t 信息量 的增長給信息搜集工作帶來的巨大壓力，各種特色的搜索引擎將搜集的 信息范圍縮小到特定的區(qū)域。 在各種搜索引擎不斷涌現(xiàn)的同時，傳統(tǒng)搜索引擎依然占據(jù)著搜索引 擎主流的地位。美國知名投資銀行b a n c o r pp i p e rj a f f 髓y 的數(shù)據(jù)顯示 g o o g l e 、雅虎、m s n 、a o l 四家公司將占全球搜索引擎市場8 0 以上的 市場份額。世界上最著名的三個搜索引擎為g o o g l e 、雅虎、m s n 占有份 額在7 3 左右【1 1 以g o o g l e 為例，據(jù)報道截止到2 0 0 5 年2 月1 6 日， g o o g l e 已留存、搜集整理了8 , 0 5 8 ，0 4 4 ，6 5 1 個網(wǎng)頁，1 3 億張圖像，成為 搜集網(wǎng)頁最完整的搜索引擎 7 1 。a l e x a 網(wǎng)站是全球最權(quán)威的排名網(wǎng)站，它 的u r l 網(wǎng)址庫已經(jīng)超過了3 5 0 億，u r l 數(shù)量超過了g o o g l e ，成為互聯(lián) 網(wǎng)上最全的網(wǎng)址信息數(shù)據(jù)庫嘲。在國內(nèi)，號稱擁有國內(nèi)最強大的搜索性 能的百度公司一直占據(jù)著搜索引擎領(lǐng)域的重要地位。因此g o o g l e 超強、 中國石油大學(xué)( 華東) 碩士論文第1 章前言 高效的信息搜集能力令無數(shù)同行羨慕，而這一工作的完成者一個超強的 r o b o t ( 網(wǎng)絡(luò)機器人或網(wǎng)絡(luò)蜘蛛、s p i d e r ) 。據(jù)稱o o o g l e 在全球各地擁有 60 0 0 多部紅帽l i n u x 服務(wù)器，g o o g l e 用這幾千臺機器構(gòu)成一個龐大的超 級計算機，并很好地完成了一切步驟：搜集信息、整理歸類、精確網(wǎng)絡(luò) 信息、處理搜索請求i 刀 隨著i n t e r n c t 信息量的不斷增加，r o b o t 所要擔(dān)負的搜集工作愈加 繁重。當(dāng)前，提高r o b o t 的搜集性能主要通過兩種方式：一是硬件技術(shù)， 隨著計算機硬件技術(shù)的飛速發(fā)展，人們不斷地提高單機性能，通過使用 高處理性能的計算機來提高r o b o t 的搜集的能力；二是理論研究，r o b o t 采用分布式技術(shù)增加并行計算能力，通過優(yōu)化搜索策略和算法來減少內(nèi) 部的開銷和增加信息搜集的效率。 當(dāng)前學(xué)術(shù)界對大規(guī)模的信息搜集工作的研究較少，而上述兩種方式 都有存在一些缺點。雖然近年來，計算機硬件技術(shù)不斷提高，高性能的 處理器( c p u ) 、海量的存儲器、寬帶技術(shù)的出現(xiàn)，使得單機處理，信息 存儲以及網(wǎng)絡(luò)帶寬的性能不斷提高。但是硬件技術(shù)的發(fā)展跟不上i n t e r a c t 信息增長的步伐，受限于硬件技術(shù)，r o b o t 的搜集性能提高有限。分布 式處理和并行運算技術(shù)讓人們看到了提高r o b o t 的搜集性能的無窮潛 力，通過增加機群中機器的數(shù)量，來無限地提高r o b o t 的信息搜集性能。 但是采用分布式技術(shù)的r o b o t 的設(shè)計上較傳統(tǒng)的單機集中式r o b o t 的設(shè) 計復(fù)雜，而且在具體的實現(xiàn)中，面臨著u r l 劃分策略、u r l 匹配方式、 負載平衡、擴展性和健壯性等諸多新問題。而且機器數(shù)量的增加會加大 r o b o t 的內(nèi)部開銷，這使得信息搜集能力的提高受到限制。除了上述兩 種方式，r o b o t 的搜集性能還受到搜索策略的影響，而且當(dāng)前搜索策略 的研究也成為熱點，如啟發(fā)式搜索策略和更新策略的研究，這會使r o b o t 搜集性能進一步提高。 2 中國石油大學(xué)( 華東) 碩士論文第1 章前言 1 2 課題的意義 據(jù)c n n i c 發(fā)布統(tǒng)計報告：我國網(wǎng)站總數(shù)約為6 6 8 9 萬個；網(wǎng)頁總數(shù) 約為6 5 億個。比上年增長1 0 8 6 ：網(wǎng)頁的總字節(jié)數(shù)約為2 0 5 3 7 g b ，比 上年增長2 3 8 9 n 。中文w e b 信息的飛速增長，使得中文搜索引擎更有 用武之地，但卻使信息搜集工作變得愈加繁重。國外g o o g l e 、a l e x a 的 搜索能力可以很好的滿足中文w e b 信息的搜集工作，但由于其不是專門 面向中文w e b 信息的搜索引擎，因此，它們對中文w e b 信息的搜索能力 大大折扣。國內(nèi)的搜索弓l 擎，在信息搜集技術(shù)上與國外相比，差距十分 巨大，中文搜索引擎r o b o t 技術(shù)有待于進一步提高。而當(dāng)前關(guān)于它的研 究卻不多，學(xué)術(shù)界更多地將研究目標(biāo)放在信息檢索領(lǐng)域，這使得信息搜 集問題交得異常的尖銳。而在信息更新領(lǐng)域，當(dāng)前的形勢更是不容樂觀， 如o o o g l e 的整個搜索結(jié)果的更新周期為一個月【堋，而a l e x a 的更新周期 為2 個, 目e l l j 即使一些不求信息數(shù)量只求信息質(zhì)量的搜索引擎，沒有強 大的搜集能力，也會出現(xiàn)很多問題。如信息更新問題，據(jù)統(tǒng)計g o o g l e 的 死鏈接在7 6 翻，出現(xiàn)死鏈接的情況是用戶對搜索引擎最不滿意的事情 之一。因此，無論哪種搜索引擎，搜索引擎r o b o t 信息搜集的能力提高 是非常必要的，這會便搜索引擎如虎添翼。鑒于中文搜索引擎在信息搜 集性能上的不足，本文就中文搜索引擎r o b o t 技術(shù)展開研究。 1 3 論文研究內(nèi)容 除去硬件技術(shù)的發(fā)展之外，分布式技術(shù)和搜索策略的研究是提高 r o b o t 性能的兩種有效的方式。為提高中文搜索引擎r o b o t 的搜集性能， 采用分布式技術(shù)是首選。實際應(yīng)用中，采用分布式技術(shù)會帶來一些新問 題，如u r l 劃分策略、u r l 匹配算法、系統(tǒng)的負載平衡、內(nèi)部通信開 銷、擴展性和健壯性等問題【1 3 1 。本文對搜索引擎和r o b o t 技術(shù)的作了全 面的闡述，深入分析了現(xiàn)有的分布式技術(shù)方案，針對一些不足，提出了 中國石油大學(xué)( 華東) 碩士論文 第1 章前言 基于u r l 分級散列機制的中文w e b 信息搜集系統(tǒng)( 簡稱u c h s 系統(tǒng)) 。 該系統(tǒng)的核心為對u r l 分級散列進行系統(tǒng)節(jié)點的定位和u r l 的匹配， 結(jié)合中文w e b 信息的特點，為之設(shè)計了兩種適用于定位和匹配的u r l 散列函數(shù)。 為了進一步提高u c h s 系統(tǒng)的性能，本文對搜索策略作了一定的研 究，在基于u r l 分級散列機制的研究上，提出了基于域名的u r l 過濾 技術(shù)、基于首頁內(nèi)容的中文網(wǎng)站識別技術(shù)、基于首頁的搜索策略和基于 內(nèi)容變化度的更新策略等技術(shù)和策略。 1 4 論文組織結(jié)構(gòu) 本文共分7 章，具體結(jié)構(gòu)如下： 第l 章闡述了論文的研究背景和意義，介紹了論文的主要研究內(nèi)容， 最后給出本文的組織結(jié)構(gòu)。 第2 章從搜索引擎的歷史、分類、原理、評價標(biāo)準(zhǔn)及發(fā)展趨勢等五 個方面詳細地闡述了傳統(tǒng)的搜索引擎的整個工作流程及其相關(guān)技術(shù)。 第3 章介紹了r o b o t 技術(shù)的相關(guān)研究，給出了各具特色的r o b o t 、搜 索策略和更新策略，對此作了分析并指出當(dāng)前存在的一些問題。 第4 章深入分析了采用分布式技術(shù)帶來的一些問題，提出了基于 u r l 分級散列機制的中文w e b 信息分布式搜集系統(tǒng)( 簡稱u c h s 系統(tǒng)) ； 根據(jù)中文w e b 信息的特點，給出了兩種適用的u r l 散列函數(shù)；根據(jù)現(xiàn) 有的搜索策略，對搜索策略、更新策略和相關(guān)的一些技術(shù)作了一定的研 究。 第5 章設(shè)計和構(gòu)建基于u r l 分級散列機制的中文w e b 信息分布式 搜集系統(tǒng)，并給出實現(xiàn)中所用到的相關(guān)技術(shù)，并對一些模塊作了測試和 分析。 第6 章全文總結(jié)并展望未來的發(fā)展方向。 4 中國石油大學(xué)( 華東) 碩士論文 第2 章搜索引擎概述 第2 章搜索引擎概述 1 9 9 0 年以前，沒有任何人能搜索i n t e r n e t 的信息，也無需搜索。當(dāng) 時的i n t e r n e t 還在剛剛起步階段。人們僅僅記住i n t e m e t 上的幾個站點， 就可以瀏覽i n t e r n e t 。搜索引擎的出現(xiàn)是i n t e m e t 發(fā)展壯大的產(chǎn)物，當(dāng)有 一天人們發(fā)現(xiàn)瀏覽整個i n t e m e t 信息變得不可能時，一種基于i n t e r n e t 信 息檢索的工具隨之而生，這就是搜索引擎。i n t e m e t 的飛速發(fā)展促生了搜 索引擎，搜索引擎反過來也促進了i n t e m e t 的發(fā)展。搜索引擎從問世至今， 僅僅十余年的歷史，但據(jù)美國互聯(lián)網(wǎng)調(diào)查機構(gòu)p i a l p 公布的統(tǒng)計結(jié)果顯 示，網(wǎng)民對i n t c - m e t 搜索的依賴性越來越大，如今已成為繼電子郵件之后 的第二大網(wǎng)絡(luò)應(yīng)用【1 4 1 。與此同時，搜索引擎技術(shù)的研究也步入到智能搜 索引擎的研究階段b 5 , 1 6 1 。 2 1 搜索引擎的歷史 搜索引擎豹雛形出現(xiàn)在1 9 9 0 年，當(dāng)時m c g i l lu m v e r s i t y 的學(xué)生a l a n e m t a g e 、b i l l w h e e l a n 和p e t e r d e u t s c h 創(chuàng)建了名叫a r c h i e 的數(shù)據(jù)庫系統(tǒng)。 a r c h i e 是第一個自動索引i n t e m e t 上匿名f t p 網(wǎng)站文件的程序，但它還 不是真正的搜索引擎。用戶必須輸入精確的文件名，然后a r c h i e 會告訴 用戶哪一個f t p 地址可以下載該文件。這使i n t e m e t 用戶難以掌握。受 a r c h i e 啟發(fā)，n e v a d as y s t e mc o m p u t i n gs e r v i c e s 大學(xué)于1 9 9 3 年開發(fā)了一 個搜索工具v e r o n i c a ( v e r ye a s yr o d e n t - o r i e n t e dn e tw i d ei n d e xt o c o m p u t e r i z e d a r c h i v e s ) 。它是一種基于g o p h e r 的服務(wù)資源，通過關(guān)鍵字 來搜索整個g o p h e r 空間，搜索的范圍包括了i n t e m e t 上所有g(shù) o p h e r 服務(wù) 器的各個層次的菜單，并且搜索結(jié)果可以使用戶直接與相應(yīng)的信息或數(shù) 據(jù)源相連接。 搜索引擎用來搜集信息的工具被稱為r o b o t ( 或s p i d e r ) ，世界上第 一個r o b o t 程序，是m i tm a t t h e wg r a y 的w o r l dw i d ew e bw a n d e r e r ，用 s 中國石油大學(xué)( 華東) 碩士論文 第2 章搜索引肇概述 于追蹤互聯(lián)網(wǎng)發(fā)展規(guī)模。1 9 9 4 年4 月，基于人工搜集信息提供檢索的服 務(wù)工具y a h o o 出現(xiàn)。它的數(shù)據(jù)是手工輸入的，所以不能真正被歸為搜索 引擎，但它具有很好的索引功能，在2 0 世紀(jì)9 0 年代幾乎成為i n t e m e t 的代名詞，這也預(yù)示著搜索引擎美好的前景。同年l y c o s 的出現(xiàn)是搜索 引擎史上一個重要的進步。c a r n e g i em e l l o nu n i v e r s i t y 的m i c h a e lm a u l d i n 將j o h nl e a v i t t 的r o b o t 程序接入到其索引程序中，創(chuàng)建了l y c o s 。它具 有自動搜集和索引功能，是真正意義上的搜索引擎。隨后出現(xiàn)的還有 i n f o s e e k 和e x c i t e 。最初搜索引擎的發(fā)展方向是具有更強的搜索能力。 1 9 9 5 年，a l t a v i s t a 出現(xiàn)，它的最大的優(yōu)勢是它的搜索速度，但它的 一些新功能，則改變了搜索引擎的定義。a l t a v i s t a 是第一個支持自然語 言搜索的搜索引擎，是第一個實現(xiàn)高級搜索語法的搜索引擎( 如a n d ， o r , n o t 等) 。在面向用戶的界面上，a l t a v i s t a 也作了大量革新。它在搜 索框區(qū)域下放了“邱8 ”以幫助用戶更好的表達搜索式，這些小邱經(jīng)常 更新，這樣，在搜索過幾次以后，用戶會看到很多他們可能從來不知道 的有趣功能。這系列功能，逐漸被其它搜索引擎廣泛采用并延續(xù)至今。 在搜索引擎已經(jīng)具備了一定的搜索性能之后，一種新的搜索引擎形 式出現(xiàn)了元搜索引擎( a m e t a s e a r c h e n g i n e r o u n d u p ) 。它利用了獨 立搜索引擎的搜索結(jié)果，根據(jù)用戶提交的搜索請求，由元搜索引擎負責(zé) 轉(zhuǎn)換處理后提交給多個預(yù)先選定的獨立搜索引擎，并將返回的所有查詢 結(jié)果集中起來處理后再返回給用戶第一個元搜索引擎是w a s h i n g t o n 大 學(xué)碩士生e r i cs e l b e r g 和o r e ne t z i o n i 的m e t a e m w l e r 。從概念上分析， 元搜索引擎是建立在獨立搜索引擎的基礎(chǔ)上的一種搜索引擎，但在實際 的應(yīng)用中，元搜索引擎的效果始終不理想，至今沒有哪個元搜索引擎有 過強勢地位。 1 9 9 5 年以后，搜索引擎技術(shù)逐漸發(fā)展成熟起來，較為著名的搜索引 中國石油大學(xué)( 華東) 碩士論文 第2 章搜索引擎概述 擎有：n o r t h e m l i g h t 、i n k t o m i 、f a s t 、g o o g l e 。其代表是1 9 9 8 年9 月由 l a r r yp a g e 和s e r g e yb d n 創(chuàng)建的g o o g l e 。它在p a g e r a n k 、動態(tài)摘要、 網(wǎng)頁快照、d a i l y r e f r e s h 、多文檔格式支持、地圖股票詞典尋人等集成搜 索、多語言支持、用戶界面等功能上的革新，繼a l t a v i s t a 之后，再一次 改變了搜索引擎的定義。 國內(nèi)搜索引擎的起步較晚，但最近幾年發(fā)展很快。比較著名的有： 百度( b a i d u ) 、天網(wǎng)、中搜、一艘。其中天網(wǎng)是國家”九五”重點科技攻 關(guān)項耳”中文編碼和分布式中英文信息發(fā)現(xiàn)”的研究成果，由北大計算機 系網(wǎng)絡(luò)與分布式系統(tǒng)研究室開發(fā)，于1 9 9 7 年1 0 月2 9 日正式在c e r n e t 上提供服務(wù)。2 0 0 0 年初成立天網(wǎng)搜索引擎新課題組，由國家9 7 3 重點基 礎(chǔ)研究發(fā)展規(guī)劃項目基金資助開發(fā)，收錄網(wǎng)頁約6 0 0 0 萬，利用教育網(wǎng)優(yōu) 勢，有強大的f l p 搜索功能。百度于2 0 0 1 年1 0 月2 2 日正式發(fā)布，只提 供中文搜索，但目前收錄中文網(wǎng)頁超過9 0 0 0 萬，可能是最大的的中文數(shù) 據(jù)庫。b a i d u 搜索引擎的其它特色包括：網(wǎng)頁快照、網(wǎng)頁預(yù)覽、相關(guān)搜索 詞、錯別字糾正提示、新聞搜索、f l a s h 搜索、信息快遞搜索等。 隨著互聯(lián)網(wǎng)規(guī)模的急劇膨脹，搜索引擎的搜集工作變得日益繁重， 因此現(xiàn)在搜索引擎之間開始出現(xiàn)了分工協(xié)作，并有了專業(yè)的搜索弓l 擎技 術(shù)和搜索數(shù)據(jù)庫服務(wù)提供商國外的i n k t o m i ，它本身并不是直接面向用 戶的搜索引擎，但向包括o v e r t u r e ( 原g o t o ) 、l o o k s m a r t 、m s n h o t b o t 等在內(nèi)的其他搜索引擎提供全文網(wǎng)頁搜索服務(wù)。國內(nèi)的百度也屬于這一 類。因此從這個意義上說，它們是搜索引擎的搜索引擎。 2 2 搜索引擎的分類 隨著搜索引擎技術(shù)的發(fā)展，出現(xiàn)了各種特色的搜索引擎，如元搜索 引擎、分布式搜索引擎、f 皿搜索引擎、交互式搜索引擎、個性化搜索 引擎、專家型搜索引擎、主題搜索引擎、自然語言搜索引擎、新聞搜索 7 中國石油大學(xué)( 華東) 碩士論文第2 章搜索引擎概述 引擎、m p 3 搜索引擎以及圖片搜索引擎等等。搜索引擎?zhèn)鹘y(tǒng)的分類方式 是基于搜索引擎使用的信息搜集技術(shù)，它將搜索引擎分為三類：目錄式 ( d i r e c t o r y ，或c a t a l o g ) 搜索引擎、基于機器人( r o b o t ) 的搜索引擎和 元( m e t a ) 搜索引擎t 塒。 目錄式搜索引擎：它以人工方式或半自動方式搜集信息，不算是真 正的搜索引擎。它的信息搜集方式：由專職人員訪問w e b 站點后撰寫一 段對該站點的描述，并根據(jù)站點的內(nèi)容和性質(zhì)將其歸為一個預(yù)先分好的 類別，把站點的u r l 和描述放在這個類別中；很多目錄也接受用戶提交 的網(wǎng)站和描述，當(dāng)目錄的編輯人員認(rèn)可該網(wǎng)站及描述后，就會將之添加 到合適的類別中信息大多面向網(wǎng)站，提供目錄瀏覽服務(wù)和直接檢索服 務(wù)。這類搜索引擎因為加入了人的智能，返回給用戶的準(zhǔn)確率較好。典 型代表是y a h o o ! 基于機器人的搜索引擎：這種搜索引擎又被稱為基于全文檢索的搜 索引擎，它的特點是利用搜集器( r o b o t 或s p i d e r ) 以某種策略在i n t e m e t 上自動搜集，搜集到的信息由索引器建立索引，再由檢索器根據(jù)用戶提 交的請求檢索索引庫，并將結(jié)果返回給用戶。面向網(wǎng)頁搜集信息，提供 面向網(wǎng)頁的全文檢索服務(wù)。由于使用r o b o t 自動搜集信息，它包含的信 息量大、更新及時，現(xiàn)有的多數(shù)搜索引擎都屬于此類。 元搜索引擎：它與基于機器人的搜索引擎的最大區(qū)別是它沒有獨立 的索引庫，它也可以看作是基于機器人的搜索引擎，只是這兩種機器人 不同。元搜索引擎根據(jù)用戶提交的請求轉(zhuǎn)換處理后提交給多個預(yù)先選定 的獨立搜索引擎，并將所有查詢結(jié)果集中起來，再按照自己的規(guī)則呈現(xiàn) 到用戶面前。這類搜索引擎的代表是w c b c r a w l e r 、i n f o m a r k e t 等。 目前，搜索引擎的分類有衍生出其它的方式，如按信息語種分類有： 單語種搜索引擎、多語種搜索弓l 擎或中文搜索引擎、英文搜索引擎等。 8 中國石油大學(xué)( 華東) 碩士論文第2 章搜索引肇概述 按信息類型分類有：文本搜索引擎、多媒體搜索引擎、f t p 搜索引擎等。 隨著搜索引擎的發(fā)展，搜索引擎的類別越來越多，搜索引擎的分類方式 也在發(fā)生變化。 2 3 搜索引擎的工作原理 隨著i n t e r a c t 信息量的增長和搜索技術(shù)的發(fā)展，目錄式搜索引擎已經(jīng) 落伍，而元搜索引擎只是概念上比獨立搜索引擎先進，卻沒有取得比獨 立搜索引擎更好的搜索效果。當(dāng)前，多數(shù)的搜索引擎都屬于基于機器人 的搜索引擎( 簡稱搜索引擎) ，它的工作原理如下【。 工作方式：搜索引擎返回給用戶的信息是事先處理好了的，它首先 去網(wǎng)絡(luò)中抓取信息，再為抓取來得信息建立索引，當(dāng)用戶提交查詢請求 時，搜索引擎在本地的索弓l 庫中檢索，返回給用戶一些相關(guān)的網(wǎng)絡(luò)信息。 搜索引擎主要由搜集器、索引器、檢索器和用戶接口四部分組成， 結(jié)構(gòu)如圖2 - 1 所示。 l 搜集器l乏二f爿檢索器l 一馨 l 苧鷙咎墨0 ，一一j j 卜、 團 u 一u 卜l l 原始l l 數(shù)據(jù)i 喀上 f l 鶼皤l i 用戶接1 2 1b r _ 1 圖2 - 1 搜索引擎結(jié)構(gòu)圖 搜集器負責(zé)將i n t e r a c t 上的信息抓取到本地數(shù)據(jù)庫。它一般由一個 r o b o t 程序自動運行搜集i n t e r a c t 信息并按照規(guī)定的格式將信息下載到原 始數(shù)據(jù)庫。索引器負責(zé)為抓取來的信息建立索引形成索引數(shù)據(jù)庫。通常， 它要去除頁面上的無用信息，提取所有出現(xiàn)的詞或字，并記錄所在的u r l 和所在的位置，然后將其存入索引庫。檢索器根據(jù)用戶的請求檢索索引 9 中國石油大學(xué)( 華東) 碩士論文第2 章搜索引擎概述 庫，獲得相應(yīng)的檢索結(jié)果。搜索引擎一般不直接對用戶的請求進行檢索， 而是先分析用戶的請求，再按照一定的邏輯關(guān)系獲德最終的檢索結(jié)果。 用戶接口提供了查詢輸入、結(jié)果顯示、相關(guān)性信息反饋等功能。主要的 目的是方便用戶使用搜索引擎，高效率、多方式地從搜索引擎中得到有 效、及時的信息。用戶輸入接口可以分為簡單接口和復(fù)雜接口兩種。簡 單接口只提供用戶輸入查詢串的文本框；復(fù)雜接口可以讓用戶對查詢進 行限制，如邏輯運算、相近關(guān)系、域名范圍、出現(xiàn)位置、信息時間、長 度等。 2 4 搜索引擎的評價標(biāo)準(zhǔn) 影響一個搜索引擎系統(tǒng)的性能有很多因素，最主要的是信息檢索模 型，包括文檔和查詢的表示方法、評價文檔和用戶查詢相關(guān)性的匹配策 略、查詢結(jié)果的排序方法和用戶進行相關(guān)度反饋的機制【1 9 1 。通常使用的 評價搜索引擎的技術(shù)指標(biāo)有：查全率( r e c a u ) 與查準(zhǔn)率( p r e c i s i o n ) 、內(nèi)容的 更新速度、反饋的查詢結(jié)果、信息量及其覆蓋率。 查全率與查準(zhǔn)率：查全率是檢索出的相關(guān)文檔數(shù)和文檔庫中所有的 相關(guān)文檔數(shù)的比率。查準(zhǔn)率是檢索出的相關(guān)文檔數(shù)與檢索出的文檔總數(shù) 的比率。查全率與查準(zhǔn)率是一對矛盾體，當(dāng)它們的值達到一定對，查全 率高會降低查準(zhǔn)率，反之亦然。評價一個搜索引擎時，應(yīng)以該搜索引擎 所服務(wù)的主要用戶的需求特點為準(zhǔn)。目前的搜索引擎研究更多的放在查 準(zhǔn)率上。 內(nèi)容的更新速度：互聯(lián)網(wǎng)是一個動態(tài)的網(wǎng)絡(luò)，網(wǎng)絡(luò)信息瞬息萬變， 信息的更迭與消亡無法預(yù)測。以中國互聯(lián)網(wǎng)為例，國內(nèi)前1 0 0 家大型網(wǎng) 站中，3 0 7 的網(wǎng)頁更新時間為1 月至6 月，全國網(wǎng)站中相應(yīng)的比例為 2 3 1 ；國內(nèi)前1 0 0 家大型網(wǎng)站中6 1 9 的網(wǎng)頁更新時間在6 個月以上， 全國網(wǎng)站中相應(yīng)的比例為6 8 4 口0 】。因此搜索引擎要及時地反映出互聯(lián) i o 中國石油大學(xué)( 華東) 碩士論文 第2 章搜索引擎概述 網(wǎng)的最新動態(tài)。由于各網(wǎng)頁的更新不是同步進行的，使得搜索引擎自身 數(shù)據(jù)庫的更新情況比較復(fù)雜。不同目的的搜索引擎對更新速度要求不一 樣，但盡可能的與互聯(lián)網(wǎng)保持同步是所有搜索引擎的目標(biāo)。而對一些搜 索引擎而言，實效性是評價該搜索引擎的重要指標(biāo)，如新聞搜索引擎。 反饋的查詢結(jié)果：對一般搜索引擎而言，反饋的查詢結(jié)果評價標(biāo)準(zhǔn) 主要是主題的重復(fù)率和死鏈接率。目前，中國互聯(lián)網(wǎng)中網(wǎng)頁的重復(fù)率比 較高，估計有2 5 4 0 1 2 0 1 ，若搜索引擎對此不作相應(yīng)處理，同一主題信息 會大量重復(fù)出現(xiàn)；死鏈接主要是因為搜索引擎的更新速度問題，它不僅 無法滿足用戶的需求，而且還浪費用戶的許多時間。信息量的增加使得 查詢結(jié)果的排序也成為評價搜索引擎性能的指標(biāo)之一，對于用戶提交的 一個請求，搜索引擎經(jīng)常會反饋給用戶海量的查詢結(jié)果，那些被排在一 千位之外的信息，被用戶讀到的機會幾乎為零。 信息量大小及其覆蓋率：在傳統(tǒng)的計算機情報檢索系統(tǒng)中，數(shù)據(jù)庫 的覆蓋率是影響其檢索性能的重要指標(biāo)，它直接影響系統(tǒng)的查全率。盡 管由于網(wǎng)上信息分散、無序，更新和消亡無法預(yù)測，信息量對系統(tǒng)的查 全率的影響可能不是那么明顯，但是在用戶選擇搜索引擎的過程中信息 量的大小仍有一定的借鑒作用，畢竟從統(tǒng)計學(xué)的角度看，收集的網(wǎng)頁多， 查到更多的結(jié)果的可能性也就越大。信息覆蓋率指搜索引擎索引數(shù)據(jù)庫 索引的w 如頁面占其所要搜集的w e b 頁面的比例，它是提高查全率的基 本條件。因為搜索引擎搜集范圍的不同，通常從兩個方面考察信息的覆 蓋率：一是該搜索引擎應(yīng)窮盡所規(guī)定的搜集信息；二是該搜索引擎應(yīng)窮 盡所有有價值的信息。 2 5 搜索引擎的發(fā)展趨勢 搜索引擎已成為一個新的研究、開發(fā)領(lǐng)域。因為它要用到信息檢索、 人工智能、計算機網(wǎng)絡(luò)、分布式處理、數(shù)據(jù)庫、數(shù)據(jù)挖掘、數(shù)字圖書館、 中國石油大學(xué)( 華東) 碩士論文第2 章搜索引擎概述 自然語言處理等多領(lǐng)域的理論和技術(shù)，所以具有綜合性和挑戰(zhàn)性1 1 9 】。搜 索引擎將在諸多方麗發(fā)生著深刻的變化：搜索技術(shù)將更加智能化；搜索 資源將更加廣泛；搜索方式將更加便捷、有效；專項搜索將更加豐富。 具有特色服務(wù)的搜索引擎：互聯(lián)網(wǎng)上的信息浩如煙海，并且還在不 斷的增長，搜索引擎想要搜集到所有信息是不可能的事情。若一個搜索 引擎的搜集能力不強，而它搜集信息的主題比較全面，這就很難保證所 搜集到信息的質(zhì)量，使得檢索結(jié)果不盡人意。為保證檢索結(jié)果的精確度， 對一般的搜索引擎而言，確定信息搜集范圍是十分必要的。當(dāng)前各種具 有特色服務(wù)的搜索引擎不斷出現(xiàn)，如垂直搜索引擎、主題搜索引擎、新 聞搜索引擎以及個性化搜索引擎等，圍繞它們的研究越來越多。 多媒體搜索引擎：互聯(lián)網(wǎng)上音頻、視頻、圖像正在取代文本成為互 聯(lián)網(wǎng)上主要的信息。它們自身信息量大，而且難以提供有效的檢索。傳 統(tǒng)搜索引擎一般并不收集這些信息。隨著網(wǎng)絡(luò)技術(shù)、存儲技術(shù)和檢索技 術(shù)的發(fā)展，開發(fā)基于內(nèi)容檢索的多媒體搜索引擎是一個新的發(fā)展方向。 桌面搜索是新提出的概念，對它的描述是“就像是電腦的照相存儲 器，任何在計算機上瀏覽過的信息都能輕松搜索到”，它將對現(xiàn)有的搜索 方式產(chǎn)生極大的挑戰(zhàn)【2 ”。它在功能上更加方便地實現(xiàn)終端用戶的個性化、 智能化需求，并且語音、視頻等多媒體搜索方式也將得到平臺的依靠， 具備進一步開發(fā)應(yīng)用可能。在搜索范圍上，桌面搜索實現(xiàn)了更加廣泛的 選擇，從電腦到網(wǎng)絡(luò)包括本地硬盤、局域網(wǎng)、互聯(lián)網(wǎng)，每個角落都可以 用桌面搜索尋找要找的東西。 基于自然語言的搜索引擎：傳統(tǒng)的搜索引擎對要檢索的信息僅僅采 用機械的關(guān)鍵詞匹配來實現(xiàn)，缺乏知識處理能力和理解能力，基于自然 語言的搜索引擎把信息檢索從目前基于關(guān)鍵詞的層面提高到語義的層 面。它對信息有一定的理解與處理能力，能夠?qū)崿F(xiàn)智能分詞技術(shù)、同義 1 2 中國石油大學(xué)( 華東) 碩士論文 第2 章搜索引擎概述 詞技術(shù)、概念搜索、短語識別以及機器翻譯等技術(shù)。它允許用戶采用自 然語言進行信息檢索，提供更方便、更確切的搜索服務(wù)。i b m 認(rèn)為，新 型搜索技術(shù)將文檔視為“人類語言的表達”，而不是匹配文字模式。除處 理句法分析之外，i b m 還在研究能夠理解語義的搜索引擎技術(shù)詞在 上下文中的含義【2 1 1 。 p 2 p 搜索引擎：p 2 p 是p e e r - t o p e e r 的縮寫，意為對等網(wǎng)絡(luò)。它通過 共享所有硬盤上的文件、目錄乃至整個硬盤，用戶搜索時無需通過w e b 服務(wù)器，不受信息文檔格式的限制，即可達到傳統(tǒng)目錄式搜索引擎無可 比擬的深度( 傳統(tǒng)引擎只能達到2 0 3 0 的網(wǎng)絡(luò)資源) 。以p 2 p 技術(shù)進 行的搜索1 ，搜索范圍將在幾秒鐘內(nèi)以幾何級數(shù)增長，幾分鐘內(nèi)就可 搜遍幾百萬臺p c 上的信息資源。未來的一段時間，隨著信息國際化程 度的加深，隨著p 2 p 技術(shù)的普及必將對搜索引擎這一網(wǎng)絡(luò)軟件產(chǎn)生很大 的影響，f 2 p 搜索是未來的搜索技術(shù)發(fā)展方向之一。 中國石油大學(xué)( 華東) 碩士論文第3 章r o b o t 技術(shù)的相關(guān)研究 第3 章r o b o t 技術(shù)的相關(guān)研究 3 。1r o b o t 的工作原理 互聯(lián)網(wǎng)中的w e b 頁面間存在著大量的鏈接，因此可以將互聯(lián)網(wǎng)抽象 成一個有向圖來處理，將每個w e b 頁面看作圖中的一個節(jié)點，將頁面中 的鏈接看作圖中的有向邊，使用有向圖的遍歷算法( 深度優(yōu)先和寬度優(yōu)先) 來對互聯(lián)網(wǎng)進行遍歷例r o b o t 的設(shè)計正是基于圖的遍歷的思想，它利 用h t t p 協(xié)議來讀取w e b 頁面并沿著w e b 頁面間的鏈接在互聯(lián)網(wǎng)上自動 漫游，同時按照一定的規(guī)則自動訪問互聯(lián)網(wǎng)資源。它的搜索過程：r o b o t 從一個或一組等待搜索的u r l 對列開始，獲得這些u r l 對應(yīng)的頁面信 息，提取出新的u r l ，并把它們加入到u r l 等待隊列中以后每次從 隊列中取出一個或一些u r l 重復(fù)上述的過程。 3 2r o b o t 的種類 隨著搜索弓| 擎的多樣化，出現(xiàn)了各種功能的r o b o t 。如基于整個 i n t e r n c t 搜集的r o b o t 、增量式搜集的r o b o t 2 5 、基于m o b i l ea g e n t 的 r o b o t 2 6 、基于主題搜集的r o b o t l 3 1 、基于個性化搜集的r o b o t l 4 等。 3 2 1 基