畢業(yè)設計論文 搜索引擎

目 錄 第一章 課題背景知識 . (1) 第一節(jié) 搜索引擎原理 . (1) 第二節(jié) 搜索引擎分類 . (2) 第三節(jié) 搜索引擎技術的發(fā)展歷史 . (4) 第四節(jié) 搜索引擎現(xiàn)狀 . (5) 第五節(jié) 搜索引擎展望 . (6) 第二章 技術詮釋 . (10) 第一節(jié) HTTP 及 HTML . (10) 第二節(jié) 網(wǎng)絡蜘蛛 . (11) 第三節(jié) 網(wǎng)頁噪聲 . (13) 第四節(jié) 頁面分析 . (13) 第五節(jié) 中文分詞 . (16) 第六節(jié) 布爾 代數(shù) . (19) 第七節(jié) CGI. (19) 第八節(jié) SOCKECT 網(wǎng)絡編程 . (20) 第三章 TOKING 海量網(wǎng)頁搜索系統(tǒng)體系結構 及實現(xiàn) . (21) 第一節(jié) 結構設計 . (21) 第二節(jié) 數(shù)據(jù)流圖 . (22) 第三節(jié) 網(wǎng)頁抓取部分 . (31) 第四節(jié) 網(wǎng)頁預處理部分 . (35) 第五節(jié) 信息查詢服務部分 . (42) 第六節(jié) 用戶反饋 . (46) 第七節(jié) 功能拓展 . (46) 第八節(jié) 優(yōu)化用戶感受 . (50) 第四章 系統(tǒng)測評 . (52) 第一節(jié) 抓取速度 . (52) 第二節(jié) 分詞效率 . (52) 第三節(jié) 搜索評價 . (53) 參考文獻 . (54) 致 謝 . (55) 附 錄 . (56) 本科生畢業(yè)設計 1 第一章 課題背景知識 70 年代中期，美國國防部高級研究計劃局 DARPA (Defense Advanced Research Projects Agency)開始了互聯(lián)網(wǎng)技術的研究。而 WWW (World Wide Web)自 1989 年誕生以來，近二十年來發(fā)展迅猛，它已成為人類社會信息資源中的一個重要組成部分，越來越多的社會信息資源實體開始選擇 Web 作為其載體。 著名的 netcraft(via Digg)剛剛完成了最新的互聯(lián)網(wǎng)調查，結果顯示到 2006 年 3月 31 日止，互聯(lián)網(wǎng)上一共有 80655993 個網(wǎng)站。而單是在 06 年 3 月這一個月里，世界上的網(wǎng)站數(shù)量就增長了 310 萬個。而在 2003 年 8 月所得的調查結果為 4000 萬個，這說明了互聯(lián)網(wǎng)上的網(wǎng) 站數(shù)量在過去的 3 年里就已經(jīng)翻了一番，增長速度 十分 驚人。著名的網(wǎng)站排名的國際網(wǎng)站 在 2007 年 4 月更是收錄了全球大約有34762836735 個網(wǎng)址。 由此，人們在信息海洋中搜索自己所需要的信息的能力顯得愈發(fā)重要，搜索引擎成了人們在網(wǎng)上檢索信息的必要工具。 第一節(jié) 搜索引擎原理 搜索引擎， 應該被定位成 一個計算機應用軟件系統(tǒng)，或者一個網(wǎng)絡應用軟件系統(tǒng)。從網(wǎng)絡用戶的角度看，它根據(jù)用戶提交的類自然語言查詢詞或者短語 ，返回一系列很可能與該查詢相關的網(wǎng)頁信息，供用戶進一步判斷和選取。為了有效地做到這一點，它大致上被分成三個子系統(tǒng)；即網(wǎng)頁搜集，網(wǎng)頁預處理和查詢服務。 網(wǎng)頁搜集主要負責網(wǎng)頁的抓取，由 URL 服務器、爬行器、存儲器、分析器和URL 解析器組成 ， 爬行器是該部分的核心；網(wǎng)頁 預處理 主要負責對網(wǎng)頁內容進行分析，對文檔進行標引并存儲到數(shù)據(jù)庫里，由標引器和分類器組成，該模塊涉及許多文件和數(shù)據(jù)，有關于桶的操作是該部分的核心； 查詢服務 主要負責分析用戶輸入的檢索表達式，匹配相關文檔，把檢索結果返回給用戶，由查詢器和網(wǎng)頁級別評定器組 成，其中網(wǎng)頁等級的計算是該部分的核心。 搜索引擎的主要工作流程是：首先從蜘蛛開始，蜘蛛程序每隔一定的時間自動啟動并讀取網(wǎng)頁 URL服務器上的 URL列表，按深度優(yōu)先或廣度優(yōu)先算法，抓取各 URL所指定的網(wǎng)站，將抓取的網(wǎng)頁分配一個唯一文檔，存入文檔數(shù)據(jù)庫。并將當前頁上的所的超連接存入到 URL服務器中。在進行抓取的同時，切詞器和索引器將已經(jīng)抓取的網(wǎng)頁文檔進行切詞處理，并按詞在網(wǎng)頁中出現(xiàn)的位置和頻率計算權值，然后將切詞結果存入索引數(shù)據(jù)庫。整個抓取工作和索引工作完成后更新整個索引數(shù)據(jù)庫和文檔數(shù)據(jù)庫，這樣用戶就可以查詢最新 的網(wǎng)頁信息。查詢器首先對用戶輸入的信息本科生畢業(yè)設計 2 進行切詞處理，并檢索出所有包含檢索詞的記錄，通過計算網(wǎng)頁權重和級別對查詢記錄進行排序并進行集合運算，最后從文檔數(shù)據(jù)庫中提取各網(wǎng)頁的摘要信息反饋給查詢用戶。 U R L 服務器 爬行器 存儲服務器 資源庫 頁級別評定器 U R L 解析器 標引器 查詢器 分類器 錨庫 詞典庫 索引庫 鏈接庫 桶 桶 桶 桶 桶 桶 Web頁搜索標引入庫用戶查詢圖 1-1-1 搜索引擎通用總體系統(tǒng)結構圖 第二節(jié) 搜索引擎分類 搜索引擎按其工作方式主要可分為三種，分別是全文搜索引擎（ Full Text Search Engine）、目錄索引類搜索引擎（ Search Index/Directory）和元搜索引擎（ Meta Search Engine）。 一、 全文搜索引擎 全文搜索引擎是名副其實的搜索引擎，國外具代表性的有 Google、Fast/AllTheWeb、 AltaVista、 Inktomi、 Teoma、 WiseNut 等，國內著名的有百度（ Baidu）。它們都是通過從互聯(lián)網(wǎng)上提取的各個網(wǎng)站的信息（以網(wǎng)頁文字為主）而建立的數(shù)據(jù)庫中，檢索與用戶查詢條件匹配的相關記錄，然后按一定的排列順序將結果返回給用戶，因此他們是真正的搜索引擎。 本科生畢業(yè)設計 3 圖 1-2-1 全球著名全文搜索引擎 LOGO 二、 目錄索引 目錄索引雖然有搜索功能，但在嚴格意義上算不上是真正的搜索引擎，僅僅是按目錄分類的網(wǎng)站鏈接列表而已。用戶完全可以不用進行關鍵詞（ Keywords）查詢，僅靠分類目錄也可找到需要的信息。目錄索引中最具代表性的莫過于大名鼎鼎的Yahoo 雅虎。其他著名的還有 Open Directory Project（ DMOZ）、 LookSmart、 About等。國內的搜狐、新浪、網(wǎng)易搜索也都屬于這一類。 圖 1-2-2 全球著名目錄索引 LOGO 三、 元搜索引擎 (META Search Engine) 元搜索引擎在接受用戶查詢請求時，同時在其他多個引擎上進行搜索，并將結果返回給用戶。著名的元搜索引擎有 InfoSpace、 Dogpile、 Vivisimo 等，中文元搜索引擎 中具代表性的有搜星搜索引擎。在搜索結果排列方面，有的直接按來源引擎排列搜索結果，如 Dogpile，有的則按自定的規(guī)則將結果重新排列組合，如 Vivisimo。 四、 其他 除上述三大類引擎外，還有以下幾種非主流形式： （一） 集合式搜索引擎：如 HotBot 在 2002 年底推出的引擎。該引擎類似 META搜索引擎，但區(qū)別在于不是同時調用多個引擎進行搜索，而是由用戶從提供的 4 個引擎當中選擇，因此叫它 “集合式 ”搜索引擎更確切些。 （二） 門戶搜索引擎：如 AOL Search、 MSN Search 等雖然提供搜索服務，但自身即沒 有分類目錄也沒有網(wǎng)頁數(shù)據(jù)庫，其搜索結果完全來自其他引擎。 （三） 免費鏈接列表（ Free For All Links，簡稱 FFA）：這類網(wǎng)站一般只簡單地滾動排列鏈接條目，少部分有簡單的分類目錄，不過規(guī)模比起 Yahoo 等目錄索引來要小得多。 （四） 垂直搜索引擎： 有針對性的搜索引擎。 一次搜索的結果可能有成千上萬條，而在這過于龐大的信息群中，有用信息只是其中的小部分。通用搜索引擎的弊端在網(wǎng)絡信息的急劇膨脹下突顯起來，搜索越來越難以控制，用戶需求和市場服務間的巨大反差產生了強大的 “搜索噪音 ”，垂直搜索引擎的應運而生， 成為搜索引擎本科生畢業(yè)設計 4 發(fā)展史上的一塊里程碑。 第三節(jié) 搜索引擎技術的發(fā)展歷史 在互聯(lián)網(wǎng)發(fā)展初期，網(wǎng)站相對較少，信息查找比較容易。然而伴隨互聯(lián)網(wǎng)爆炸性的發(fā)展，普通網(wǎng)絡用戶想找到所需的資料簡直如同大海撈針，這時為滿足大眾信息檢索需求的專業(yè)搜索網(wǎng)站便應運而生了。 現(xiàn)代意義上的搜索引擎的祖先，是 1990 年由蒙特利爾大學學生 Alan Emtage 發(fā)明的 Archie。雖然當時 World Wide Web 還未出現(xiàn)，但網(wǎng)絡中文件傳輸還是相當頻繁的，而且由于大量的文件散布在各個分散的 FTP 主機中，查詢起來非常不便，因此Alan Emtage 想到了開發(fā)一個可以以文件名查找文件的系統(tǒng)，于是便有了 Archie。 Archie 工作原理與現(xiàn)在的搜索引擎已經(jīng)很接近，它依靠腳本程序自動搜索網(wǎng)上的文件，然后對有關信息進行索引，供使用者以一定的表達式查詢。由于 Archie 深受用戶歡迎，受其啟發(fā)，美國內華達 System Computing Services 大學于 1993 年開發(fā)了另一個與之非常相似的搜索工具，不過此時的搜索工具除了索引文件外，已能檢索網(wǎng)頁。 當時， “機器人 ”一詞在編程者中十分流行。電腦 “機器人 ”（ Computer Robot）是指某個能以人類無法 達到的速度不間斷地執(zhí)行某項任務的軟件程序。由于專門用于檢索信息的 “機器人 ”程序象蜘蛛一樣在網(wǎng)絡間爬來爬去，因此，搜索引擎的 “機器人 ”程序 也 被稱為 “蜘蛛 ”程序。 世界上第一個用于監(jiān)測互聯(lián)網(wǎng)發(fā)展規(guī)模的 “機器人 ”程序是 Matthew Gray開發(fā)的World wide Web Wanderer。剛開始它只用來統(tǒng)計互聯(lián)網(wǎng)上的服務器數(shù)量，后來則發(fā)展為能夠檢索網(wǎng)站域名。 與 Wanderer相對應， Martin Koster 于 1993 年 10月創(chuàng)建了 ALIWEB，它是 Archie的 HTTP 版本。 ALIWEB 不使用 “機器人 ”程序，而是靠網(wǎng)站主動提交信息來建立自己的鏈接索引，類似于現(xiàn)在我們熟知的 Yahoo。 隨著互聯(lián)網(wǎng)的迅速發(fā)展，使得檢索所有新出現(xiàn)的網(wǎng)頁變得越來越困難，因此，在 Matthew Gray 的 Wanderer 基礎上，一些編程者將傳統(tǒng)的 “蜘蛛 ”程序工作原理作了些改進。其設想是，既然所有網(wǎng)頁都可能有連向其他網(wǎng)站的鏈接，那么從跟蹤一個網(wǎng)站的鏈接開始，就有可能檢索整個互聯(lián)網(wǎng)。到 1993 年底，一些基于此原理的搜索引擎開始紛紛涌現(xiàn)，其中以 JumpStation、 The World Wide Web Worm（ Goto 的前身，也就是 今天 Overture），和 Repository-Based Software Engineering (RBSE) spider最負盛名。 本科生畢業(yè)設計 5 然而 JumpStation 和 WWW Worm 只是以搜索工具在數(shù)據(jù)庫中找到匹配信息的先后次序排列搜索結果，因此毫無信息關聯(lián)度可言。而 RBSE 是第一個在搜索結果排列中引入關鍵字串匹配程度概念的引擎。 最早現(xiàn)代意義上的搜索引擎出現(xiàn)于 1994 年 7 月。當時 Michael Mauldin 將 John Leavitt 的蜘蛛程序接入到其索引程序中，創(chuàng)建了大家現(xiàn)在熟知的 Lycos。同年 4 月，斯坦福（ Stanford）大學的兩名博士生， David Filo 和美籍華人楊致遠（ Gerry Yang）共同創(chuàng)辦了超級目錄索引 Yahoo，并成功地使搜索引擎的概念深入人心。從此搜索引擎進入了高速發(fā)展時期。目前，互聯(lián)網(wǎng)上有名有姓的搜索引擎已達數(shù)百家，其檢索的信息量也與從前不可同日而語。比如 Yahoo 號稱收錄的網(wǎng)頁達到 200 億 。 隨著互聯(lián)網(wǎng)規(guī)模的急劇膨脹，一家搜索引擎光靠自己單打獨斗已無法適應目前的市場狀況，因此現(xiàn)在搜索引擎之間開始出現(xiàn)了分工協(xié)作，并有了專業(yè)的搜索引擎技術和搜索數(shù)據(jù)庫服務提供商。象國外的 Inktomi（已被 Yahoo 收購），它本身并不是直接面向用戶的搜索引擎，但 像 包括 Overture（原 GoTo，已被 Yahoo 收購）、LookSmart、 MSN、 HotBot 等在內的其他搜索引擎提供全文網(wǎng)頁搜索服務。國內的百度也屬于這一類，搜狐和新浪用的就是它的技術。因此從這個意義上說，它們是搜索引擎的搜索引擎。 第四節(jié) 搜索引擎現(xiàn)狀 隨著網(wǎng) 絡信息 內容的爆炸式增長和形式的不斷翻新，搜索引擎越來越不能滿足網(wǎng)絡使用者 的各種信息需求。從 1996 年起，搜索引擎技術開始注重網(wǎng)頁質量與相關性的結合，這主要是通過三種手段： 是對網(wǎng)上的超鏈結構進行分析，如 INFOSEEK 和 GOOGLE； 是對用戶的點擊行為進行分析，如 DIRECTHIT(被 ASK JEEVES 收購 )； 是與網(wǎng)站目錄相結合。最新的趨勢則是搜索的個性化 、 本地化 和垂直化 。 個性化：入門網(wǎng)站的個性化已經(jīng)比較成熟了，但是搜索引擎的個性化并沒有得到解決，不同的人使用相同的檢索詞得到的結果是相同的。也就是說搜索引擎沒有考慮人的地域、性別、年齡等方面的差別。 DIRECTHIT 等公司一年 前開始了個性化方面的研發(fā)工作，但至今沒有推出任何產品。 垂直化：垂直搜索引擎這種高度目標化、專業(yè)化的搜索引擎的優(yōu)勢在于 :針對性強，對特定范圍的網(wǎng)絡信息的覆蓋率相對較高，具有可靠的技術和信息資源保障，有明確的檢索目標定位，有效地彌補了通用綜合性搜索引擎對專門領域及特定主題信息覆蓋率過低的問題。根據(jù) CNNIC 的調查結果， 2005 年，使用百度和 Google 的本科生畢業(yè)設計 6 用戶達到總量的 90%；而 2006 年這一數(shù)值下降到 87.4%，這其中就有垂直搜索的分流作用。 本地化：本地化是一個比個性化更明顯的趨勢。隨著互聯(lián)網(wǎng)在全球的迅速普 及，綜合性的搜索引擎已經(jīng)不能滿足很多非美國網(wǎng)民的信息需求。近來， YAHOO!、INKTOMI、 LYCOS 等公司不斷推出各國、各地區(qū)的本地搜索網(wǎng)站，搜索的本地化已經(jīng)是勢不可擋。 第五節(jié) 搜索引擎展望 一、技術展望 各大公司都把下一代搜索引擎的查詢方式的創(chuàng) 新 性，作為自己競爭的籌碼，以下是對下一代搜索引擎技術的一些構想。 未來，搜索引擎 技術將重點發(fā)展在以下幾個方面 ： （一） 自然語言理解技術 自然語言理解是計算機科學中的一個富有挑戰(zhàn)性的課題。從計算機科學特別是從人工智能的觀點看，自然語言理解的任務是建立一種計算機模型， 這種計算機模型能夠給出像人那樣理解、分析并回答自然語言。以自然語言理解技術為基礎的新一代搜索引擎，我們稱之為智能搜索引擎。由于它將信息檢索從目前基于關鍵詞層面提高到基于知識 (或概念 )層面，對知識有一定的理解與處理能力，能夠實現(xiàn)分詞技術、同義詞技術、概念搜索、短語識別以及機器翻譯技術等。因而這種搜索引擎具有信息服務的智能化、人性化特征，允許網(wǎng)民采用自然語言進行信息的檢索，為他們提供更方便、更確切的搜索服務。 （二） P2P P2P 是 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)上信息的價值得到極大的提升。 （三） 移動搜索引擎 隨著手機接入互聯(lián)網(wǎng)的能力越來越強，以及移動業(yè)務日益傾向于內容驅動，搜索引擎的移動化也成為不可避免的趨勢 。許多運營商已經(jīng)在其內容網(wǎng)站上使用當?shù)乇究粕厴I(yè)設計 7 搜索引擎來幫助消費者找到所需信息，一些主要的搜索引擎公司如 Google、百度、愛問等已著力于移動搜索，其搜索引擎的移動化版本已經(jīng)問世并開始運營。 （四） 垂直搜索 服務及本地化 垂直搜索引擎的搜索器只搜索特定的主題信息，按預先己經(jīng)定義好的專題有選擇地收集相關的網(wǎng)頁。這樣大大降低了收集信息的難度，提高了信息的質量。由于所收集的學科領域小，信息量相對較少，可以采用 “專家分類標引 ”的方法對收集到的信息進行組織整理，進一步提高信息的質量，建立一個高質量的、專業(yè)信息收集全的數(shù)據(jù)庫。 每一 種 行 業(yè) 都可以做一個垂直搜索。目前搜索領域才剛剛起步，尤其是垂直搜索，還有很大的空間。比如說家電、建材、家居、醫(yī)療健康等等方面，甚至還可以在更細的領域做更加深的搜索。美國去年第四季度出現(xiàn)了專門給老年人 服務的 搜索引擎。 本地搜索前景 也 很好，面臨的挑戰(zhàn)就是把全中國所有的店家信息收集上來需要很多投入。 賽迪顧問執(zhí)行總裁李峻預測，垂直搜索、本地搜索等未來搜索引擎市場仍將保持 30%左右的增長速度。 一些垂直搜索將會成為值得深度挖掘的方向，如旅游搜索、求職搜索等行業(yè)細分的搜索引擎，而且搜索引擎技術和渠道的創(chuàng)新核心還在于商 業(yè)模式的不斷完善。 （五） 多媒體搜索引擎 隨著寬帶技術的發(fā)展，未來的互聯(lián)網(wǎng)是多媒體數(shù)據(jù)的時代。開發(fā)出可查尋圖像、聲音、圖片和電影的搜索引擎是一個新的方向。目前瑞典一家公司已經(jīng)研制推出被稱作 “第五代搜索引擎 ”的動態(tài)的和有聲的多媒體搜索引擎。圖像、視頻將很快取代文本成為互聯(lián)網(wǎng)上主要的信息。 二、市場展望 iResearch 預測到 2007 年中國搜索引擎市場規(guī)模將達到 56.2 億元人民幣，未來3 年的年增長率平均保持在 55%以上 1。中國本土的搜索引擎：百度、中搜、搜狗、一搜等相繼推出后，都取得了不錯的反響，特別是百 度在 2005 年 8 月 5 日正式在納斯達克上市，上市首日股票瘋狂上漲：最高達 151 美元，把搜索引擎的市值推到了高潮。微軟對搜索引擎的研發(fā)也伴隨著大規(guī)模的招兵買馬，微軟亞洲研究院也成立了專門的搜索小組。李開復先生加盟 Google 后，讓很多人預測 Google 一定 會吃掉中 文 搜索引擎這個 巨大 的市場。而李開復先生在閃電加盟后，在 “開復學生網(wǎng) ”上發(fā)表了一篇題為 “Google和中國 -追隨我心的選擇 ”， Google 的搜索文化對技術人員的吸引可見一斑，等等數(shù)字和事件表明，搜索引擎在互聯(lián)網(wǎng)上有著強勁的生命力和發(fā)展?jié)摿Γ瑫r也是互聯(lián) 網(wǎng)公司豐厚利潤的來源之一。 本科生畢業(yè)設計 8 圖 1-5-1 2002-2006 年中國搜索引擎市場規(guī)模及增長 2 2005 年 8 月，法國總統(tǒng)希拉克大張旗鼓地發(fā)布了 “Quaero”計劃，它很快被顯現(xiàn)為一種歐洲的決心 推出與 Google 搜索競爭的相同產品。這款名為 “Quaero”的搜索引擎，不僅能搜索文本，而且還能搜索圖片和視頻。 Quaero 的拉丁文語義是 “我搜索 ”，該項目獲得了 2.5 億歐元資助 (3.3 億美元 )，法德兩國主要技術公司參加了開發(fā)。而在德國，一些德國企業(yè)將參加另外的德國版搜索引擎 “Theseus”的開發(fā)，該引擎 更加集中于文本分析。法德兩國開發(fā)商將在合作、競爭及互補的環(huán)境下實施歐洲新一代搜索引擎的開發(fā)計劃。 和其他許多國家一樣，在日本提起搜索引擎，人們首先想到的是谷歌，此外還有雅虎和微軟麾下的 MSN。根據(jù)今年 3 月的一項調查，在日本檢索服務利用率排名中居首位的是雅虎，其利用率達 64.5%，其次是谷歌和 MSN，日本開發(fā)的 GOO 雖然名列第四，但實際利用率只有 5.5%，與前三名的差距很明顯。中國百度也已經(jīng)進入日本市場，欲與群雄共逐鹿。 其實日本著手開發(fā)搜索引擎要早于美國，日本電信電話公司、日本電氣公司和東芝公司等都曾擁有過 各自獨立的搜索引擎。直到 20 世紀 90 年代后期，這些日本國產搜索引擎還在相互競爭。但隨著美國谷歌的出現(xiàn)，互聯(lián)網(wǎng)信息檢索業(yè)界的格局在 2000 年前后發(fā)生了劇變。谷歌高精確度的檢索服務使日本眾多門戶網(wǎng)站形成了這樣的共識 “搜索引擎依靠谷歌就足夠了 ”，因此日本國產搜索引擎全線敗退。 搜索引擎是遨游網(wǎng)絡世界的必備工具，而其中的基干技術掌握在外國企業(yè)手中。一些日本業(yè)界專家認為，長此以往日本互聯(lián)網(wǎng)搜索業(yè)務未來有可能被外國企業(yè)控制。抱著同樣的危機感，日本政府把國產下一代搜索引擎項目提上了議事日程。經(jīng)濟產業(yè)省 2005 年 12 月 設立了企業(yè)、研究機構和政府部門共同參與的網(wǎng)絡搜索引擎研究小組，負責整理與搜索技術開發(fā)相關的資料， 2006 年 7 月末由大學和 52 家企業(yè)參與本科生畢業(yè)設計 9 的合作項目 “信息大航海計劃 ”正式啟動，準備用 3 年時間開發(fā)出下一代互聯(lián)網(wǎng)搜索引擎，挑戰(zhàn)谷歌等搜索引擎的市場霸主地位，并打算在 2007 年度預算中申請 50 億日元 (約合 4300 萬美元 )作為研發(fā)費用，爭取 5年后使下一代搜索引擎進入實用階段。 據(jù)日本媒體報道，日本下一代搜索引擎不僅能像現(xiàn)在一樣依靠關鍵詞從互聯(lián)網(wǎng)上的信息海洋中提取所需信息，運用現(xiàn)在逐漸普及的電子標簽，還可以及時掌握有關全 球產品的信息，或者以從視頻資料中剪輯的錄音為基礎，檢索音頻資料。日本下一代搜索引擎的終端設備不僅有電腦，還可能是電視機、 手機 、汽車導航儀等。今后只要操縱遙控器就能通過新搜索引擎找到電視節(jié)目中出現(xiàn)過的人物或某個地區(qū)的資料，查詢并購買電視中出現(xiàn)過的某款商品等。 業(yè)內人士指出，雅虎、谷歌、 MSN 每年分別投資數(shù)億美元用于技術研發(fā)，這帶來問題是在目前體制下怎樣才能超越上述企業(yè)的技術水 準。谷歌等搜索引擎霸主的戰(zhàn)略也包含將檢索對象從文本擴展到視頻和音頻資料，此外日本及歐洲大型企業(yè)的不少資深技術人員常跳槽到谷歌和雅虎，這可能有助于谷歌等開發(fā)下一代搜索引擎終端設備。因此像法國的 “Quaero”計劃和日本的 “信息大航海計劃 ”等等的實施能否取得預期效果現(xiàn)在很難準確預料。但不可否認的是：搜索引擎市場將進入一個群雄逐鹿的瘋狂競爭時代。 隨著搜索經(jīng)濟的崛起，人們開始越加關注全球各大搜索引擎的性能、技術和日流量。作為企業(yè)，會根據(jù)搜索引擎的知名度以及日流量來選擇是否要投放廣告等。對于消費者而言，使用互聯(lián)網(wǎng) 搜索引擎是進入網(wǎng)絡世界的一個重要入口，這意味著巨大的商機。微軟將 2007 財政年度的研發(fā)開支預算調高至 75 億美元，較預期高出約 13 億美元，此舉顯示出微軟與 Google、雅虎在互聯(lián)網(wǎng)搜索市場上一決高下的決心。搜索引擎也將不再是技術，而是經(jīng)濟。 本科生畢業(yè)設計 10 第一章 技術詮釋 第一節(jié) HTTP 及 HTML 超文本傳輸協(xié)議（ HTTP）是應用層協(xié)議，由于其簡捷、快速的方式，適用于分布式和合作式超媒體信息系統(tǒng)。自 1990 年起， HTTP 就已經(jīng)被應用于 WWW 全球信息服務系統(tǒng)?？蛻暨M程建立一條同服務器進程的 TCP 連接，然后發(fā)出請求并 讀取服務器進程的應答。服務器進程關閉連接表示本次響應結束。服務器進程返回的內容包含兩個部分，一個 “應答頭 ”（ response header），一個 “應答體 ”（ response body），后者通常是一個 HTML 文件，我們稱之為 “網(wǎng)頁 ”。 通常 HTTP 消息包括客戶機向服務器的請求消息和服務器向客戶機的響應消息。這兩種類型的消息由一個起始行，一個或者多個頭域，一個只是頭域結束的空行和可選的消息體組成。 HTTP 的頭域包括通用頭，請求頭，響應頭和實體頭四個部分。每個頭域由一個域名，冒號（ :）和域值三部分組成。域名是 大小寫無關的，域值前可以添加任何數(shù)量的空格符，頭域可以被擴展為多行，在每行開始處，使用至少一個空格或制表符。 HTTP 協(xié)議采用了請求 /響應模型?？蛻舳讼蚍掌靼l(fā)送一個請求，請求頭包含請求的方法、 URI、協(xié)議版本、以及包含請求修飾符、客戶信息和內容的類似于 MIME的消息結構。服務器以一個狀態(tài)行作為響應，相應的內容包括消息協(xié)議的版本，成功或者錯誤編碼加上包含服務器信息、實體元信息以及可能的實體內容。 Web 服務器的 HTTP 應答一般由以下幾項構成：一個狀態(tài)行，一個或多個應答頭，一個空行，內容文檔。設置 HTTP 應答 頭往往和設置狀態(tài)行中的狀態(tài)代碼結合起來。 典型的請求消息： GET http:/class/download.microtool.de:80/somedata.exe Host:download.microtool.de Accept:*/* Pragma:no-cache Cache-Control:no-cache Referer:http:/class/download.microtool.de/ User-Agent:Mozilla/4.04en(Win95；I；Nav) Range:bytes=554554- 典型的響應消息 ： HTTP/1.0200OK 本科生畢業(yè)設計 11 Date:Mon,31Dec200104:25:57GMT Server:Apache/1.3.14(Unix) Content-type:text/html Last-modified:Tue,17Apr200106:46:28GMT Etag:a030f020ac7c01:1e9f Content-length:39725426 Content-range:bytes554554-40279979/40279980 一個完整的 HTML 文檔以 開始，以 結束。大部分的 HTML命令都像這樣成對出現(xiàn)。 HTML 文檔含有以 開始、以 結束的首部和以 開始、以 結束的主體部分。標題通常由客戶程序顯示在窗口的頂部。 第二節(jié) 網(wǎng)絡蜘蛛 網(wǎng)絡蜘蛛即 Web Spider，是一個很形象的名字。把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng)，那么 Spider 就是在網(wǎng)上爬來爬去的蜘蛛 。網(wǎng)絡蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從網(wǎng)站某一個頁面（通常是首頁）開始，讀取網(wǎng)頁的內容，找到在網(wǎng)頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個網(wǎng)頁，這樣一直循環(huán)下去，直到把這個網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當成一個網(wǎng)站，那么網(wǎng)絡蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。 首先蜘蛛讀取抓取站點的 URL 列表，取出一個站點 URL，將其放入未訪問的URL 列表（ UVURL 列表）中，如果 UVURL 不為空剛從中取出一個 URL 判斷是否已經(jīng)訪問過，若沒有訪問過則讀取此網(wǎng)頁，并進行超鏈分析及內 容分析，并將些頁存入文檔數(shù)據(jù)庫，并將些 URL 放入已訪問 URL 列表（ VURL 列表），直到 UVRL為空為止，此時再抓取其他站點，依次循環(huán)直到所有的站點 URL 列表都抓取完為止。 對于搜索引擎來說，要抓取互聯(lián)網(wǎng)上所有的網(wǎng)頁幾乎是不可能的，從目前公布的數(shù)據(jù)來看，容量最大的搜索引擎也不過是抓取了整個網(wǎng)頁數(shù)量的百分之四十左右。這其中的原因一方面是抓取技術的瓶頸，無法遍歷所有的網(wǎng)頁，有許多網(wǎng)頁無法從其它網(wǎng)頁的鏈接中找到；另一個原因是存儲技術和處理技術的問題，如果按照每個頁面的平均大小為 20K 計算（包含圖片）， 100 億網(wǎng)頁的 容量是 1002000G 字節(jié)，即使能夠存儲，下載也存在問題（按照一臺機器每秒下載 20K 計算，需要 340 臺機器不停的下載一年時間，才能把所有網(wǎng)頁下載完畢）。同時，由于數(shù)據(jù)量太大，在提供搜索時也會有效率方面的影響。因此，許多搜索引擎的網(wǎng)絡蜘蛛只是抓取那些重要的網(wǎng)頁，而在抓取的時候評價重要性主要的依據(jù)是某個網(wǎng)頁的鏈接深度。 本科生畢業(yè)設計 12 在抓取網(wǎng)頁的時候，網(wǎng)絡蜘蛛一般有兩種策略：廣度優(yōu)先和深度優(yōu)先（如下圖所示）。廣度優(yōu)先是指網(wǎng)絡蜘蛛會先抓取起始網(wǎng)頁中鏈接的所有網(wǎng)頁，然后再選擇其中的一個鏈接網(wǎng)頁，繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng) 頁。這是最常用的方式，因為這個方法可以讓網(wǎng)絡蜘蛛并行處理，提高其抓取速度。深度優(yōu)先是指網(wǎng)絡蜘蛛會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉入下一個起始頁，繼續(xù)跟蹤鏈接。這個方法有個優(yōu)點是網(wǎng)絡蜘蛛在設計的時候比較容易。 網(wǎng)絡蜘蛛在訪問網(wǎng)站網(wǎng)頁的時候，經(jīng)常會遇到加密數(shù)據(jù)和網(wǎng)頁權限的問題，有些網(wǎng)頁是需要會員權限才能訪問。當然，網(wǎng)站的所有者可以通過協(xié)議讓網(wǎng)絡蜘蛛不去抓取，但對于一些出售報告的網(wǎng)站，他們希望搜索引擎能搜索到他們的報告，但又不能完全免費的讓搜索者查看，這樣就需要給網(wǎng)絡蜘蛛提供相應的用 戶名和密碼。網(wǎng)絡蜘蛛可以通過所給的權限對這些網(wǎng)頁進行網(wǎng)頁抓取，從而提供搜索。而當搜索者點擊查看該網(wǎng)頁的時候，同樣需要搜索者提供相應的權限驗證。 網(wǎng)絡蜘蛛需要抓取網(wǎng)頁，不同于一般的訪問，如果控制不好，則會引起網(wǎng)站服務器負擔過重。有多種方法可以讓網(wǎng)站和網(wǎng)絡蜘蛛進行交流。一方面讓網(wǎng)站管理員了解網(wǎng)絡蜘蛛都來自哪兒，做了些什么，另一方面也告訴網(wǎng)絡蜘蛛哪些網(wǎng)頁不應該抓取，哪些網(wǎng)頁應該更新。 每個網(wǎng)絡蜘蛛都有自己的名字，在抓取網(wǎng)頁的時候，都會向網(wǎng)站標明自己的身份。網(wǎng)絡蜘蛛在抓取網(wǎng)頁的時候會發(fā)送一個請求，這個請求中就有一 個字段為 User agent，用于標識此網(wǎng)絡蜘蛛的身份。例如 Google 網(wǎng)絡蜘蛛的標識為 GoogleBot，Baidu 網(wǎng)絡蜘蛛的標識為 BaiDuSpider， Yahoo 網(wǎng)絡蜘蛛的標識為 Inktomi Slurp。如果在網(wǎng)站上有訪問日志記錄，網(wǎng)站管理員就能知道，哪些搜索引擎的網(wǎng)絡蜘蛛過來過，什么時候過來的，以及讀了多少數(shù)據(jù)等等。如果網(wǎng)站管理員發(fā)現(xiàn)某個蜘蛛有問題，就通過其標識來和其所有者聯(lián)系。 網(wǎng)絡蜘蛛進入一個網(wǎng)站，一般會訪問一個特殊的文本文件 Robots.txt，這個文件一般放在網(wǎng)站服務器的根目錄下，如： /robots.txt 。網(wǎng)站管理員可以通過 robots.txt 來定義哪些目錄網(wǎng)絡蜘蛛不能訪問，或者哪些目錄對于某些特定的網(wǎng)絡蜘蛛不能訪問。例如有些網(wǎng)站的可執(zhí)行文件目錄和臨時文件目錄不希望被搜索引擎搜索到，那么網(wǎng)站管理員就可以把這些目錄定義為拒絕訪問目錄。Robots.txt 語法很簡單，例如如果對目錄沒有任何限制，可以用以下兩行來描述： User-agent: * Disallow: 當然， Robots.txt 只是一個協(xié)議，如果網(wǎng)絡蜘蛛的設計者不遵循這個協(xié)議 ，網(wǎng)站管理員也無法阻止網(wǎng)絡蜘蛛對于某些頁面的訪問，但一般的網(wǎng)絡蜘蛛都會遵循這些協(xié)議，而且網(wǎng)站管理員還可以通過其它方式來拒絕網(wǎng)絡蜘蛛對某些網(wǎng)頁的抓取。 本科生畢業(yè)設計 13 第三節(jié) 網(wǎng)頁 噪聲 當 Web 中獲取所需信息的同時， 會常常看見大量和所關心內容無關的導航條、廣告信息、版權信息以及調查問卷等，稱之為 “噪 聲 ”內容。 在某些情況下 ，可能從這些噪音內容中得到一些意外的驚喜； 但多數(shù) 時候， 因 這些 噪聲 消耗 掉了很多的 注意力。同時，噪 聲 內容通常伴隨著相關的超鏈。因此，噪 聲 會導致相互鏈接的網(wǎng)頁常常并無內容相關性。這樣，網(wǎng)頁內容的混亂不僅給基于網(wǎng)頁內容的 研究工作帶來困難，也給基于網(wǎng)頁超鏈指向的研究工作帶來困難。另外，隨著 Web 各種研究與應用的深入發(fā)展，僅僅是原始網(wǎng)頁內容已經(jīng)不能滿足需求，還要求能夠提供便于計算機處理的元數(shù)據(jù)信息，例如關鍵詞、摘要、網(wǎng)頁內容類別等。然而，現(xiàn)在大部分網(wǎng)頁仍然是普通 HTML 網(wǎng)頁，并不包含必要的元數(shù)據(jù)。 因 此，本節(jié)討論一個網(wǎng)頁表示模型建立和實現(xiàn)的方法，這一方面使我們能夠自動從網(wǎng)頁中提取相關的元數(shù)據(jù)，另一方面也去除了和網(wǎng)頁主題內容無關的噪音內容，進而在原始 Web 上搭建一個噪 聲小、描述清晰、更易于處理和利用的網(wǎng)頁信息平臺。 在網(wǎng)頁分類領域 ，由于噪 聲 內容與主題無關，訓練集中的噪 聲 內容會導致各個類別的特征不夠明顯，而待分類網(wǎng)頁中的噪 聲 內容則會導致該網(wǎng)頁類別不明確，因而影響了網(wǎng)頁自動分類的效果。因此提出了通過去掉網(wǎng)頁中的噪 聲 內容來提高網(wǎng)頁分類質量的方法。 在網(wǎng)頁信息提取領域，自動識別模式的方法必須要從整個網(wǎng)頁中提取模式，而不是只針對主題內容提取。因此，在凈化后的網(wǎng)頁上作信息提取不僅可以排除噪 聲信息對信息提取的干擾，提高信息提取的準確性，而且可以使得網(wǎng)頁中的結構簡單化，提高信息提取的效率。 上述分析我們看到， 網(wǎng)頁 噪 聲 對基于網(wǎng)頁的研究工作的影響是普遍 而嚴重的，雖然各個領域采用的方法各不相同，但處理的目的都是為了去除網(wǎng)頁中的噪 聲 內容，得到真正的主題內容。 第四節(jié) 頁面分析 由于 WWW網(wǎng)上的信息主要是以 HTML文檔的形式存放的，因此要根據(jù) HTML文檔的特點，對其進行掃描分析，以提取信息。 HTML文檔有五個定義好的組件 : 、文本 本科生畢業(yè)設計 14 、注釋 、簡單標簽 、起始標簽 、結束標簽 文本就是在 HTML頁面上看到的 詞句的內容。除了腳本代碼， HTML文檔中的所有數(shù)據(jù)，只要不是標簽的組成部分，都被認為是文本。文本是格式化的， 并且受包圍它的標簽的控制。就像前面所提到的那樣，如果數(shù)據(jù)位于文本之外，將不會被看作文本。但是程序在理解 HTML頁面時，腳本代碼具有與文本相似的特性。腳本代碼包含在標簽 之間。確保搜索引擎程序不會將腳本代碼與文本數(shù)據(jù)混淆是很重要的。 文本實際上就是顯示在瀏覽器中的文字，其顯示方式由包圍它的標簽來網(wǎng)以決定。根據(jù)本課題的要求，文本無疑是我們所需要的重要的信息源之一。頁相關的 主題是通過文本來表達的，所以文本信息必須被完全提取出來，便進一步處理。 注釋表示 HTML文檔中不會顯示給用戶的那部分內容。他們通常是 HTML程序員所做的說明，這些說明通常是表達編程思路的，所以這類數(shù)據(jù)對本課題來說是毫無用處。因此在解析 HTML文檔時，將注釋忽略。簡單標簽是由單個表示的 HTML標簽。最普遍的簡單標簽是行中斷符 ()標簽和圖像標簽 ( )，它們都沒有相應的結束標簽。簡單標簽主要是用來控制顯示格式或使用圖像美化界面用的。 大多數(shù) HTML標簽都是由開始標簽和結束標簽組成的。開始標簽非常 像簡單標簽。開始標簽與簡單標簽直接的唯一區(qū)別是 :開始標簽有一個相應的結束標簽，該結束標簽出現(xiàn)在后面。開始標簽和結束標簽用來控制其所包含的 HTML代碼的功能。 在所有的開始和結束標簽中，標簽 是最有用的。標簽 在 HTML中叫做鏈接標簽，它決定了當在瀏覽器中點擊該標簽的文本時所要打開的網(wǎng)頁的 URL。下面是一個例子 : Click Here 從上面的例子中我們可以看出，標識它所鏈接的 URL是該標簽的 href屬性決定，href的值就代表了一個 URL. Href屬性值有兩種表達方式 :一種是絕對路徑，也就是說它的值是一個完整的 URL， 程序可以直接使用它 ；另一種相對路徑，它的表示方式只有目錄或文件名，表示相對于木網(wǎng)頁的所在目錄的位置。使用相對路徑的目的是提高網(wǎng)頁的可移植性。標簽 中的鏈接并不是唯一將用戶帶到其它頁面的基礎結構標簽。 Web站點還能建立圖像映像，當用戶點擊它們時，也能將用戶帶到相應的新頁面。圖像映像由客戶端和服務器圖像映像組成，但是服務器圖像映像幾乎完全被客戶端所取代。這是因為服務器端的圖像 映像，需要一個服務器插件來注冊用戶本科生畢業(yè)設計 15 點擊的圖像區(qū)域。而這在客戶端圖像映像中是完全包含在 HTML文件中 3。 客戶端圖像映像不需要服務器端的腳本表示來解釋可多處點擊的圖像的 hot”區(qū)。實際上，客戶端圖像映像比服務器端圖像映像更為有效，而且還允許訪問者在Web瀏覽器的狀態(tài)區(qū)中看到映像區(qū)域真正關聯(lián)的 URL。該狀態(tài)文本還會在用戶鼠標在圖像映像區(qū)域移動的時候出現(xiàn)。客戶端映像圖像將包含一個如下所示的映像。該映像將每個圖像區(qū)域鏈接到一個 URL: 在該 HTML文件的后面，該映像以類似于下面的方式使用 : 通過以上分析圖像映像當中的超級鏈接可以由圖像的 簡單標簽中的 href屬性得到。除了以上兩種情況外，框架中的 src屬性也可以設置超級鏈接?？蚣軜撕瀸儆陂_始標簽和結束標簽，下面是一個例子。 在上面的例子中可以看出，該標簽中有一個名為 src的屬性， 代表了該框架中應顯示的網(wǎng)頁鏈接，在網(wǎng)頁中搜索鏈接時，不應遺漏此類鏈接。需要說明的是，窗體、腳本語言代碼和網(wǎng)頁中嵌入式對象也可以提供鏈接功能。但是，它們主要是提供一些特殊領域的特殊功能的應用。窗體主要是用來收集用戶信息，用戶信息是瀏覽網(wǎng)頁的人根據(jù)自己的實際情況填寫，例如，用戶名和密碼等。在這些用戶信息不全的情況下，返回的網(wǎng)頁通常顯示的是錯誤的信息的頁面。這對本文所研究的垂直搜索引擎來說是毫無意義的，因此，我們對表單不作處理。至于腳本語言代碼，通常是網(wǎng)頁編寫者按照自己的意愿和邏輯，用腳本