分布式網(wǎng)絡爬蟲技術分析與實現(xiàn)1

分布式網(wǎng)絡爬蟲技術分析與實現(xiàn)(1)2010-06-1717:39:38來源：互聯(lián)網(wǎng)1990年以前，沒有任何人能搜索互聯(lián)網(wǎng)。所有搜索引擎的祖先，是1990年由Montreal的McGillUniversity學生AlanEmtage,PeterDeutsch.BillWheelan發(fā)明的Archie(ArchieFAQ)。一個可以用文件名查找文件的系統(tǒng)，...1990年以前，沒有任何人能搜索互聯(lián)網(wǎng)。所有搜索引擎的祖先，是1990年由Montreal的McGillUniversity學生AlanEmtage,PeterDeutsch.BillWheelan發(fā)明的Archie(ArchieFAQ)。一個可以用文件名查找文件的系統(tǒng)，于是便有了Archie.Archie是第一個自動索引互聯(lián)網(wǎng)上匿名FTP網(wǎng)站文件的程序，但它還不是真正的搜索引擎。1995年12月，Altavista永遠改變了搜索引擎的定義。AltaVista是第一個支持自然語言搜索的搜索引擎，AltaVista是第一個實現(xiàn)高級搜索語法的搜索引擎(如AND,OR,NOT等)。用戶可以用Altavista搜索Newsgroups新聞組)的內容并從互聯(lián)網(wǎng)上獲得文章，還可以搜索圖片名稱中的文字、搜索Titles、搜索Javaapplets、搜索ActiveXobjects.許多關于網(wǎng)絡爬蟲的論文都在第一屆和第二屆WorldWideWebconferences被發(fā)表。1998年，Google在Pagerank、動態(tài)摘要、網(wǎng)頁快照、DailyRefresh、多文檔格式支持、地圖股票詞典尋人等集成搜索、多語言支持、用戶界面等功能上的革新，象Altavista一樣，再一次永遠改變了搜索引擎的定義。至2005年4月21為止，Google中所收集的Web頁面數(shù)量已經(jīng)達到8,058,044,651張?，F(xiàn)階段，出現(xiàn)了AskJeeves,B,G,MySimon,Dito等內容類別不同的搜索引擎。2搜索引擎的發(fā)展現(xiàn)狀與趨勢目前，大多數(shù)的搜索引擎都是基于關鍵詞的搜索引擎?；陉P鍵字匹配的搜索技術有較大的局限性：首先，它不能區(qū)分同形異義。其次，不能聯(lián)想到關鍵字的同義詞[9]。Web商業(yè)化至今，搜索引擎始終保持著網(wǎng)絡上被使用最多的服務項目的地位，然而，隨著網(wǎng)上內容的爆炸式增長和內容形式花樣的不斷翻新，搜索引擎越來越不能滿足挑剔的網(wǎng)民們的各種信息需求。這表現(xiàn)在以下幾個方面：(1)搜索引擎對自然語言提問沒有理解能力。(2)搜索引擎收集的網(wǎng)頁數(shù)量和其數(shù)據(jù)庫的更新速度存在著不可調和的矛盾。(3)搜索引擎無法與電子商務緊密結合。(4)搜索引擎對多媒體內容的處理尚不成熟。搜索引擎的發(fā)展面臨著兩大難題：一是如何跟上Internet的發(fā)展速度，二是如何為用戶提供更精確的查詢結果。所以，傳統(tǒng)的引擎不能適應信息技術的高速發(fā)展，新一代智能搜索引擎作為一種高效搜索引擎技術的在當今的網(wǎng)絡信息時代日益引起業(yè)界人士的關注。搜索引擎己成為一個新的研究、開發(fā)領域。因為它要用到信息檢索、人工智能、計算機網(wǎng)絡、分布式處理、數(shù)據(jù)庫、數(shù)據(jù)挖掘、數(shù)字圖書館、自然語言處理等多領域的理論和技術，所以具有綜合性和挑戰(zhàn)性。又由于搜索引擎有大量的用戶，有很好的經(jīng)濟價值，所以引起了世界各國計算機科學界和信息產(chǎn)業(yè)界的高度關注，目前的研究、開發(fā)十分活躍，并出現(xiàn)了很多值得注意的動向。1．自然語言理解技術自然語言理解是計算機科學中的一個引人入勝的、富有挑戰(zhàn)性的課題。從計算機科學特別是從人工智能的觀點看，自然語言理解的任務是建立一種計算機模型，這種計算機模型能夠給出像人那樣理解、分析并回答自然語言。以自然語言理解技術為基礎的新一代搜索引擎，我們稱之為智能搜索引擎。由于它將信息檢索從目前基于關鍵詞層面提高到基于知識(或概念)層面，對知識有一定的理解與處理能力，能夠實現(xiàn)分詞技術、同義詞技術、概念搜索、短語識別以及機器翻譯技術等。因而這種搜索引擎具有信息服務的智能化、人性化特征，允許網(wǎng)民采用自然語言進行信息的檢索，為它們提供更方便、更確切的搜索服務。2．十分注意提高信息查詢結果的精度，提高檢索的有效性用戶在搜索引擎上進行信息查詢時，并不十分關注返回結果的多少，而是看結果是否和自己的需求吻合。對于一個查詢，傳統(tǒng)的搜索引擎動輒返回幾十萬、幾百萬篇文檔，用戶不得不在結果中篩選。解決查詢結果過多的現(xiàn)象目前出現(xiàn)了幾種方法：(1)是通過各種方法獲得用戶沒有在查詢語句中表達出來的真正用途，包括使用智能代理跟蹤用戶檢索行為，分析用戶模型;使用相關度反饋機制，使用戶告訴搜索引擎哪些文檔和自己的需求相關(及其相關的程度)，哪些不相關，通過多次交互逐步求精。-3-哈爾濱工業(yè)大學工學碩士學位論文(2)是用正文分類(TextCategorization)技術將結果分類，使用可視化技術顯示分類結構，用戶可以只瀏覽自己感興趣的類別。(3)是進行站點類聚或內容類聚，減少信息的總量。3．基于智能代理的信息過濾和個性化服務信息智能代理是另外一種利用互聯(lián)網(wǎng)信息的機制。它使用自動獲得的領域模型(如Web知識、信息處理、與用戶興趣相關的信息資源、領域組織結構)、用戶模型(如用戶背景、興趣、行為、風格)知識進行信息搜集、索引、濾(包括興趣過濾和不良信息過濾)，并自動地將用戶感興趣的、對用戶有用的信息提交給用戶。智能代理具有不斷學習、適應信息和用戶興趣動態(tài)變化的能力，從而提供個性化的服務。智能代理可以在用戶端進行，也可以在服務器端運行。4．采用分布式體系結構提高系統(tǒng)規(guī)模和性能搜索引擎的實現(xiàn)可以采用集中式體系結構和分布式體系結構，兩種方法各有千秋。但當系統(tǒng)規(guī)模到達一定程度(如網(wǎng)頁數(shù)達到億級)時，必然要采用某種分布式方法，以提高系統(tǒng)性能。搜索引擎的各個組成部分，除了用戶接口之外，都可以進行分布：搜索器可以在多臺機器上相互合作、相互分工進行信息發(fā)現(xiàn)，以提高信息發(fā)現(xiàn)和更新速度:索引器可以將索引分布在不同的機器上，以減小索引對機器的要求;檢索器可以在不同的機器上進行文檔的并行檢索，以提高檢索的速度和性能。這項內容的一個明顯的技術是P2PoP2P是peer-to-peer的縮寫，意為對等網(wǎng)絡。其在加強網(wǎng)絡上人的交流、文件交換、分布計算等方面大有前途。長久以來，人們習慣的互聯(lián)網(wǎng)是以服務器為中心，人們向服務器發(fā)送請求，然后瀏覽服務器回應的信息。而P2P所包含的技術就是使聯(lián)網(wǎng)電腦能夠進行數(shù)據(jù)交換，但數(shù)據(jù)是存儲在每臺電腦里，而不是存儲在既昂貴又容易受到攻擊的服務器里。網(wǎng)絡成員可以在網(wǎng)絡數(shù)據(jù)庫里自由搜索、更新、回答和傳送數(shù)據(jù)。所有人都共享了它們認為最有價值的東西，這將使互聯(lián)網(wǎng)上信息的價值得到極大的提升。5．重視交叉語言檢索的研究和開發(fā)交叉語言信息檢索是指用戶用母語提交查詢，搜索分布式網(wǎng)絡爬蟲技術分析與實現(xiàn)(2)2010-06-1717:39:38來源：互聯(lián)網(wǎng)1990年以前，沒有任何人能搜索互聯(lián)網(wǎng)。所有搜索引擎的祖先，是1990年由Montreal的McGillUniversity學生AlanEmtage,PeterDeutsch.BillWheelan發(fā)明的Archie(ArchieFAQ)。一個可以用文件名查找文件的系統(tǒng)，...擎在多種語言的數(shù)據(jù)庫中進行信息檢索，返回能夠回答用戶問題的所有語言的文檔[17]。如果再加上機器翻譯，返回結果可以用母語顯示。該技術目前還處于初步研究階段，主要的困難在于語言之間在表達方式和語義對應上的不確定性。但對于經(jīng)濟全球化、互聯(lián)網(wǎng)跨越國界的今天，無疑具有很重要的意義。6．多媒體搜索引擎隨著寬帶技術的發(fā)展，未來的互聯(lián)網(wǎng)是多媒體數(shù)據(jù)的時代。開發(fā)出可查尋圖像、聲音、圖片和電影的搜索引擎是一個新的方向。目前瑞典一家公司己經(jīng)研制推出被稱作“第五代搜索引擎”的動態(tài)的和有聲的多媒體搜索引擎。3搜索引擎分類與工作原理3.1搜索引擎的分類按照信息搜集方法和服務提供方式的不同，目前Internet上的搜索引擎大致可以分成三類：1．一般搜索引擎：利用網(wǎng)絡爬蟲對Internet資源進行索引，一般無須人工干預。所謂的網(wǎng)絡爬蟲是一個程序，通過自動讀取一篇文檔遍歷Web的超鏈接結構，從而遞歸獲得被引用的所有文檔。不同的搜索引擎搜索的內容不盡相同：有的著重站點搜索，而有的搜索可能包括Gropher、新聞組、E-MAIL等。一般搜索引擎的性能主要取決于：索引數(shù)據(jù)庫的容量、存放內容、以及更新速度，搜索速度，用戶界面的友好程度以及是否易用等。這類的引擎的代表包括國外的AltaVista(htp://)InfoSeek(htp://)等。2．元搜索引擎：接受一個搜索請求，然后將該請求轉交給其他若干個搜索引擎同時處理。最后對多個引擎的搜索結果進行整和處理后返回給查詢者。整和處理包括諸如消除重復，對來自多個引擎的結果進行排序等。3．專用引擎：譬如人物搜索、旅行路線搜索、產(chǎn)品搜索等。這些搜索都依賴于具體的數(shù)據(jù)庫。引擎的其他分類方法還有：按照自動化程度分為人工與自動引擎；按照是否有智能分智能與非智能引擎；按照搜索內容分文本搜索引擎、語音搜索引擎、圖形搜索引擎、視頻搜索引擎等。3.2搜索引擎的基本工作原理搜索引擎搜集互聯(lián)網(wǎng)上成千上萬的網(wǎng)頁并對網(wǎng)頁中的內容按照關鍵詞進行索引，建立索引數(shù)據(jù)庫供用戶進行全文搜索。當用戶需要查找某一個關鍵詞時，所有在頁面內容中包含了該關鍵詞的頁面都會被搜索出來。下圖了描述搜索引擎的工作原理。依靠網(wǎng)絡爬蟲獲取互聯(lián)網(wǎng)上的大量的網(wǎng)頁信息，交給索引程序建立索引，最后提交給用戶查詢程序供用戶使用。傳統(tǒng)搜索引擎的工作從功能結構上劃分主要分三個部分：1、從互聯(lián)網(wǎng)上獲取信息的爬蟲模塊；2、建立全文索引庫的索引模塊；3、用戶查詢模塊。其中，本文所討論的范圍僅限于爬蟲模塊。下面簡要介紹一下各個模塊的作用。1、網(wǎng)絡爬蟲模塊網(wǎng)絡爬蟲實際上是一個基于web的程序。它從一個初始的網(wǎng)頁集出發(fā)，遍歷自動的采集網(wǎng)絡信息。當爬蟲打開某個HTML頁面后，它會分析HTML標記結構來獲取信息，并獲取指向其它頁面的超級鏈接，然后通過既定的搜索策略選擇下一個要訪問的站點。從理論上講，如果為Spider指定個適當?shù)某跏嘉臋n集和個適當?shù)木W(wǎng)絡搜索策略，它就可以遍歷整個網(wǎng)絡。它的性能在很大程度上影響了搜索引擎站點的規(guī)模。2、索引模塊網(wǎng)絡爬蟲爬取的網(wǎng)頁上的信息以固定的格式獲取到本地后，索引建立程序對信息進行分析，針對頁面中出現(xiàn)的關鍵詞建立一種利于快速查找的數(shù)據(jù)結構，即索引，以供搜索引擎使用。搜索引擎在選擇索引數(shù)據(jù)結構時通?？紤]兩個因素：緊湊的數(shù)據(jù)結構和高效的檢索能力。由于搜索引擎在建立索引的時候是面對海量的信息，因此在考慮記錄大小時要具體到字節(jié)中的位，這樣才能達到一種比較合理科學性的空間膨脹比。合理的數(shù)據(jù)結構將使對關鍵詞的檢索更加迅速。通常有三種索引的建立基本技術：倒排文件、后綴數(shù)組和簽名文件。倒排文件在當前大多數(shù)信息獲取系統(tǒng)中得到應用，它對于關鍵詞的搜索非常有效。后綴數(shù)組在短語查詢中具有較快的速度，但是該結構在維護上相對比較麻煩。簽名文檔如今已被倒排索引技術替代。處理網(wǎng)頁的過程主要包括這幾部分:文檔特征向量提取、網(wǎng)頁篩選、相關度分析、文檔分類和入庫操作。3、用戶查詢模塊用戶查詢模塊是搜索引擎和用戶之間的接口。其首先獲取用戶查詢條件并加以分析，然后訪問索引數(shù)據(jù)庫進行匹配后獲得檢索結果，然后根據(jù)設定的相關度進行降序排序處理后返回給用戶。3.3網(wǎng)絡爬蟲在搜索引擎中的地位從上面的搜索引擎基本原理上可以看出網(wǎng)絡爬蟲是一種能夠跟蹤網(wǎng)絡上超鏈接結構，并不斷進行網(wǎng)絡資源發(fā)現(xiàn)與采集的程序。作為搜索引擎的資源采集部分，網(wǎng)絡爬蟲的性能將直接影響到整個搜索引擎索引網(wǎng)頁的數(shù)量、質量和更新周期。因此對于網(wǎng)絡爬蟲的研究具有深遠的意義。網(wǎng)絡爬蟲的種類為了解決Web采集的關鍵問題，研究者們經(jīng)過不斷地研究與實踐，將爬行器由最早期單純的基于整個Web的爬行器發(fā)展到可滿足不同需要的多種采集技術的爬行器。歸納起來，大致可以分為以下幾種類型：第一種是基于整個Web的爬行器。主要是指目標為從一些種子URL擴充到整個Web的爬行器，這種爬行器通常是作為門戶站點搜索引擎和大型的Web服務提供商的數(shù)據(jù)采集部分。這類信息采集由于目標是采集整個Web，因此對內存和硬盤等硬件的要求比較高，對采集頁面的順序要求相對較低。第二種是增量式的爬行器。傳統(tǒng)的爬行器根據(jù)自己的需要采集足量的信息后停止采集，當過一段時間這些數(shù)據(jù)過時后，它會重新采集一遍來代替先前的信息，稱為周期性Web采集器。而增量式的爬行器對待就的頁面采用增量式更新，即采集器在需要的時候采集新產(chǎn)生的或己經(jīng)發(fā)生了變化的頁面，而對沒有變化的頁面不進行采集。和周期性信息采集相比，增量式信息采集能極大地減小數(shù)據(jù)采集量，從而極大地減少了采集的時間與空間開銷。但是與此同時，增量式信息采集也增加了算法的復雜性和技術難度。第三種是基于主題的爬行器是指選擇性地搜尋那些與預先定義好的主題相關的頁面的爬行器。和基于整個Web的爬行器相比，它并不采集那些與主題無關的頁面，所以大大地節(jié)省了硬件和網(wǎng)絡資源，保存的頁面也由于數(shù)量少而更新快。加之它可以很好地滿足一些特定人群對特定領域信息的需求，成為時下研究的熱門重點。但它的問題也是顯而易見的，例如如何定義有實際意義的主題，如何在采集時判定頁面與主題的相關性以及如何提高系統(tǒng)的搜索精度和完全度等。第四種是基于用戶個性化的爬行器。不同的用戶對一個搜索引擎提交同一個檢索詞，他們期待的結果是不盡相同的。而通用的搜索引擎卻只能返回相同的檢索結果，這顯然不完全符合用戶的需要。而基于用戶個性化的爬行器是一種輕量級的采集系統(tǒng)，它的目標就是通過用戶興趣制導或與用戶交互等手段來采集信息，給用戶提供個性化服務。第五種是移動的爬行器。這種爬行器并不像其他爬行器一樣在本地客戶機向Web站點服務器發(fā)送頁面請求，而是將自己上載到它所要采集的服務器中，在當?shù)剡M行采集，并將采集結果壓縮后，再回傳到本地。這樣做大量地節(jié)省了Web資源，大量的剪裁工作將在被采集對象的服務器上完成。第六種是基于元搜索的爬行器。它對用戶的提交的查詢請求通過多個領域或門戶搜索引擎搜索，并將結果整合后返回給用戶。一般元搜索引擎并不保存Web頁面的索引文件，但是有一些元搜索引擎會保存為它服務的每個搜索引擎的信息特征，以后根據(jù)用戶請求做出選擇。作為搜索引擎首要部件的爬行器在元搜索引擎中功能有所退化，但依然是Web采集的一個研究方向，被稱作基于元搜索的信息采集。3.5網(wǎng)絡爬蟲的兩種工作方式3.5.1集中式網(wǎng)絡爬蟲集中式爬蟲的工作原理是：給定的一組初始URL種子集合，通過爬蟲主體程序多個線程分別獲取到種子URL后，將URL對應的html頁面獲取到本地進行分析，頁面內容提取模塊將頁面中有用的可供搜索引擎建索引的信息獲取到本地保存起來，種子提取模塊將html頁面中新的指向其他頁面的鏈接提取出來，經(jīng)過一系列的處理保存起來供以后繼續(xù)爬行。3.5.2分布式網(wǎng)絡爬蟲隨著WWW信息的爆炸性增長，網(wǎng)絡爬蟲信息采集的速度越來越不能滿足實際應用的需要。即使大型的信息采集系統(tǒng)對Web的覆蓋率也只有30－40％，刷新一遍已經(jīng)采集的頁面常常需要數(shù)周到一個月的時間。解決這一問題的直接辦法是升級信息采集器的硬件，采用處理能力更強的計算機系統(tǒng)，然而這種方法的擴展性有限，性價比也不高。因而人們找了一個更好的選擇，用分布式方式來進行網(wǎng)頁信息采集。分布式網(wǎng)絡爬蟲可以看做由多個集中式網(wǎng)絡爬蟲組合而成。分布式系統(tǒng)中的每個節(jié)點都可以看作一個集中式網(wǎng)絡爬蟲。多個網(wǎng)絡爬蟲共同運行，肯定會涉及到各個節(jié)點間相互通信。這時候就會涉及到一些系統(tǒng)通信問題。分布式網(wǎng)絡爬蟲研究現(xiàn)狀要在搜索引擎中盡可能地找到用戶所需信息，就要求搜索引擎索引盡可能多的網(wǎng)頁，索引網(wǎng)頁數(shù)量是評價一個搜索引擎好壞的關鍵因素之一。采用分布式技術在盡可能短的時間內搜集盡可能多的網(wǎng)頁，是研制高效搜索引擎的關鍵技術到目前為止，分布式網(wǎng)絡爬蟲系統(tǒng)已經(jīng)有了不少應用，例如現(xiàn)在著名的Google和AltaVista搜索引擎所采用的網(wǎng)絡爬蟲系統(tǒng)。但由于商業(yè)機密等因素的影響，較詳細的介紹分布式網(wǎng)絡爬蟲系統(tǒng)的文章并不多，并且基于Web信息采集的分布式理論也還不完善，仍然有待研究。目前，較著名的分布式爬蟲有GoogleCrawler、Mercator、InternetArchiveCrawler、UbiCrawler等，國內的有北大天網(wǎng)的WebGather爬蟲系統(tǒng)。Google的分布式爬蟲系統(tǒng)由四臺機器組成，其中一臺機器是中央主機，其它三臺機器只負責爬行網(wǎng)頁，并且只與中央主機通信。中央主機從一個文件里讀取URL，并把它們分發(fā)給其它機器的Crawler進程。爬蟲采用異步I/O同時從300個網(wǎng)站上獲取數(shù)據(jù)