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

《畢業(yè)設(shè)計論文 搜索引擎》由會員分享，可在線閱讀，更多相關(guān)《畢業(yè)設(shè)計論文 搜索引擎（68頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、目 錄 第一章 課題背景知識 .(1) 第一節(jié) 搜索引擎原理 .(1) 第二節(jié) 搜索引擎分類 .(2) 第三節(jié) 搜索引擎技術(shù)的發(fā)展歷史 .(4) 第四節(jié) 搜索引擎現(xiàn)狀 .(5) 第五節(jié) 搜索引擎展望 .(6) 第二章 技術(shù)詮釋 .(10) 第一節(jié) HTTP 及 HTML .(10) 第二節(jié) 網(wǎng)絡(luò)蜘蛛 .(11) 第三節(jié) 網(wǎng)頁噪聲 .(13) 第四節(jié) 頁面分析 .(13) 第五節(jié) 中文分詞 .(16) 第六節(jié) 布爾代數(shù) .(19) 第七節(jié) CGI.(19) 第八節(jié) SOCKECT 網(wǎng)絡(luò)編程 .(20) 第三章 TOKING 海量網(wǎng)頁搜索系統(tǒng)體系結(jié)構(gòu)及實現(xiàn) .(21) 第一節(jié) 結(jié)構(gòu)設(shè)計 .(21)

2、 第二節(jié) 數(shù)據(jù)流圖 .(22) 第三節(jié) 網(wǎng)頁抓取部分 .(31) 第四節(jié) 網(wǎng)頁預(yù)處理部分 .(35) 第五節(jié) 信息查詢服務(wù)部分 .(42) 第六節(jié) 用戶反饋 .(46) 第七節(jié) 功能拓展 .(46) 第八節(jié) 優(yōu)化用戶感受 .(50) 第四章 系統(tǒng)測評 .(52) 第一節(jié) 抓取速度 .(52) 第二節(jié) 分詞效率 .(52) 第三節(jié) 搜索評價 .(53) 參考文獻 .(54) 致 謝 .(55) 附 錄 .(56) 本科生畢業(yè)設(shè)計 1 第一章 課題背景知識 70 年代中期，美國國防部高級研究計劃局 DARPA (Defense Advanced Research Projects Agency)開

3、始了互聯(lián)網(wǎng)技術(shù)的研究。而 WWW (World Wide Web)自 1989 年 誕生以來，近二十年來發(fā)展迅猛，它已成為人類社會信息資源中的一個重要組成部 分，越來越多的社會信息資源實體開始選擇 Web 作為其載體。 著名的 netcraft(via Digg)剛剛完成了最新的互聯(lián)網(wǎng)調(diào)查，結(jié)果顯示到 2006 年 3 月 31 日止，互聯(lián)網(wǎng)上一共有 80655993 個網(wǎng)站。而單是在 06 年 3 月這一個月里， 世界上的網(wǎng)站數(shù)量就增長了 310 萬個。而在 2003 年 8 月所得的調(diào)查結(jié)果為 4000 萬 個，這說明了互聯(lián)網(wǎng)上的網(wǎng)站數(shù)量在過去的 3 年里就已經(jīng)翻了一番，增長速度十分 驚人

4、。著名的網(wǎng)站排名的國際網(wǎng)站 在 2007 年 4 月更是收錄了全球 大約有 34762836735 個網(wǎng)址。由此，人們在信息海洋中搜索自己所需要的信息的能 力顯得愈發(fā)重要，搜索引擎成了人們在網(wǎng)上檢索信息的必要工具。 第一節(jié) 搜索引擎原理 搜索引擎，應(yīng)該被定位成一個計算機應(yīng)用軟件系統(tǒng)，或者一個網(wǎng)絡(luò)應(yīng)用軟件系 統(tǒng)。從網(wǎng)絡(luò)用戶的角度看，它根據(jù)用戶提交的類自然語言查詢詞或者短語，返回一 系列很可能與該查詢相關(guān)的網(wǎng)頁信息，供用戶進一步判斷和選取。為了有效地做到 這一點，它大致上被分成三個子系統(tǒng)；即網(wǎng)頁搜集，網(wǎng)頁預(yù)處理和查詢服務(wù)。 網(wǎng)頁搜集主要負責網(wǎng)頁的抓取，由 URL 服務(wù)器、爬行器、存儲器、分析器和

5、URL 解析器組成， 爬行器是該部分的核心；網(wǎng)頁預(yù)處理主要負責對網(wǎng)頁內(nèi)容進行 分析，對文檔進行標引并存儲到數(shù)據(jù)庫里，由標引器和分類器組成，該模塊涉及許 多文件和數(shù)據(jù)，有關(guān)于桶的操作是該部分的核心；查詢服務(wù)主要負責分析用戶輸入 的檢索表達式，匹配相關(guān)文檔，把檢索結(jié)果返回給用戶，由查詢器和網(wǎng)頁級別評定 器組成，其中網(wǎng)頁等級的計算是該部分的核心。 搜索引擎的主要工作流程是：首先從蜘蛛開始，蜘蛛程序每隔一定的時間自動 啟動并讀取網(wǎng)頁URL服務(wù)器上的URL列表，按深度優(yōu)先或廣度優(yōu)先算法，抓取各 URL所指定的網(wǎng)站，將抓取的網(wǎng)頁分配一個唯一文檔，存入文檔數(shù)據(jù)庫。并將當前 頁上的所的超連接存入到URL服務(wù)器

6、中。在進行抓取的同時，切詞器和索引器將已 經(jīng)抓取的網(wǎng)頁文檔進行切詞處理，并按詞在網(wǎng)頁中出現(xiàn)的位置和頻率計算權(quán)值，然 后將切詞結(jié)果存入索引數(shù)據(jù)庫。整個抓取工作和索引工作完成后更新整個索引數(shù)據(jù) 庫和文檔數(shù)據(jù)庫，這樣用戶就可以查詢最新的網(wǎng)頁信息。查詢器首先對用戶輸入的 本科生畢業(yè)設(shè)計 2 信息進行切詞處理，并檢索出所有包含檢索詞的記錄，通過計算網(wǎng)頁權(quán)重和級別對 查詢記錄進行排序并進行集合運算，最后從文檔數(shù)據(jù)庫中提取各網(wǎng)頁的摘要信息反 饋給查詢用戶。 URL服 務(wù) 器 爬 行 器 存 儲 服 務(wù) 器 資 源 庫 頁 級 別 評 定 器 URL解 析 器 標 引 器 查 詢 器 分 類 器 錨 庫 詞

7、典 庫 索 引 庫 鏈 接 庫 桶 桶 桶 桶 桶 桶 Web 頁搜 索 標引 入庫 用戶 查詢 圖 1-1-1 搜索引擎通用總體系統(tǒng)結(jié)構(gòu)圖 第二節(jié) 搜索引擎分類 搜索引擎按其工作方式主要可分為三種，分別是全文搜索引擎（Full Text Search Engine） 、目錄索引類搜索引擎（Search Index/Directory）和元搜索引擎 （Meta Search Engine） 。 一、全文搜索引擎 全文搜索引擎是名副其實的搜索引擎，國外具代表性的有 Google、Fast/AllTheWeb、AltaVista、Inktomi、Teoma 、WiseNut 等，國內(nèi)著名的 有百度

8、（Baidu） 。它們都是通過從互聯(lián)網(wǎng)上提取的各個網(wǎng)站的信息（以網(wǎng)頁文字為 主）而建立的數(shù)據(jù)庫中，檢索與用戶查詢條件匹配的相關(guān)記錄，然后按一定的排列 順序?qū)⒔Y(jié)果返回給用戶，因此他們是真正的搜索引擎。 本科生畢業(yè)設(shè)計 3 圖 1-2-1 全球著名全文搜索引擎 LOGO 二、目錄索引 目錄索引雖然有搜索功能，但在嚴格意義上算不上是真正的搜索引擎，僅僅是 按目錄分類的網(wǎng)站鏈接列表而已。用戶完全可以不用進行關(guān)鍵詞（Keywords）查 詢，僅靠分類目錄也可找到需要的信息。目錄索引中最具代表性的莫過于大名鼎鼎 的 Yahoo 雅虎。其他著名的還有 Open Directory Project（DMOZ）

9、 、 LookSmart、 About 等。國內(nèi)的搜狐、新浪、網(wǎng)易搜索也都屬于這一類。 圖 1-2-2 全球著名目錄索引 LOGO 三、元搜索引擎 (META Search Engine) 元搜索引擎在接受用戶查詢請求時，同時在其他多個引擎上進行搜索，并將結(jié) 果返回給用戶。著名的元搜索引擎有 InfoSpace、Dogpile、Vivisimo 等，中文元搜 索引擎中具代表性的有搜星搜索引擎。在搜索結(jié)果排列方面，有的直接按來源引擎 排列搜索結(jié)果，如 Dogpile，有的則按自定的規(guī)則將結(jié)果重新排列組合，如 Vivisimo。 四、其他 除上述三大類引擎外，還有以下幾種非主流形式： （一）集合式

10、搜索引擎：如 HotBot 在 2002 年底推出的引擎。該引擎類似 META 搜索引擎，但區(qū)別在于不是同時調(diào)用多個引擎進行搜索，而是由用戶從提 供的 4 個引擎當中選擇，因此叫它“集合式” 搜索引擎更確切些。 （二）門戶搜索引擎：如 AOL Search、MSN Search 等雖然提供搜索服務(wù)，但 自身即沒有分類目錄也沒有網(wǎng)頁數(shù)據(jù)庫，其搜索結(jié)果完全來自其他引擎。 （三）免費鏈接列表（Free For All Links，簡稱 FFA）：這類網(wǎng)站一般只簡單 地滾動排列鏈接條目，少部分有簡單的分類目錄，不過規(guī)模比起 Yahoo 等目錄索 引來要小得多。 （四）垂直搜索引擎：有針對性的搜索引擎。

11、一次搜索的結(jié)果可能有成千上萬 條，而在這過于龐大的信息群中，有用信息只是其中的小部分。通用搜索引擎的弊 端在網(wǎng)絡(luò)信息的急劇膨脹下突顯起來，搜索越來越難以控制，用戶需求和市場服務(wù) 本科生畢業(yè)設(shè)計 4 間的巨大反差產(chǎn)生了強大的“搜索噪音” ，垂直搜索引擎的應(yīng)運而生，成為搜索引擎 發(fā)展史上的一塊里程碑。 第三節(jié) 搜索引擎技術(shù)的發(fā)展歷史 在互聯(lián)網(wǎng)發(fā)展初期，網(wǎng)站相對較少，信息查找比較容易。然而伴隨互聯(lián)網(wǎng)爆炸 性的發(fā)展，普通網(wǎng)絡(luò)用戶想找到所需的資料簡直如同大海撈針，這時為滿足大眾信 息檢索需求的專業(yè)搜索網(wǎng)站便應(yīng)運而生了。 現(xiàn)代意義上的搜索引擎的祖先，是 1990 年由蒙特利爾大學(xué)學(xué)生 Alan Emtag

12、e 發(fā)明的 Archie。雖然當時 World Wide Web 還未出現(xiàn)，但網(wǎng)絡(luò)中文件傳輸還是相當 頻繁的，而且由于大量的文件散布在各個分散的 FTP 主機中，查詢起來非常不便， 因此 Alan Emtage 想到了開發(fā)一個可以以文件名查找文件的系統(tǒng)，于是便有了 Archie。 Archie 工作原理與現(xiàn)在的搜索引擎已經(jīng)很接近，它依靠腳本程序自動搜索網(wǎng)上 的文件，然后對有關(guān)信息進行索引，供使用者以一定的表達式查詢。由于 Archie 深受用戶歡迎，受其啟發(fā)，美國內(nèi)華達 System Computing Services 大學(xué)于 1993 年 開發(fā)了另一個與之非常相似的搜索工具，不過此時的搜索

13、工具除了索引文件外，已 能檢索網(wǎng)頁。 當時， “機器人 ”一詞在編程者中十分流行。電腦 “機器人”（Computer Robot）是 指某個能以人類無法達到的速度不間斷地執(zhí)行某項任務(wù)的軟件程序。由于專門用于 檢索信息的“ 機器人” 程序象蜘蛛一樣在網(wǎng)絡(luò)間爬來爬去，因此，搜索引擎的“機器 人”程序也被稱為 “蜘蛛”程序。 世界上第一個用于監(jiān)測互聯(lián)網(wǎng)發(fā)展規(guī)模的“機器人” 程序是 Matthew Gray 開發(fā) 的 World wide Web Wanderer。剛開始它只用來統(tǒng)計互聯(lián)網(wǎng)上的服務(wù)器數(shù)量，后來 則發(fā)展為能夠檢索網(wǎng)站域名。 與 Wanderer 相對應(yīng)，Martin Koster 于 1

14、993 年 10 月創(chuàng)建了 ALIWEB，它是 Archie 的 HTTP 版本。ALIWEB 不使用“機器人” 程序，而是靠網(wǎng)站主動提交信息來 建立自己的鏈接索引，類似于現(xiàn)在我們熟知的 Yahoo。 隨著互聯(lián)網(wǎng)的迅速發(fā)展，使得檢索所有新出現(xiàn)的網(wǎng)頁變得越來越困難，因此， 在 Matthew Gray 的 Wanderer 基礎(chǔ)上，一些編程者將傳統(tǒng)的 “蜘蛛”程序工作原理作 了些改進。其設(shè)想是，既然所有網(wǎng)頁都可能有連向其他網(wǎng)站的鏈接，那么從跟蹤一 個網(wǎng)站的鏈接開始，就有可能檢索整個互聯(lián)網(wǎng)。到 1993 年底，一些基于此原理的 搜索引擎開始紛紛涌現(xiàn)，其中以 JumpStation、The Worl

15、d Wide Web Worm（Goto 本科生畢業(yè)設(shè)計 5 的前身，也就是今天 Overture） ，和 Repository-Based Software Engineering (RBSE) spider 最負盛名。 然而 JumpStation 和 WWW Worm 只是以搜索工具在數(shù)據(jù)庫中找到匹配信息的 先后次序排列搜索結(jié)果，因此毫無信息關(guān)聯(lián)度可言。而 RBSE 是第一個在搜索結(jié) 果排列中引入關(guān)鍵字串匹配程度概念的引擎。 最早現(xiàn)代意義上的搜索引擎出現(xiàn)于 1994 年 7 月。當時 Michael Mauldin 將 John Leavitt 的蜘蛛程序接入到其索引程序中，創(chuàng)建了大家現(xiàn)

16、在熟知的 Lycos。同年 4 月，斯坦福（Stanford ）大學(xué)的兩名博士生， David Filo 和美籍華人楊致遠 （Gerry Yang）共同創(chuàng)辦了超級目錄索引 Yahoo，并成功地使搜索引擎的概念深入 人心。從此搜索引擎進入了高速發(fā)展時期。目前，互聯(lián)網(wǎng)上有名有姓的搜索引擎已 達數(shù)百家，其檢索的信息量也與從前不可同日而語。比如 Yahoo 號稱收錄的網(wǎng)頁 達到 200 億。 隨著互聯(lián)網(wǎng)規(guī)模的急劇膨脹，一家搜索引擎光靠自己單打獨斗已無法適應(yīng)目前 的市場狀況，因此現(xiàn)在搜索引擎之間開始出現(xiàn)了分工協(xié)作，并有了專業(yè)的搜索引擎 技術(shù)和搜索數(shù)據(jù)庫服務(wù)提供商。象國外的 Inktomi（已被 Yaho

17、o 收購） ，它本身并 不是直接面向用戶的搜索引擎，但像包括 Overture（原 GoTo，已被 Yahoo 收購） 、 LookSmart、 MSN、HotBot 等在內(nèi)的其他搜索引擎提供全文網(wǎng)頁搜索服務(wù)。國內(nèi)的 百度也屬于這一類，搜狐和新浪用的就是它的技術(shù)。因此從這個意義上說，它們是 搜索引擎的搜索引擎。 第四節(jié) 搜索引擎現(xiàn)狀 隨著網(wǎng)絡(luò)信息內(nèi)容的爆炸式增長和形式的不斷翻新，搜索引擎越來越不能滿足 網(wǎng)絡(luò)使用者的各種信息需求。從 1996 年起，搜索引擎技術(shù)開始注重網(wǎng)頁質(zhì)量與相 關(guān)性的結(jié)合，這主要是通過三種手段： 是對網(wǎng)上的超鏈結(jié)構(gòu)進行分析，如 INFOSEEK 和 GOOGLE； 是對用戶

18、的點擊行為進行分析，如 DIRECTHIT(被 ASK JEEVES 收購)； 是與網(wǎng)站目錄相結(jié)合。最新的趨勢則是搜索的個性化、本地化和垂直化。 個性化：入門網(wǎng)站的個性化已經(jīng)比較成熟了，但是搜索引擎的個性化并沒有得 到解決，不同的人使用相同的檢索詞得到的結(jié)果是相同的。也就是說搜索引擎沒有 考慮人的地域、性別、年齡等方面的差別。DIRECTHIT 等公司一年前開始了個性 化方面的研發(fā)工作，但至今沒有推出任何產(chǎn)品。 垂直化：垂直搜索引擎這種高度目標化、專業(yè)化的搜索引擎的優(yōu)勢在于:針對 本科生畢業(yè)設(shè)計 6 性強，對特定范圍的網(wǎng)絡(luò)信息的覆蓋率相對較高，具有可靠的技術(shù)和信息資源保障， 有明確的檢索目標定

19、位，有效地彌補了通用綜合性搜索引擎對專門領(lǐng)域及特定主題 信息覆蓋率過低的問題。根據(jù) CNNIC 的調(diào)查結(jié)果，2005 年，使用百度和 Google 的用戶達到總量的 90%;而 2006 年這一數(shù)值下降到 87.4%，這其中就有垂直搜索的 分流作用。 本地化：本地化是一個比個性化更明顯的趨勢。隨著互聯(lián)網(wǎng)在全球的迅速普及， 綜合性的搜索引擎已經(jīng)不能滿足很多非美國網(wǎng)民的信息需求。近來， YAHOO!、INKTOMI、LYCOS 等公司不斷推出各國、各地區(qū)的本地搜索網(wǎng)站，搜 索的本地化已經(jīng)是勢不可擋。 第五節(jié) 搜索引擎展望 一、技術(shù)展望 各大公司都把下一代搜索引擎的查詢方式的創(chuàng)新性，作為自己競爭的籌

20、碼，以 下是對下一代搜索引擎技術(shù)的一些構(gòu)想。 未來，搜索引擎技術(shù)將重點發(fā)展在以下幾個方面： （一）自然語言理解技術(shù) 自然語言理解是計算機科學(xué)中的一個富有挑戰(zhàn)性的課題。從計算機科學(xué)特別是 從人工智能的觀點看，自然語言理解的任務(wù)是建立一種計算機模型，這種計算機模 型能夠給出像人那樣理解、分析并回答自然語言。以自然語言理解技術(shù)為基礎(chǔ)的新 一代搜索引擎，我們稱之為智能搜索引擎。由于它將信息檢索從目前基于關(guān)鍵詞層 面提高到基于知識(或概念)層面，對知識有一定的理解與處理能力，能夠?qū)崿F(xiàn)分詞 技術(shù)、同義詞技術(shù)、概念搜索、短語識別以及機器翻譯技術(shù)等。因而這種搜索引擎 具有信息服務(wù)的智能化、人性化特征，允許網(wǎng)民

21、采用自然語言進行信息的檢索，為 他們提供更方便、更確切的搜索服務(wù)。 （二）P2P P2P 是 peer-to-peer 的縮寫，意為對等網(wǎng)絡(luò)。其宗旨在于加強網(wǎng)絡(luò)上人與人的 交流、在文件交換、分布計算等方面大有前途。長久以來，人們習(xí)慣的互聯(lián)網(wǎng)是以 服務(wù)器為中心，人們向服務(wù)器發(fā)送請求，然后瀏覽服務(wù)器回應(yīng)的信息。而 P2P 所 包含的技術(shù)就是使聯(lián)網(wǎng)電腦能夠進行數(shù)據(jù)交換，但數(shù)據(jù)是存儲在每臺電腦里，而不 是存儲在既昂貴又容易受到攻擊的服務(wù)器里。網(wǎng)絡(luò)成員可以在網(wǎng)絡(luò)數(shù)據(jù)庫里自由搜 索、更新、回答和傳送數(shù)據(jù)。所有人都共享了他們認為最有價值的東西，這將使互 聯(lián)網(wǎng)上信息的價值得到極大的提升。 本科生畢業(yè)設(shè)計 7

22、（三）移動搜索引擎 隨著手機接入互聯(lián)網(wǎng)的能力越來越強，以及移動業(yè)務(wù)日益傾向于內(nèi)容驅(qū)動，搜 索引擎的移動化也成為不可避免的趨勢。許多運營商已經(jīng)在其內(nèi)容網(wǎng)站上使用當?shù)?搜索引擎來幫助消費者找到所需信息，一些主要的搜索引擎公司如 Google、百度、 愛問等已著力于移動搜索，其搜索引擎的移動化版本已經(jīng)問世并開始運營。 （四）垂直搜索服務(wù)及本地化 垂直搜索引擎的搜索器只搜索特定的主題信息，按預(yù)先己經(jīng)定義好的專題有選 擇地收集相關(guān)的網(wǎng)頁。這樣大大降低了收集信息的難度，提高了信息的質(zhì)量。由于 所收集的學(xué)科領(lǐng)域小，信息量相對較少，可以采用“ 專家分類標引” 的方法對收集到 的信息進行組織整理，進一步提高信息

23、的質(zhì)量，建立一個高質(zhì)量的、專業(yè)信息收集 全的數(shù)據(jù)庫。 每一種行業(yè)都可以做一個垂直搜索。目前搜索領(lǐng)域才剛剛起步，尤其是垂直搜 索，還有很大的空間。比如說家電、建材、家居、醫(yī)療健康等等方面，甚至還可以 在更細的領(lǐng)域做更加深的搜索。美國去年第四季度出現(xiàn)了專門給老年人服務(wù)的搜索 引擎。本地搜索前景也很好，面臨的挑戰(zhàn)就是把全中國所有的店家信息收集上來需 要很多投入。賽迪顧問執(zhí)行總裁李峻預(yù)測，垂直搜索、本地搜索等未來搜索引擎市 場仍將保持 30%左右的增長速度。 一些垂直搜索將會成為值得深度挖掘的方向，如旅游搜索、求職搜索等行業(yè)細 分的搜索引擎，而且搜索引擎技術(shù)和渠道的創(chuàng)新核心還在于商業(yè)模式的不斷完善。

24、（五）多媒體搜索引擎 隨著寬帶技術(shù)的發(fā)展，未來的互聯(lián)網(wǎng)是多媒體數(shù)據(jù)的時代。開發(fā)出可查尋圖像、 聲音、圖片和電影的搜索引擎是一個新的方向。目前瑞典一家公司已經(jīng)研制推出被 稱作“第五代搜索引擎 ”的動態(tài)的和有聲的多媒體搜索引擎。圖像、視頻將很快取代 文本成為互聯(lián)網(wǎng)上主要的信息。 二、市場展望 iResearch 預(yù)測到 2007 年中國搜索引擎市場規(guī)模將達到 56.2 億元人民幣，未來 3 年的年增長率平均保持在 55%以上 1。中國本土的搜索引擎：百度、中搜、搜狗、 一搜等相繼推出后，都取得了不錯的反響，特別是百度在 2005 年 8 月 5 日正式在 納斯達克上市，上市首日股票瘋狂上漲：最高達

25、 151 美元，把搜索引擎的市值推到 了高潮。微軟對搜索引擎的研發(fā)也伴隨著大規(guī)模的招兵買馬，微軟亞洲研究院也成 立了專門的搜索小組。李開復(fù)先生加盟 Google 后，讓很多人預(yù)測 Google 一定會吃 掉中文搜索引擎這個巨大的市場。而李開復(fù)先生在閃電加盟后，在“開復(fù)學(xué)生網(wǎng)” 上 發(fā)表了一篇題為“Google 和中國 -追隨我心的選擇”，Google 的搜索文化對技術(shù)人員 本科生畢業(yè)設(shè)計 8 的吸引可見一斑，等等數(shù)字和事件表明，搜索引擎在互聯(lián)網(wǎng)上有著強勁的生命力和 發(fā)展?jié)摿?，同時也是互聯(lián)網(wǎng)公司豐厚利潤的來源之一。 圖 1-5-1 2002-2006 年中國搜索引擎市場規(guī)模及增長 2 2005

26、年 8 月，法國總統(tǒng)希拉克大張旗鼓地發(fā)布了“Quaero”計劃，它很快被顯 現(xiàn)為一種歐洲的決心推出與 Google 搜索競爭的相同產(chǎn)品。這款名為“Quaero”的 搜索引擎，不僅能搜索文本，而且還能搜索圖片和視頻。Quaero 的拉丁文語義是 “我搜索”，該項目獲得了 2.5 億歐元資助(3.3 億美元 )，法德兩國主要技術(shù)公司參加 了開發(fā)。而在德國，一些德國企業(yè)將參加另外的德國版搜索引擎“Theseus”的開發(fā)， 該引擎更加集中于文本分析。法德兩國開發(fā)商將在合作、競爭及互補的環(huán)境下實施 歐洲新一代搜索引擎的開發(fā)計劃。 和其他許多國家一樣，在日本提起搜索引擎，人們首先想到的是谷歌，此外還 有雅

27、虎和微軟麾下的 MSN。根據(jù)今年 3 月的一項調(diào)查，在日本檢索服務(wù)利用率排 名中居首位的是雅虎，其利用率達 64.5%，其次是谷歌和 MSN，日本開發(fā)的 GOO 雖然名列第四，但實際利用率只有 5.5%，與前三名的差距很明顯。中國百度也已 經(jīng)進入日本市場，欲與群雄共逐鹿。 其實日本著手開發(fā)搜索引擎要早于美國，日本電信電話公司、日本電氣公司和 東芝公司等都曾擁有過各自獨立的搜索引擎。直到 20 世紀 90 年代后期，這些日本 國產(chǎn)搜索引擎還在相互競爭。但隨著美國谷歌的出現(xiàn)，互聯(lián)網(wǎng)信息檢索業(yè)界的格局 在 2000 年前后發(fā)生了劇變。谷歌高精確度的檢索服務(wù)使日本眾多門戶網(wǎng)站形成了 這樣的共識“ 搜索

28、引擎依靠谷歌就足夠了 ”，因此日本國產(chǎn)搜索引擎全線敗退。 搜索引擎是遨游網(wǎng)絡(luò)世界的必備工具，而其中的基干技術(shù)掌握在外國企業(yè)手中。一 些日本業(yè)界專家認為，長此以往日本互聯(lián)網(wǎng)搜索業(yè)務(wù)未來有可能被外國企業(yè)控制。 本科生畢業(yè)設(shè)計 9 抱著同樣的危機感，日本政府把國產(chǎn)下一代搜索引擎項目提上了議事日程。經(jīng)濟產(chǎn) 業(yè)省 2005 年 12 月設(shè)立了企業(yè)、研究機構(gòu)和政府部門共同參與的網(wǎng)絡(luò)搜索引擎研究 小組，負責整理與搜索技術(shù)開發(fā)相關(guān)的資料，2006 年 7 月末由大學(xué)和 52 家企業(yè)參 與的合作項目“ 信息大航海計劃 ”正式啟動，準備用 3 年時間開發(fā)出下一代互聯(lián)網(wǎng)搜 索引擎，挑戰(zhàn)谷歌等搜索引擎的市場霸主地位，

29、并打算在 2007 年度預(yù)算中申請 50 億日元(約合 4300 萬美元)作為研發(fā)費用，爭取 5 年后使下一代搜索引擎進入實用 階段。 據(jù)日本媒體報道，日本下一代搜索引擎不僅能像現(xiàn)在一樣依靠關(guān)鍵詞從互聯(lián)網(wǎng) 上的信息海洋中提取所需信息，運用現(xiàn)在逐漸普及的電子標簽，還可以及時掌握有 關(guān)全球產(chǎn)品的信息，或者以從視頻資料中剪輯的錄音為基礎(chǔ)，檢索音頻資料。日本 下一代搜索引擎的終端設(shè)備不僅有電腦，還可能是電視機、手機、汽車導(dǎo)航儀等。 今后只要操縱遙控器就能通過新搜索引擎找到電視節(jié)目中出現(xiàn)過的人物或某個地區(qū) 的資料，查詢并購買電視中出現(xiàn)過的某款商品等。 業(yè)內(nèi)人士指出，雅虎、谷歌、MSN 每年分別投資數(shù)億美

30、元用于技術(shù)研發(fā)，這 帶來問題是在目前體制下怎樣才能超越上述企業(yè)的技術(shù)水準。谷歌等搜索引擎霸主 的戰(zhàn)略也包含將檢索對象從文本擴展到視頻和音頻資料，此外日本及歐洲大型企業(yè) 的不少資深技術(shù)人員常跳槽到谷歌和雅虎，這可能有助于谷歌等開發(fā)下一代搜索引 擎終端設(shè)備。因此像法國的 “Quaero”計劃和日本的 “信息大航海計劃”等等的實施 能否取得預(yù)期效果現(xiàn)在很難準確預(yù)料。但不可否認的是：搜索引擎市場將進入一個 群雄逐鹿的瘋狂競爭時代。 隨著搜索經(jīng)濟的崛起，人們開始越加關(guān)注全球各大搜索引擎的性能、技術(shù)和日 流量。作為企業(yè)，會根據(jù)搜索引擎的知名度以及日流量來選擇是否要投放廣告等。 對于消費者而言，使用互聯(lián)網(wǎng)搜

31、索引擎是進入網(wǎng)絡(luò)世界的一個重要入口，這意味著 巨大的商機。微軟將 2007 財政年度的研發(fā)開支預(yù)算調(diào)高至 75 億美元，較預(yù)期高出 約 13 億美元，此舉顯示出微軟與 Google、雅虎在互聯(lián)網(wǎng)搜索市場上一決高下的決 心。搜索引擎也將不再是技術(shù)，而是經(jīng)濟。 本科生畢業(yè)設(shè)計 10 第一章 技術(shù)詮釋 第一節(jié) HTTP 及 HTML 超文本傳輸協(xié)議（HTTP）是應(yīng)用層協(xié)議，由于其簡捷、快速的方式，適用于 分布式和合作式超媒體信息系統(tǒng)。自 1990 年起， HTTP 就已經(jīng)被應(yīng)用于 WWW 全球信息服務(wù)系統(tǒng)?？蛻暨M程建立一條同服務(wù)器進程的 TCP 連接，然后發(fā)出請求 并讀取服務(wù)器進程的應(yīng)答。服務(wù)器進程

32、關(guān)閉連接表示本次響應(yīng)結(jié)束。服務(wù)器進程返 回的內(nèi)容包含兩個部分，一個“應(yīng)答頭” （response header） ，一個“ 應(yīng)答體” （response body） ，后者通常是一個 HTML 文件，我們稱之為“網(wǎng)頁”。 通常 HTTP 消息包括客戶機向服務(wù)器的請求消息和服務(wù)器向客戶機的響應(yīng)消息。 這兩種類型的消息由一個起始行，一個或者多個頭域，一個只是頭域結(jié)束的空行和 可選的消息體組成。HTTP 的頭域包括通用頭，請求頭，響應(yīng)頭和實體頭四個部分。 每個頭域由一個域名，冒號（:）和域值三部分組成。域名是大小寫無關(guān)的，域值 前可以添加任何數(shù)量的空格符，頭域可以被擴展為多行，在每行開始處，使用至少

33、 一個空格或制表符。 HTTP 協(xié)議采用了請求/響應(yīng)模型?？蛻舳讼蚍?wù)器發(fā)送一個請求，請求頭包 含請求的方法、URI、協(xié)議版本、以及包含請求修飾符、客戶信息和內(nèi)容的類似于 MIME 的消息結(jié)構(gòu)。服務(wù)器以一個狀態(tài)行作為響應(yīng)，相應(yīng)的內(nèi)容包括消息協(xié)議的版 本，成功或者錯誤編碼加上包含服務(wù)器信息、實體元信息以及可能的實體內(nèi)容。 Web 服務(wù)器的 HTTP 應(yīng)答一般由以下幾項構(gòu)成：一個狀態(tài)行，一個或多個應(yīng) 答頭，一個空行，內(nèi)容文檔。設(shè)置 HTTP 應(yīng)答頭往往和設(shè)置狀態(tài)行中的狀態(tài)代碼結(jié) 合起來。 典型的請求消息： GET http:/class/download.microtool.de:80/somed

34、ata.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- 典型的響應(yīng)消息： HTTP/1.0200OK 本科生畢業(yè)設(shè)計 11 Date:Mon,31Dec200104:25:57GMT Server:Apache/1.3.14(Unix) Content-type:text/html

35、 Last-modified:Tue,17Apr200106:46:28GMT Etag:a030f020ac7c01:1e9f Content-length:39725426 Content-range:bytes554554-40279979/40279980 一個完整的 HTML 文檔以 開始，以結(jié)束。大部分的 HTML 命令都像這樣成對出現(xiàn)。HTML 文檔含有以開始、以結(jié)束的首 部和以 開始、以結(jié)束的主體部分。標題通常由客戶程序顯示在 窗口的頂部。 第二節(jié) 網(wǎng)絡(luò)蜘蛛 網(wǎng)絡(luò)蜘蛛即 Web Spider，是一個很形象的名字。把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng)， 那么 Spider 就是在網(wǎng)上爬來爬去

36、的蜘蛛。網(wǎng)絡(luò)蜘蛛是通過網(wǎng)頁的鏈接地址來尋找 網(wǎng)頁，從網(wǎng)站某一個頁面（通常是首頁）開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的 其它鏈接地址，然后通過這些鏈接地址尋找下一個網(wǎng)頁，這樣一直循環(huán)下去，直到 把這個網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當成一個網(wǎng)站，那么網(wǎng)絡(luò) 蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。 首先蜘蛛讀取抓取站點的 URL 列表，取出一個站點 URL，將其放入未訪問的 URL 列表（UVURL 列表）中，如果 UVURL 不為空剛從中取出一個 URL 判斷是 否已經(jīng)訪問過，若沒有訪問過則讀取此網(wǎng)頁，并進行超鏈分析及內(nèi)容分析，并將些 頁存入文檔數(shù)據(jù)庫，并將些 URL 放

37、入已訪問 URL 列表（VURL 列表） ，直到 UVRL 為空為止，此時再抓取其他站點，依次循環(huán)直到所有的站點 URL 列表都抓 取完為止。 對于搜索引擎來說，要抓取互聯(lián)網(wǎng)上所有的網(wǎng)頁幾乎是不可能的，從目前公布 的數(shù)據(jù)來看，容量最大的搜索引擎也不過是抓取了整個網(wǎng)頁數(shù)量的百分之四十左右。 這其中的原因一方面是抓取技術(shù)的瓶頸，無法遍歷所有的網(wǎng)頁，有許多網(wǎng)頁無法從 其它網(wǎng)頁的鏈接中找到；另一個原因是存儲技術(shù)和處理技術(shù)的問題，如果按照每個 頁面的平均大小為 20K 計算（包含圖片） ，100 億網(wǎng)頁的容量是 1002000G 字節(jié)， 即使能夠存儲，下載也存在問題（按照一臺機器每秒下載 20K 計算，

38、需要 340 臺 機器不停的下載一年時間，才能把所有網(wǎng)頁下載完畢） 。同時，由于數(shù)據(jù)量太大， 在提供搜索時也會有效率方面的影響。因此，許多搜索引擎的網(wǎng)絡(luò)蜘蛛只是抓取那 本科生畢業(yè)設(shè)計 12 些重要的網(wǎng)頁，而在抓取的時候評價重要性主要的依據(jù)是某個網(wǎng)頁的鏈接深度。 在抓取網(wǎng)頁的時候，網(wǎng)絡(luò)蜘蛛一般有兩種策略：廣度優(yōu)先和深度優(yōu)先（如下圖 所示） 。廣度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會先抓取起始網(wǎng)頁中鏈接的所有網(wǎng)頁，然后再選擇 其中的一個鏈接網(wǎng)頁，繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng)頁。這是最常用的方式， 因為這個方法可以讓網(wǎng)絡(luò)蜘蛛并行處理，提高其抓取速度。深度優(yōu)先是指網(wǎng)絡(luò)蜘蛛 會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處

39、理完這條線路之后再轉(zhuǎn)入下一個 起始頁，繼續(xù)跟蹤鏈接。這個方法有個優(yōu)點是網(wǎng)絡(luò)蜘蛛在設(shè)計的時候比較容易。 網(wǎng)絡(luò)蜘蛛在訪問網(wǎng)站網(wǎng)頁的時候，經(jīng)常會遇到加密數(shù)據(jù)和網(wǎng)頁權(quán)限的問題，有 些網(wǎng)頁是需要會員權(quán)限才能訪問。當然，網(wǎng)站的所有者可以通過協(xié)議讓網(wǎng)絡(luò)蜘蛛不 去抓取，但對于一些出售報告的網(wǎng)站，他們希望搜索引擎能搜索到他們的報告，但 又不能完全免費的讓搜索者查看，這樣就需要給網(wǎng)絡(luò)蜘蛛提供相應(yīng)的用戶名和密碼。 網(wǎng)絡(luò)蜘蛛可以通過所給的權(quán)限對這些網(wǎng)頁進行網(wǎng)頁抓取，從而提供搜索。而當搜索 者點擊查看該網(wǎng)頁的時候，同樣需要搜索者提供相應(yīng)的權(quán)限驗證。 網(wǎng)絡(luò)蜘蛛需要抓取網(wǎng)頁，不同于一般的訪問，如果控制不好，則會引起網(wǎng)站服

40、務(wù)器負擔過重。有多種方法可以讓網(wǎng)站和網(wǎng)絡(luò)蜘蛛進行交流。一方面讓網(wǎng)站管理員 了解網(wǎng)絡(luò)蜘蛛都來自哪兒，做了些什么，另一方面也告訴網(wǎng)絡(luò)蜘蛛哪些網(wǎng)頁不應(yīng)該 抓取，哪些網(wǎng)頁應(yīng)該更新。 每個網(wǎng)絡(luò)蜘蛛都有自己的名字，在抓取網(wǎng)頁的時候，都會向網(wǎng)站標明自己的身 份。網(wǎng)絡(luò)蜘蛛在抓取網(wǎng)頁的時候會發(fā)送一個請求，這個請求中就有一個字段為 Useragent，用于標識此網(wǎng)絡(luò)蜘蛛的身份。例如 Google 網(wǎng)絡(luò)蜘蛛的標識為 GoogleBot，Baidu 網(wǎng)絡(luò)蜘蛛的標識為 BaiDuSpider，Yahoo 網(wǎng)絡(luò)蜘蛛的標識為 Inktomi Slurp。如果在網(wǎng)站上有訪問日志記錄，網(wǎng)站管理員就能知道，哪些搜索引 擎的網(wǎng)絡(luò)蜘

41、蛛過來過，什么時候過來的，以及讀了多少數(shù)據(jù)等等。如果網(wǎng)站管理員 發(fā)現(xiàn)某個蜘蛛有問題，就通過其標識來和其所有者聯(lián)系。 網(wǎng)絡(luò)蜘蛛進入一個網(wǎng)站，一般會訪問一個特殊的文本文件 Robots.txt，這個文 件一般放在網(wǎng)站服務(wù)器的根目錄下，如： http:/ 。網(wǎng) 站管理員可以通過 robots.txt 來定義哪些目錄網(wǎng)絡(luò)蜘蛛不能訪問，或者哪些目錄對 于某些特定的網(wǎng)絡(luò)蜘蛛不能訪問。例如有些網(wǎng)站的可執(zhí)行文件目錄和臨時文件目錄 不希望被搜索引擎搜索到，那么網(wǎng)站管理員就可以把這些目錄定義為拒絕訪問目錄。 Robots.txt 語法很簡單，例如如果對目錄沒有任何限制，可以用以下兩行來描述： User-agent

42、: * Disallow: 當然，Robots.txt 只是一個協(xié)議，如果網(wǎng)絡(luò)蜘蛛的設(shè)計者不遵循這個協(xié)議，網(wǎng) 站管理員也無法阻止網(wǎng)絡(luò)蜘蛛對于某些頁面的訪問，但一般的網(wǎng)絡(luò)蜘蛛都會遵循這 本科生畢業(yè)設(shè)計 13 些協(xié)議，而且網(wǎng)站管理員還可以通過其它方式來拒絕網(wǎng)絡(luò)蜘蛛對某些網(wǎng)頁的抓取。 第三節(jié) 網(wǎng)頁噪聲 當 Web 中獲取所需信息的同時，會常?？匆姶罅亢退P(guān)心內(nèi)容無關(guān)的導(dǎo)航條、 廣告信息、版權(quán)信息以及調(diào)查問卷等，稱之為“噪聲 ”內(nèi)容。在某些情況下，可能從 這些噪音內(nèi)容中得到一些意外的驚喜；但多數(shù)時候，因這些噪聲消耗掉了很多的注 意力。同時，噪聲內(nèi)容通常伴隨著相關(guān)的超鏈。因此，噪聲會導(dǎo)致相互鏈接的網(wǎng)頁

43、常常并無內(nèi)容相關(guān)性。這樣，網(wǎng)頁內(nèi)容的混亂不僅給基于網(wǎng)頁內(nèi)容的研究工作帶來 困難，也給基于網(wǎng)頁超鏈指向的研究工作帶來困難。另外，隨著 Web 各種研究與 應(yīng)用的深入發(fā)展，僅僅是原始網(wǎng)頁內(nèi)容已經(jīng)不能滿足需求，還要求能夠提供便于計 算機處理的元數(shù)據(jù)信息，例如關(guān)鍵詞、摘要、網(wǎng)頁內(nèi)容類別等。然而，現(xiàn)在大部分 網(wǎng)頁仍然是普通 HTML 網(wǎng)頁，并不包含必要的元數(shù)據(jù)。因此，本節(jié)討論一個網(wǎng)頁 表示模型建立和實現(xiàn)的方法，這一方面使我們能夠自動從網(wǎng)頁中提取相關(guān)的元數(shù)據(jù)， 另一方面也去除了和網(wǎng)頁主題內(nèi)容無關(guān)的噪音內(nèi)容，進而在原始 Web 上搭建一個 噪聲小、描述清晰、更易于處理和利用的網(wǎng)頁信息平臺。 在網(wǎng)頁分類領(lǐng)域，

44、由于噪聲內(nèi)容與主題無關(guān)，訓(xùn)練集中的噪聲內(nèi)容會導(dǎo)致各個 類別的特征不夠明顯，而待分類網(wǎng)頁中的噪聲內(nèi)容則會導(dǎo)致該網(wǎng)頁類別不明確，因 而影響了網(wǎng)頁自動分類的效果。因此提出了通過去掉網(wǎng)頁中的噪聲內(nèi)容來提高網(wǎng)頁 分類質(zhì)量的方法。 在網(wǎng)頁信息提取領(lǐng)域，自動識別模式的方法必須要從整個網(wǎng)頁中提取模式，而 不是只針對主題內(nèi)容提取。因此，在凈化后的網(wǎng)頁上作信息提取不僅可以排除噪聲 信息對信息提取的干擾，提高信息提取的準確性，而且可以使得網(wǎng)頁中的結(jié)構(gòu)簡單 化，提高信息提取的效率。 上述分析我們看到，網(wǎng)頁噪聲對基于網(wǎng)頁的研究工作的影響是普遍而嚴重的， 雖然各個領(lǐng)域采用的方法各不相同，但處理的目的都是為了去除網(wǎng)頁中的噪

45、聲內(nèi)容， 得到真正的主題內(nèi)容。 第四節(jié) 頁面分析 由于WWW網(wǎng)上的信息主要是以HTML文檔的形式存放的，因此要根據(jù)HTML文檔 的特點，對其進行掃描分析，以提取信息。 HTML文檔有五個定義好的組件: 本科生畢業(yè)設(shè)計 14 、文本 、注釋 、簡單標簽 、起始標簽 、結(jié)束標簽 文本就是在HTML頁面上看到的詞句的內(nèi)容。除了腳本代碼，HTML文檔中的所有 數(shù)據(jù)，只要不是標簽的組成部分，都被認為是文本。文本是格式化的，并且受包圍 它的標簽的控制。就像前面所提到的那樣，如果數(shù)據(jù)位于文本之外，將不會被看作 文本。但是程序在理解HTML頁面時，腳本代碼具有與文本相似的特性。腳本代碼包 含在標簽和之間。確保

46、搜索引擎程序不會將腳本代碼與文本數(shù) 據(jù)混淆是很重要的。 文本實際上就是顯示在瀏覽器中的文字，其顯示方式由包圍它的標簽來網(wǎng)以決 定。根據(jù)本課題的要求，文本無疑是我們所需要的重要的信息源之一。頁相關(guān)的主 題是通過文本來表達的，所以文本信息必須被完全提取出來，便進一步處理。 注釋表示HTML文檔中不會顯示給用戶的那部分內(nèi)容。他們通常是HTML程序員所 做的說明，這些說明通常是表達編程思路的，所以這類數(shù)據(jù)對本課題來說是毫無用 處。因此在解析HTML文檔時，將注釋忽略。簡單標簽是由單個表示的HTML標簽。最 普遍的簡單標簽是行中斷符()標簽和圖像標簽( )，它們都沒有相應(yīng)的結(jié) 束標簽。簡單標簽主要是用來

47、控制顯示格式或使用圖像美化界面用的。 大多數(shù)HTML標簽都是由開始標簽和結(jié)束標簽組成的。開始標簽非常像簡單標簽。 開始標簽與簡單標簽直接的唯一區(qū)別是:開始標簽有一個相應(yīng)的結(jié)束標簽，該結(jié)束 標簽出現(xiàn)在后面。開始標簽和結(jié)束標簽用來控制其所包含的HTML代碼的功能。 在所有的開始和結(jié)束標簽中，標簽是最有用的。標簽在HTML中 叫做鏈接標簽，它決定了當在瀏覽器中點擊該標簽的文本時所要打開的網(wǎng)頁的 URL。下面是一個例子: Click Here 從上面的例子中我們可以看出，標識它所鏈接的URL是該標簽的href屬性決定， href的值就代表了一個URL. Href屬性值有兩種表達方式:一種是絕對路徑，也

48、就是 說它的值是一個完整的URL，程序可以直接使用它;另一種相對路徑，它的表示方式 只有目錄或文件名，表示相對于木網(wǎng)頁的所在目錄的位置。使用相對路徑的目的是 提高網(wǎng)頁的可移植性。標簽中的鏈接并不是唯一將用戶帶到其它頁面的基 礎(chǔ)結(jié)構(gòu)標簽。Web站點還能建立圖像映像，當用戶點擊它們時，也能將用戶帶到相 應(yīng)的新頁面。圖像映像由客戶端和服務(wù)器圖像映像組成，但是服務(wù)器圖像映像幾乎 本科生畢業(yè)設(shè)計 15 完全被客戶端所取代。這是因為服務(wù)器端的圖像映像，需要一個服務(wù)器插件來注冊 用戶點擊的圖像區(qū)域。而這在客戶端圖像映像中是完全包含在HTML文件中 3。 客戶端圖像映像不需要服務(wù)器端的腳本表示來解釋可多處點擊

49、的圖像的 hot”區(qū)。實際上，客戶端圖像映像比服務(wù)器端圖像映像更為有效，而且還允許訪 問者在Web瀏覽器的狀態(tài)區(qū)中看到映像區(qū)域真正關(guān)聯(lián)的URL。該狀態(tài)文本還會在用戶 鼠標在圖像映像區(qū)域移動的時候出現(xiàn)。客戶端映像圖像將包含一個如下所示的映像。 該映像將每個圖像區(qū)域鏈接到一個URL: 在該HTML文件的后面，該映像以類似于下面的方式使用: 通過以上分析圖像映像當中的超級鏈接可以由圖像的簡單標簽中的href 屬性得到。除了以上兩種情況外，框架中的src屬性也可以設(shè)置超級鏈接。框架標 簽屬于開始標簽和結(jié)束標簽，下面是一個例子。 在上面的例子中可以看出，該標簽中有一個名為src的屬性，代表了該框架中 應(yīng)

50、顯示的網(wǎng)頁鏈接，在網(wǎng)頁中搜索鏈接時，不應(yīng)遺漏此類鏈接。需要說明的是，窗 體、腳本語言代碼和網(wǎng)頁中嵌入式對象也可以提供鏈接功能。但是，它們主要是提 供一些特殊領(lǐng)域的特殊功能的應(yīng)用。窗體主要是用來收集用戶信息，用戶信息是瀏 覽網(wǎng)頁的人根據(jù)自己的實際情況填寫，例如，用戶名和密碼等。在這些用戶信息不 全的情況下，返回的網(wǎng)頁通常顯示的是錯誤的信息的頁面。這對本文所研究的垂直 搜索引擎來說是毫無意義的，因此，我們對表單不作處理。至于腳本語言代碼，通 常是網(wǎng)頁編寫者按照自己的意愿和邏輯，用腳本語言寫的一段代碼，它也可以返回 一個網(wǎng)頁。然而不幸的是，除非搜索引擎能正確理解腳本代碼，才一能得到正確的 返回頁面的

51、URL。否則，應(yīng)該回避。對于網(wǎng)頁中的嵌入式對象，比如ActiveX控件， Java Applet等，他們都是已編譯好的程序。要對它們中的鏈接進行識別的話，必 須全面深入其二進制代碼內(nèi)部結(jié)構(gòu)，難度極大。 本科生畢業(yè)設(shè)計 16 第五節(jié) 中文分詞 眾所周知，英文是以詞為單位的，詞和詞之間是靠空格隔開，而中文是以字為 單位，句子中所有的字連起來才能描述一個意思。例如，英文句子 I am a student， 用中文則為：“ 我是一個學(xué)生 ”。計算機可以很簡單通過空格知道 student 是一個單 詞，但是不能很容易明白“學(xué)” 、 “生”兩個字合起來才表示一個詞。把中文的漢字序 列切分成有意義的詞，就是

52、中文分詞，有些人也稱為切詞。我是一個學(xué)生，分詞的 結(jié)果是：我/是/一個/學(xué)生。 中文分詞是其他中文信息處理的基礎(chǔ)，搜索引擎只是中文分詞的一個應(yīng)用。其 他的比如機器翻譯（MT） 、語音合成、自動分類、自動摘要、自動校對等等，都需 要用到分詞。 一、分詞方法概述 現(xiàn)有的分詞算法可分為三大類：基于字符串匹配的分詞方法、基于理解的分詞 方法和基于統(tǒng)計的分詞方法。 （一）基于字符串匹配的分詞方法 這種方法又叫做機械分詞方法，它是按照一定的策略將待分析的漢字串與一個 “充分大的”機器詞典中的詞條進行配，若在詞典中找到某個字符串，則匹配成功 （識別出一個詞） 。按照掃描方向的不同，串匹配分詞方法可以分為正向

53、匹配和逆 向匹配；按照不同長度優(yōu)先匹配的情況，可以分為最大（最長）匹配和最?。ㄗ疃蹋?匹配；按照是否與詞性標注過程相結(jié)合，又可以分為單純分詞方法和分詞與標注相 結(jié)合的一體化方法。常用的幾種機械分詞方法如下： 正向最大匹配法（由左到右的方向） ； 逆向最大匹配法（由右到左的方向） ； 最少切分（使每一句中切出的詞數(shù)最小） 。 還可以將上述各種方法相互組合，例如，可以將正向最大匹配方法和逆向最大 匹配方法結(jié)合起來構(gòu)成雙向匹配法。由于漢語單字成詞的特點，正向最小匹配和逆 向最小匹配一般很少使用。一般說來，逆向匹配的切分精度略高于正向匹配，遇到 的歧義現(xiàn)象也較少。統(tǒng)計結(jié)果表明，單純使用正向最大匹配的錯

54、誤率為 1/169，單 純使用逆向最大匹配的錯誤率為 1/2454。但這種精度還遠遠不能滿足實際的需要。 實際使用的分詞系統(tǒng)，都是把機械分詞作為一種初分手段，還需通過利用各種其它 的語言信息來進一步提高切分的準確率。 一種方法是改進掃描方式，稱為特征掃描或標志切分，優(yōu)先在待分析字符串中 本科生畢業(yè)設(shè)計 17 識別和切分出一些帶有明顯特征的詞，以這些詞作為斷點，可將原字符串分為較小 的串再來進機械分詞，從而減少匹配的錯誤率。另一種方法是將分詞和詞類標注結(jié) 合起來，利用豐富的詞類信息對分詞決策提供幫助，并且在標注過程中又反過來對 分詞結(jié)果進行檢驗、調(diào)整，從而極大地提高切分的準確率。 對于機械分詞方

55、法，可以建立一個一般的模型，在這方面有專業(yè)的學(xué)術(shù)論文， 這里不做詳細論述。 （二）基于理解的分詞方法 這種分詞方法是通過讓計算機模擬人對句子的理解，達到識別詞的效果。其基 本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧 義現(xiàn)象。它通常包括三個部分：分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。在總控 部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧 義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言 知識和信息。由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機器 可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗階段

56、。 （三）基于統(tǒng)計的分詞方法 從形式上看，詞是穩(wěn)定的字的組合，因此在上下文中，相鄰的字同時出現(xiàn)的次 數(shù)越多，就越有可能構(gòu)成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的反 映成詞的可信度?？梢詫φZ料中相鄰共現(xiàn)的各個字的組合的頻度進行統(tǒng)計，計算它 們的互現(xiàn)信息。定義兩個字的互現(xiàn)信息，計算兩個漢字 X、Y 的相鄰共現(xiàn)概率?；?現(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當緊密程度高于某一個閾值時，便可 認為此字組可能構(gòu)成了一個詞。這種方法只需對語料中的字組頻度進行統(tǒng)計，不需 要切分詞典，因而又叫做無詞典分詞法或統(tǒng)計取詞方法。但這種方法也有一定的局 限性，會經(jīng)常抽出一些共現(xiàn)頻度高、但并不是詞的常用字組

57、，例如“這一” 、 “之一”、 “有的”、 “我的 ”、 “許多的” 等，并且對常用詞的識別精度差，時空開銷大。實際應(yīng)用 的統(tǒng)計分詞系統(tǒng)都要使用一部基本的分詞詞典（常用詞詞典）進行串匹配分詞，同 時使用統(tǒng)計方法識別一些新的詞，即將串頻統(tǒng)計和串匹配結(jié)合起來，既發(fā)揮匹配分 詞切分速度快、效率高的特點，又利用了無詞典分詞結(jié)合上下文識別生詞、自動消 除歧義的優(yōu)點。 到底哪種分詞算法的準確度更高，目前并無定論。對于任何一個成熟的分詞系 統(tǒng)來說，不可能單獨依靠某一種算法來實現(xiàn)，都需要綜合不同的算法。筆者了解， 海量科技的分詞算法就采用“復(fù)方分詞法” ，所謂復(fù)方，相當于用中藥中的復(fù)方概念， 即用不同的藥才綜

58、合起來去醫(yī)治疾病，同樣，對于中文詞的識別，需要多種算法來 處理不同的問題。 本科生畢業(yè)設(shè)計 18 二、分詞中的難題 有了成熟的分詞算法，是否就能容易的解決中文分詞的問題呢？事實遠非如此。 中文是一種十分復(fù)雜的語言，讓計算機理解中文語言更是困難。在中文分詞過程中， 有兩大難題一直沒有完全突破。 （一）歧義識別 歧義是指同樣的一句話，可能有兩種或者更多的切分方法。例如：表面的，因 為“表面”和“面的 ”都是詞，那么這個短語就可以分成 “表面 的” 和“表 面的”。這種 稱為交叉歧義。像這種交叉歧義十分常見，前面舉的“和服” 的例子，其實就是因為 交叉歧義引起的錯誤。 “化妝和服裝 ”可以分成“化妝

59、/ 和/ 服裝”或者“ 化妝/ 和服/裝”。 由于沒有人的知識去理解，計算機很難知道到底哪個方案正確。 交叉歧義相對組合歧義來說是還算比較容易處理，組合歧義就必需根據(jù)整個句 子來判斷了。例如，在句子“這個門把手壞了” 中， “把手”是個詞，但在句子“ 請把手 拿開”中， “把手” 就不是一個詞；在句子“將軍任命了一名中將 ”中， “中將” 是個詞， 但在句子“產(chǎn)量三年中將增長兩倍” 中， “中將”就不再是詞。這些詞計算機又如何去 識別？ 如果交叉歧義和組合歧義計算機都能解決的話，在歧義中還有一個難題，是真 歧義。真歧義意思是給出一句話，由人去判斷也不知道哪個應(yīng)該是詞，哪個應(yīng)該不 是詞。例如：“

60、 乒乓球拍賣完了 ”，可以切分成“乒乓/ 球拍/ 賣/完/ 了” 、也可切分成 “乒乓球/拍賣 /完/了” ，如果沒有上下文其他的句子，恐怕誰也不知道“ 拍賣”在這里 算不算一個詞。 （二）新詞識別 新詞，專業(yè)術(shù)語稱為未登錄詞。也就是那些在字典中都沒有收錄過，但又確實 能稱為詞的那些詞。最典型的是人名，人可以很容易理解句子“王軍虎去廣州了” 中， “王軍虎”是個詞，因為是一個人的名字，但要是讓計算機去識別就困難了。如果把 “王軍虎”做為一個詞收錄到字典中去，全世界有那么多名字，而且每時每刻都有新 增的人名，收錄這些人名本身就是一項巨大的工程。即使這項工作可以完成，還是 會存在問題，例如：在句子

61、“王軍虎頭虎腦的” 中， “王軍虎”還能不能算詞？ 新詞中除了人名以外，還有機構(gòu)名、地名、產(chǎn)品名、商標名、簡稱、省略語等 都是很難處理的問題，而且這些又正好是人們經(jīng)常使用的詞，因此對于搜索引擎來 說，分詞系統(tǒng)中的新詞識別十分重要。目前新詞識別準確率已經(jīng)成為評價一個分詞 系統(tǒng)好壞的重要標志之一。 本科生畢業(yè)設(shè)計 19 第六節(jié) 布爾代數(shù) 布爾（George Boole) 是十九世紀英國一位小學(xué)數(shù)學(xué)老師。他生前沒有人認為 他是數(shù)學(xué)家。布爾在工作之余，喜歡閱讀數(shù)學(xué)論著、思考數(shù)學(xué)問題。1854 年思 維規(guī)律（An Investigation of the Laws of Thought, on whic

62、h are founded the Mathematical Theories of Logic and Probabilities） 一書，第一次向人們展示了如何 用數(shù)學(xué)的方法解決邏輯問題 5。 布爾代數(shù)運算的元素只有兩個 1 （TRUE ， 真) 和 0（FALSE，假)。基本的 運算只有“與 ”（AND) 、 “或” (OR) 和“非”（NOT) 三種（后來發(fā)現(xiàn)，這三種運算都 可以轉(zhuǎn)換成“ 與”“非” ANDNOT 兩種運算） 。 事實上在布爾代數(shù)提出后 80 多年里，它確實沒有什么像樣的應(yīng)用，直到 1938 年香農(nóng)在他的碩士論文中指出用布爾代數(shù)來實現(xiàn)開關(guān)電路，才使得布爾代數(shù) 成為數(shù)字電

63、路的基礎(chǔ)。所有的數(shù)學(xué)和邏輯運算，加、減、乘、除、乘方、開方等等， 全部能轉(zhuǎn)換成二值的布爾運算。 二進制和布爾運算是世界上最簡單的計數(shù)方法和運算。無論哪一個搜索引擎宣 稱自己如何聰明、多么智能化，其實只要是追求效率，從根本上講都不可能離開布 爾運算。ToKing 搜索引擎的倒排索引文件的實際方法將主要采用布爾代數(shù)。 第七節(jié) CGI CGI 代表 Common Gateway Interface(通用網(wǎng)關(guān)界面） ，它使在網(wǎng)絡(luò)服務(wù)器下運 行外部分應(yīng)用程序（或網(wǎng)關(guān)）成為可能。CGI-BIN 目錄是存放 CGI 腳本的地方。 這些腳本使 WWW 服務(wù)器和瀏覽器能運行外部程序，而無需啟動另一個原因程序。

64、它是運行在 Web 服務(wù)器上的一個程序，并由來自于瀏覽者的輸人觸發(fā)。CGI 是在 HTTP 服務(wù)器下運行外部程序（或網(wǎng)關(guān)）的一個接口，它能讓網(wǎng)絡(luò)用戶訪問遠程系 統(tǒng)上的使用類型程序，就好像他們在實際使用那些遠程計算機一樣。 CGI 能夠讓瀏覽者與服務(wù)器進行交互，如果你曾經(jīng)遇到過在網(wǎng)絡(luò)上填表或者進 行搜索，就很有可能就是用的 CGI。 盡管 CGI 易于使用，但是當大批人同時使用一個 CGI 應(yīng)用程序是會反應(yīng)較慢， 網(wǎng)絡(luò)服務(wù)器 速度也會受到很大 影響。CGI 應(yīng)用程序的優(yōu)點是可以獨立運行。 CGI 應(yīng)用程序可以由大多數(shù)的編程語言編寫，如 Perl（Practical Extraction and

65、Report Language)、CC+、Java 和 Visual Basic 等。不過對于那些沒有太多編程經(jīng) 驗的網(wǎng)頁制作人來說，實在是一個不小的難題。 本科生畢業(yè)設(shè)計 20 CGI 應(yīng)用程序的工作原理是這樣的： .瀏覽器通過 HTML 表單或超鏈接請求指上一個 CGI 應(yīng)用程序的 URL。 .服務(wù)器收發(fā)到請求。 .服務(wù)器執(zhí)行指定所 CGI 應(yīng)用程序。 .CGI 應(yīng)用程序執(zhí)行所需要的操作，通常是基于瀏覽者輸人的內(nèi)容。 .CGI 應(yīng)用程序把結(jié)果格式化為網(wǎng)絡(luò)服務(wù)器和瀏覽器能夠理解的文檔（通常 是 HTML 網(wǎng)頁） 。 .網(wǎng)絡(luò)服務(wù)器把結(jié)果返回到瀏覽器中。 自 CGI 產(chǎn)生以來，C 語言以其高效性

66、、靈活性和通用性一直是開發(fā)交互式 WEB 應(yīng)用的最有吸引力的選擇。但近年來，能直接內(nèi)嵌于 HTML 文檔中間的各種 腳本工具，以其簡便性易用性使一部分用戶開始放棄了直接用 C 來開發(fā) CGI 腳本。 但還有兩類用戶沒有放棄用 C 來開發(fā)它們的應(yīng)用，一是對性能追求較高的高端開 發(fā)者，二是嵌入式設(shè)備的開者。前者選擇 C 語言來開發(fā)它們的 WEB 應(yīng)用，是因為 C 高效性、靈活性和通用性是各種腳本工具無法取代的。后者選擇 C 語言，是因 嵌入式設(shè)備的特點（內(nèi)存、CPU 等資源有限等，不可在設(shè)備上運行如 ASP，PHP，PERL 等的腳本的運行環(huán)境）決定的（另外，目前嵌入式設(shè)備主要以 C 語言開發(fā)為主） 。 第八節(jié) SOCKECT 網(wǎng)絡(luò)編程 所謂 socket 通常也稱作套接字，用于描述 IP 地址和端口，是一個通信鏈的 句柄。應(yīng)用程序通常通過 套接字 向網(wǎng)絡(luò)發(fā)出請求或者應(yīng)答網(wǎng)絡(luò)請求。 網(wǎng)頁抓取 部分就是采用的這種技術(shù)。 本科生畢業(yè)設(shè)計 21 第二章 TOKING 海量網(wǎng)頁搜索系統(tǒng)體系結(jié)構(gòu)及實現(xiàn) 第一節(jié) 結(jié)構(gòu)設(shè)計 搜索引擎的最基本的功能就是在一個可以接受的時間內(nèi)返回一個和用戶查詢匹 配的網(wǎng)頁