【畢業(yè)學位論文】(Word原稿)搜索引擎的基本原理及中文分詞的設計與實現(xiàn)-計算機網(wǎng)絡技術

i 摘要 :隨著因特網(wǎng)的迅猛發(fā)展、 息的增加，而人們越來越依靠網(wǎng)絡來查找他們所需要的信息，用戶要在如此浩瀚的信息海洋里查找信息，就象大海撈針一樣，所以如何有效的去發(fā)現(xiàn)我們所需要的信息，就成了一個很關鍵的問題。為了解決這個問題，搜索引擎隨之誕生。因而也成為除了電子郵件以外最多人使用的網(wǎng)上服務。 但是，隨著信息多元化的增長，千篇一律的給所有用戶提供同一個入口顯然已經(jīng)不能滿足特定用戶更深入的查詢需求。我們需要分類細致精確、對硬件要求低，數(shù)據(jù)全面深入、更新及時的搜索引擎，因而搜索引擎技術成為計算機工業(yè)界和學術界爭相 研究、開發(fā)的課題。 本文闡述了搜索引擎的基本原理，著重分析了中文分詞的設計與實現(xiàn)。 關鍵詞 ： 互聯(lián)網(wǎng)；搜索引擎；中文分詞 of of EB on to Its to so so to we a To It to in of we is a is in So of to In I of of 目錄 前言 . 1 第 一章 搜索引擎概述 . 2 展現(xiàn)狀 . 2 發(fā)展歷程 . 2 . 3 信息分布 . 3 索引擎簡介 . 4 索引擎的發(fā)展 . 5 一代搜索引擎 . 5 二代搜索引擎 . 6 三代搜索引擎 . 6 四代搜索引擎 . 7 索引擎的分類 . 7 文搜索引擎 . 7 錄索引 . 8 搜索引擎 . 9 他非主流的引擎 . 9 第 二章 搜索引擎的結(jié)構介紹 . 11 索器 . 11 引器 . 12 索器 . 12 戶接口 . 12 結(jié) . 13 第 三章 基于 研究 . 14 3.1 索引擎介紹 . 14 特性分析 . 15 心部分 索引排序 . 15 2 相關度積分公式 . 17 其他特性 . 18 性 . 18 . 19 字 . 19 排序 . 19 化 . 20 為查詢 優(yōu)化索引 (. 20 并發(fā)操作 制 . 20 . 20 檔結(jié)構 . 21 念詳細介紹 . 21 本數(shù)據(jù)類型（ . 23 索引包含的文件（ . 24 詞原理 . 30 第 四章 中文分詞 . 34 中文分詞簡介 . 34 什么是中文分詞 . 34 中文分詞和搜索引擎 . 34 中文分詞技術 . 35 基于字符串匹配的分詞方法 . 35 于理解的分詞方法 . 36 基于統(tǒng)計的分詞方法 . 37 分詞中的難題 . 37 歧義識別 . 37 新詞識別 . 38 寫簡單的中文分詞程序 . 39 計思路 . 39 第 五章 搜索引擎的未來與展望 . 44 參考文獻 . 46 感謝 . 47 第 1 頁 共 47 頁 前言 隨著信息技術的不斷發(fā)展，特別是互聯(lián)網(wǎng)應用技術的不斷普及，互聯(lián)網(wǎng)提供的內(nèi)容不斷豐富，中國搜索引擎市場也出現(xiàn)了蓬勃發(fā)展的生機，搜索引擎成為人們獲取信息的重要途徑。 搜索引擎經(jīng)過幾年的發(fā)展和摸索，越來越貼近人們的需求，搜索引擎的技術也得到了很大的發(fā)展。搜索引擎的最新技術發(fā) 展包括以下幾個方面： 一、提高搜索引擎對用戶檢索提問的理解 二、對檢索結(jié)果進行處理 三、確定搜索引擎信息搜集范圍，提高搜索引擎的針對性 四、將搜索引擎的技術開發(fā)重點放在對檢索結(jié)果的處理上，提供更優(yōu)化的檢索 結(jié)果 一個開放源程序的搜尋器引擎，利用它可以輕易地為 件加入全文搜尋功能。 最主要工作是替文件的每一個字作索引，索引讓搜尋的效率比傳統(tǒng)的逐字比較大大提高， 供一組解讀，過濾，分析文件，編排和使用索引的 的強大之處除了高效和簡單外，是最重要的是使 使用者可以隨時應自已需要自訂其功能，本設計就是在 礎上開發(fā)。 第 2 頁 共 47 頁 第一章 搜索引擎概述 隨著因特網(wǎng)的迅猛發(fā)展、 息的增加，用戶要在信息海洋里查找信息，就象大海撈針一樣，搜索引擎技術恰好解決了這一難題（它可以為用戶提供信息檢索服務）。目前，搜索引擎技術正成為計算機工業(yè)界和學術界爭相研究、開發(fā)的對象。 搜索引擎（ 隨著 息的迅速增加，從 1995 年開始逐漸發(fā)展起來的技術。據(jù)發(fā)表在科學雜志 1999 年 7 月的文章 息的可訪問性估計，全球目前的網(wǎng)頁超過 8 億，有效數(shù)據(jù)超過 9T，并且仍以每 4 個月翻一番的速度增長。用戶要在如此浩瀚的信息海洋里尋找信息，必然會“大海撈針”無功而返 。 搜索引擎正是為了解決這個“迷航”問題而出現(xiàn)的技術。搜索引擎以一定的策略在互聯(lián)網(wǎng)中搜集、發(fā)現(xiàn)進行理解、提取、組織和處理，并為用戶提供檢索服務，從而起到信息導航的目的。搜索引擎提供的導航服務已經(jīng)成為互聯(lián)網(wǎng)上非常重要的網(wǎng)絡服務，搜索引擎站點也被美譽為“網(wǎng)絡門戶”。搜索引擎技術因而成為計算機工業(yè)界和學術界爭相研究、開發(fā)的對象。 展現(xiàn)狀 發(fā)展歷程 前身是美國國防部高級研究計劃署的研究試驗性網(wǎng)絡 1983 年 P 成為 唯一的正式協(xié)議。此后， 連接的網(wǎng)絡、機器和用戶快速增長。 1988 年 聯(lián)，它的規(guī)模以指數(shù)增長，很多地區(qū)網(wǎng)絡開始加入，并且開始與加拿大、歐洲和太平洋地區(qū)的網(wǎng)絡連接。 后來形成 90 年代初到現(xiàn)在，是 長最迅速的時期。 1993 年，增長速度是 341%。截止到 1996 年 7 月， 連接了 134336第 3 頁 共 47 頁 個網(wǎng)絡，入網(wǎng)主機 1228 萬臺，以及數(shù)以億計的用戶。到 1998 年 7 月， 27 萬個網(wǎng)址， 4300 萬個域名， 臺主機和 個網(wǎng)頁，其規(guī)模大概每年翻一番。 全球性的網(wǎng)絡信息系統(tǒng)。一九八九年，位于瑞士的先開始 了 研究工作。隨后，許多其他的研究機構、大學和公司也加入 究者的行列，并相繼開發(fā)出各自的 件。這些 件的運行平臺覆蓋了目前主流的計算機硬件和操作系統(tǒng)。在此過程中， 不斷完善和發(fā)展。同時，為了保證不同 件之間的互操作性，一系列 議和標準也正在使用和完善之中。 2005 年 7 月 21 日，中國互聯(lián)網(wǎng)絡信息中心 (京發(fā)布“第十六次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告”。報告顯示，截至到 6 月 30 日，我國上網(wǎng)用戶總數(shù)突破 1 億，為 人，半年增加了 900 萬人，和上年同 期相比增長 其中寬帶上網(wǎng)的人數(shù)增長迅猛，首次超過了網(wǎng)民的一半，達到 5300 萬人，增長率為 這也是寬帶用戶首次超過了撥號上網(wǎng)用戶人數(shù)。我國網(wǎng)民數(shù)和寬帶上網(wǎng)人數(shù)均僅次于美國，位居世界第二。 信息分布 的信息資源隨著 發(fā)展而呈現(xiàn)出以下特點： 信息量大而且分散 自治性強 信息資源多種多樣 不一致和不完整性 這些特點對網(wǎng)絡軟件的性能提出了很高的要求。網(wǎng)絡的快速發(fā)展給信息挖掘帶來了挑戰(zhàn)。 信息呈現(xiàn)爆炸性的指數(shù)增長，同時伴隨著上網(wǎng) 經(jīng)驗不足、不第 4 頁 共 47 頁 太曉得如何查找信息的新用戶的加入。用戶很可能最大程度的運用超鏈來在網(wǎng)上沖浪，他們通常從以下兩類網(wǎng)站開始： 第一類是目錄系統(tǒng)，其典型代表是 ）， 它通過有專業(yè)知識的網(wǎng)頁編輯人員對網(wǎng)上的網(wǎng)頁進行精選，建立一個索引目錄，來給用戶提供服務。這類 通過手工維護得很好的 系統(tǒng)的優(yōu)點是提供的網(wǎng)頁準確率高，可以有效的覆蓋所有熱門的主題，但它們的缺點是過于主觀，而且需要高昂的代價來建立和維護，更 新改進的慢，同時不能很好的覆蓋所有深奧的主題 。 第二類是搜索引擎系統(tǒng)， 比如天網(wǎng)（ ）， 它通過程序自動地從網(wǎng)上搜集和分析網(wǎng)頁，建立索引，為用戶服務。這類 通過關鍵詞匹配實現(xiàn)查找的自動更新的搜索引擎 優(yōu)點是涵蓋的網(wǎng)頁數(shù)量巨大，但 通常返回太多的低質(zhì)量相關性不大的結(jié)果。 索引擎簡介 搜索引擎的基本原理是通過網(wǎng)絡機器人定期在 頁上爬行，然后發(fā)現(xiàn)新的網(wǎng)頁，把它們?nèi)』貋矸诺奖镜氐臄?shù)據(jù)庫中，用戶的查詢請 求可以通過查詢本地的數(shù)據(jù)庫來得到。如 天會找到大約 500 萬個新的網(wǎng)頁 搜索引擎一般都有一個 期的訪問一些站點，來檢查這些站點的變化，同時查找新的站點。一般站點有一個 件用來說明服務器不希望問的區(qū)域， 必須遵守這個規(guī)定。如果是自動索引的話， 要對該頁面根據(jù)其內(nèi)容進行索引，根據(jù)它的關鍵字的情況把它歸到某一類中。頁面的信息是通過元數(shù)據(jù)的形式保存的，典型的元數(shù)據(jù)包括標題、 址、一個該頁面的簡要的介紹，關鍵字或者是索引短語、文 件的大小和最后的更新的日期。盡管元數(shù)據(jù)有一定的標準，但是很多站點都采用自己的模板。文檔提取機制和索引策略對 索引擎的有效性有很大的關系。高級的搜索選項一般包括：布爾方法或者是短語匹配和自然語言處理。一個查詢所產(chǎn)生的結(jié)果按照提取機制被分成不同的等級提交給用戶。最相關的放在最前面。每一個第 5 頁 共 47 頁 提取出來的文檔的元數(shù)據(jù)被顯示給用戶。同時包括該文檔所在的 址。 另外有一些關于某一個主題的專門的引擎，它們只對某一個主題的內(nèi)容進行搜索和處理，這樣信息的取全率和精度相對就比較高。 同時，有一類搜索引擎，它本身不用 定期的采集網(wǎng)頁。象 通過向多個搜索引擎同時發(fā)出詢問并對結(jié)果進行綜合返回給用戶實現(xiàn)搜索功能。當然實際上象 夠?qū)Ω鱾€搜索引擎的功能進行分析和比較，根據(jù)不同的用戶查詢提交給不同的搜索引擎進行處理，當然用戶自己也可以指定利用哪一個搜索引擎。 一個優(yōu)秀的搜索引擎必須處理以下幾個問題： 1 網(wǎng)頁的分類 2 自然語言的處理 3 搜索策略的調(diào)度和協(xié)作 4 面向特定用戶的搜索。所以很多搜索引擎不同程度的使用了一些人工智能的技術來解決這些方面的問題 。 面對浩瀚的網(wǎng)絡資源，搜索引擎為所有網(wǎng)上沖浪的用戶提供了一個入口，毫不夸張的說，所有的用戶都可以從搜索出發(fā)到達自己想去的網(wǎng)上任何一個地方。因此它也成為除了電子郵件以外最多人使用的網(wǎng)上服務。 索引擎的發(fā)展 搜索引擎技術伴隨著 發(fā)展是引人注目的。搜索引擎大約經(jīng)歷了三代的更新發(fā)展： 一代搜索引擎 第一代搜索引擎出現(xiàn)于 1994 年。這類搜索引擎一般都索引少于 1， 000， 000個網(wǎng)頁，極少重新搜集網(wǎng)頁并去刷新索引。而且其檢索速度非常慢，一般都要等待 10 秒甚至更長的時間。在實現(xiàn)技術上也 基本沿用較為成熟的 網(wǎng)絡、數(shù)據(jù)庫等技術，相當于利用一些已有技術實現(xiàn)的一個 的應用。在 1994 年 3 月到 4 月，網(wǎng)絡爬蟲 均每天承受大約 1500 次查詢。 第 6 頁 共 47 頁 二代搜索引擎 大約在 1996 年出現(xiàn)的第二代搜索引擎系統(tǒng)大多采用分布式方案（多個微型計算機協(xié)同工作）來提高數(shù)據(jù)規(guī)模、響應速度和用戶數(shù)量，它們一般都保持一個大約 50， 000， 000 網(wǎng)頁的索引數(shù)據(jù)庫，每天能夠響應 10， 000， 000 次用戶檢索請求。 1997 年 11 月，當時最先進的幾個搜索引擎號稱能建立從 2， 000， 000 到100， 000， 000 的網(wǎng)頁索引。 索引擎聲稱他們每天大概要承受 20， 000，000 次查詢。 三代搜索引擎 自 1998 年到現(xiàn)在，出現(xiàn)了一個搜索引擎空前繁榮的時期，我們統(tǒng)稱這一時期的搜索引擎為第三代搜索引擎。第三代搜索引擎的發(fā)展有如下幾個特點： 1. 索引數(shù)據(jù)庫的規(guī)模繼續(xù)增大，一般的商業(yè)搜索引擎都保持在幾千萬甚至上億個網(wǎng)頁。 2. 除了一般意義上的搜索以外，開始出現(xiàn)主題搜索和地域搜索。很多小型的垂直門戶站點開始使 用該技術。 3. 由于搜索返回數(shù)據(jù)量過大，檢索結(jié)果相關度評價成為研究的焦點。相關的研究又可以分為兩類：一類是對超文本鏈的分析，在這方面 學的統(tǒng) 7和 統(tǒng) 8作出了很大的貢獻；另一類是用戶信息的反饋， 統(tǒng)采用的就是這種方法。 4. 開始使用自動分類技術。 在一定程度上使用了該技術。 2000 年搜索引擎 2000 年大會上，按照 司總裁 演講，在用 3,000 臺運行 統(tǒng)的個人電腦在搜集 的網(wǎng)頁，而且以每天 30 臺的速度向這個微機集群里添加電腦，以保持與網(wǎng)絡的發(fā)展相同步。每臺微機運行多個爬蟲程序搜集網(wǎng)頁的峰值速度是每秒 100 個網(wǎng)頁，平均速度是每秒 網(wǎng)頁，一天可以搜集超過 4， 000， 000 網(wǎng)頁。 第 7 頁 共 47 頁 四代搜索引擎 隨著信息多元化的增長，千篇一律的給所有用戶同一個入口顯然已經(jīng)不能滿足特定用戶更深入的查詢需求。同時，這樣的通用搜索引擎在目前的硬件條件下，要及時更新以得到互聯(lián)網(wǎng)上較全面的信息是不太可能的。針對這種情況 ，我們需要一個分類細致精確、數(shù)據(jù)全面深入、更新及時的面向主題的搜索引擎。 由此第四代搜索引擎 主題搜索引擎誕生了，它運用了人工分類以及特征提取等智能化策略，因此比上面提到的前三代的搜索引擎將更加有效和準確。 索引擎的分類 搜索引擎按其工作方式主要可分為三種，分別是全文搜索引擎（ 目錄索引類搜索引擎（ 元搜索引擎（ 文搜索引擎 全文搜索 引擎是名副其實的搜索引擎，國外具代表性的有 ，國內(nèi)著名的有百度（ 它們都是通過從互聯(lián)網(wǎng)上提取的各個網(wǎng)站的信息（以網(wǎng)頁文字為主）而建立的數(shù)據(jù)庫中，檢索與用戶查詢條件匹配的相關記錄，然后按一定的排列順序?qū)⒔Y(jié)果返回給用戶，因此他們是真正的搜索引擎。搜索引擎的自動信息搜集功能分兩種： 一種是定期搜索，即每隔一段時間（比如 般是 28 天），搜索引擎主動派出“蜘蛛”程序，對一定 址范圍內(nèi)的 互聯(lián)網(wǎng)站進行檢索，一旦發(fā)現(xiàn)新的網(wǎng)站，它會自動提取網(wǎng)站的信息和網(wǎng)址加入自己的數(shù)據(jù)庫。 另一種是提交網(wǎng)站搜索，即網(wǎng)站擁有者主動向搜索引擎提交網(wǎng)址，它在一定時間內(nèi)（ 2 天到數(shù)月不等）定向向你的網(wǎng)站派出“蜘蛛”程序，掃描你的網(wǎng)站并將有關信息存入數(shù)據(jù)庫，以備用戶查詢。 第 8 頁 共 47 頁 由于近年來搜索引擎索引規(guī)則發(fā)生了很大變化，主動提交網(wǎng)址并不保證你的網(wǎng)站能進入搜索引擎數(shù)據(jù)庫，因此目前最好的辦法是多獲得一些外部鏈接，讓搜索引擎有更多機會找到你并自動將你的網(wǎng)站收錄。 當用戶以關鍵詞查找信息時，搜索引擎會在數(shù)據(jù)庫中進行搜 尋，如果找到與用戶要求內(nèi)容相符的網(wǎng)站，便采用特殊的算法 通常根據(jù)網(wǎng)頁中關鍵詞的匹配程度，出現(xiàn)的位置 /頻次，鏈接質(zhì)量等 計算出各網(wǎng)頁的相關度及排名等級，然后根據(jù)關聯(lián)度高低，按順序?qū)⑦@些網(wǎng)頁鏈接返回給用戶，從搜索結(jié)果來源的角度，全文搜索引擎又可細分為兩種：一種是擁有自己的檢索程序（ 俗稱“蜘蛛”（ 序或“機器人”（ 序，并自建網(wǎng)頁數(shù)據(jù)庫，搜索結(jié)果直接從自身的數(shù)據(jù)庫中調(diào)用，如上面提到的 7 家引擎；另一種則是租用其他引擎的數(shù)據(jù)庫，并按自定的格式排列搜索結(jié)果，如 擎。 錄索引 目錄索引雖然有搜索功能，但在嚴格意義上算不上是真正的搜索引擎，僅僅是按目錄分類的網(wǎng)站鏈接列表而已。用戶完全可以不用進行關鍵詞（ 詢，僅靠分類目錄也可找到需要的信息。目錄索引中最具代表性的莫過于大名鼎鼎的 虎。其他著名的還有 。國內(nèi)的搜狐、新浪、網(wǎng)易搜索也都屬于這一類。與全文搜索引擎相比，目錄索引有許多不同之處： 首先，搜索引擎屬于自動網(wǎng)站檢索，而目錄索引則完全依 賴手工操作。用戶提交網(wǎng)站后，目錄編輯人員會親自瀏覽你的網(wǎng)站，然后根據(jù)一套自定的評判標準甚至編輯人員的主觀印象，決定是否接納你的網(wǎng)站。 其次，搜索引擎收錄網(wǎng)站時，只要網(wǎng)站本身沒有違反有關的規(guī)則，一般都能登錄成功。而目錄索引對網(wǎng)站的要求則高得多，有時即使登錄多次也不一定成功。尤其象 樣的超級索引，登錄更是困難。 此外，在登錄搜索引擎時，我們一般不用考慮網(wǎng)站的分類問題，而登錄目錄第 9 頁 共 47 頁 索引時則必須將網(wǎng)站放在一個最合適的目錄（ 最后，搜索引擎中各網(wǎng)站的有關信息都是從用戶網(wǎng)頁中自動提取的， 所以用戶的角度看，我們擁有更多的自主權；而目錄索引則要求必須手工另外填寫網(wǎng)站信息，而且還有各種各樣的限制。更有甚者，如果工作人員認為你提交網(wǎng)站的目錄、網(wǎng)站信息不合適，他可以隨時對其進行調(diào)整，當然事先是不會和你商量的。 目前，搜索引擎與目錄索引有相互融合滲透的趨勢。原來一些純粹的全文搜索引擎現(xiàn)在也提供目錄搜索，如 借用 錄提供分類查詢。而象 這些老牌目錄索引則通過與 搜索引擎合作擴大搜索范圍，不過在默認搜索模式下，其目錄中匹配的網(wǎng)站永遠排在搜 索引擎的網(wǎng)頁查詢結(jié)果之前。 在這方面，國內(nèi)幾家著名的搜索引擎網(wǎng)站開始借鑒國外的做法，比如搜狐、新浪就有網(wǎng)站搜索和網(wǎng)頁搜索（來源于百度搜索引擎）之分，用戶可自行選擇。選擇網(wǎng)站搜索時，它們是目錄索引，搜索范圍僅限于自身注冊的網(wǎng)站；而選擇網(wǎng)頁搜索時，它們又成了搜索引擎。 搜索引擎 元搜索引擎 (接受用戶查詢請求時，同時在其他多個引擎上進行搜索，并將結(jié)果返回給用戶。著名的元搜索引擎有 （元搜索引擎列表），中文 元搜索引擎中具代表性的有搜星搜索引擎。在搜索結(jié)果排列方面，有的直接按來源引擎排列搜索結(jié)果，如 的則按自定的規(guī)則將結(jié)果重新排列組合，如 他非主流的引擎 除上述三大類引擎外，還有以下幾種非主流形式： 1、集合式搜索引擎：如 2002 年底推出的引擎。該引擎類似 區(qū)別在于不是同時調(diào)用多個引擎進行搜索，而是由用戶從提供的 4第 10 頁 共 47 頁 個引擎當中選擇，因此叫它“集合式”搜索引擎更確切些。 2、門戶搜索引擎：如 雖然提供搜索服務，但自身即沒有分類目錄也沒有網(wǎng)頁數(shù)據(jù)庫，其搜索結(jié)果完全來自其他引擎。 3、免費鏈接列表（ 稱 這類網(wǎng)站一般只簡單地滾動排列鏈接條目，少部分有簡單的分類目錄，不過規(guī)模比起 目錄索引來要小得多。 由于上述網(wǎng)站都為用戶提供搜索查詢服務，為方便起見，我們通常將其統(tǒng)稱為搜索引擎。 第 11 頁 共 47 頁 第二章 搜索引擎的結(jié)構介紹 一個搜索引擎由搜索器、索引器 、檢索器和用戶接口等四個部分組成。下面是四部分在搜索引擎中的一些功能。 搜索引擎首先盡可能多的從互聯(lián)網(wǎng)中抓取網(wǎng)址，然后把搜索到的網(wǎng)址存放到數(shù)據(jù)庫中，然后通過對這些網(wǎng)址進行分析，去除網(wǎng)頁當中不用的信息，把中文與英文分開處理，因為英文一個個單詞都是用空格分開，所以在處理時直接按原來結(jié)構。中文就要對他進行切詞，把一個個詞分開處理，每個詞中間用空格或標點符號隔開，通過分析每個網(wǎng)頁都生成一個分詞文件，分詞文件由中文詞，英文單詞，數(shù)字和標點符號組成。每個中文詞，英文單詞，數(shù)字之間用標點符號隔開。然后對這些分詞文件進行處 理，把每個詞所在的網(wǎng)頁及其在網(wǎng)頁中的位置標記下來存放到索引表中，最后根據(jù)用戶提供的所要查詢的詞在索引表中查找，把符合查詢條件的詞所在的網(wǎng)頁列出來，并把詞在網(wǎng)頁中的位置的前一部分和后一部分的分別列出來提供給用戶。 索器 搜索器的功能是在互聯(lián)網(wǎng)中漫游，發(fā)現(xiàn)和搜集信息。它常常是一個計算機程序，日夜不停地運行。它要盡可能多、盡可能快地搜集各種類型的新信息，同時因為互聯(lián)網(wǎng)上的信息更新很快，所以還要定期更新已經(jīng)搜集過的舊信息，以避免死連接和無效連接 。目前有兩種搜集信息的策略： 1從一個起始 合開始，順著這些 的超鏈（ 以寬度優(yōu)先、深度優(yōu)先或啟發(fā)式方式循環(huán)地在互聯(lián)網(wǎng)中發(fā)現(xiàn)信息。這些起始 以是任意的 常常是一些非常流行、包含很多鏈接的站點（如 。 2將 間按照域名、 址或國家域名劃分，每個搜索器負責一個子空間的窮盡搜索。 第 12 頁 共 47 頁 搜索器搜集的信息類型多種多樣，包括 章、件、字處理文檔、多媒體信息。 搜索器的實現(xiàn)常常用分布式、并行計算技術，以提 高信息發(fā)現(xiàn)和更新的速度。商業(yè)搜索引擎的信息發(fā)現(xiàn)可以達到每天幾百萬網(wǎng)頁。 搜索器在分析一個網(wǎng)頁的時候，可以得到這個網(wǎng)頁上的所有超鏈接 于每一個 索器都給它賦予一定的權值，才返回給主控程序，以便主控程序按照一定的順序在下一輪發(fā)給搜索器。 引器 索引器的功能是理解搜索器所搜索的信息，從中抽取出索引項，用于表示文檔以及生成文檔庫的索引表。 索引器可以使用集中式索引算法或分布式索引算法。當數(shù)據(jù)量很大時，必須實現(xiàn)即時索引（ 否則不能夠跟上信息量急劇增加 的速度。索引算法對索引器的性能（如大規(guī)模峰值查詢時的響應速度）有很大的影響。一個搜索引擎的有效性在很大程度上取決于索引的質(zhì)量。 索器 檢索器的功能是根據(jù)用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關度評價，對將要輸出的結(jié)果進行排序，并實現(xiàn)某種用戶相關性反饋機制。 檢索器常用的信息檢索模型有集合理論模型、代數(shù)模型、概率模型和混合模型四種。 戶接口 用戶接口的作用是輸入用戶查詢、顯示查詢結(jié)果、提供用戶相關性反饋機制。主要的目的是方便用戶使用搜索引擎，高效率、多方式地從搜 索引擎中得到第 13 頁 共 47 頁 有效、及時的信息。用戶接口的設計和實現(xiàn)使用人機交互的理論和方法，以充分適應人類的思維習慣。 用戶輸入接口可以分為簡單接口和復雜接口兩種： 簡單接口只提供用戶輸入查詢串的文本框； 復雜接口可以讓用戶對查詢進行限制，如邏輯運算（與、或、非； 、 -）、相近關系（相鄰、 域名范圍（如 出現(xiàn)位置（如標題、內(nèi)容）、信息時間、長度等等。目前一些公司和機構正在考慮制定查詢選項的標準。 結(jié) 本小節(jié)介紹了搜索引擎的是如何對用戶所要查詢的詞在網(wǎng)頁中進行搜索的流程， 并且分別對每個模塊進行簡單的介紹。 第 14 頁 共 47 頁 第三章 基于 研究 3.1 索引擎 介紹 是一個完整的全文索引應用，而是是一個用 的全文索引引擎工具包，它可以方便的嵌入到各種應用中實現(xiàn)針對應用的全文索引 /檢索功能。 作者： 貢獻者 一位資深全文索引 /檢索專家，曾經(jīng)是 索引擎 ( 作系統(tǒng)的成就之一 )的主要開發(fā)者，后在 任高級系統(tǒng)架構設計師，目前 從事于一些 層架構的研究。他貢獻出的 目標是為各種中小型應用程序加入全文檢索功能。 發(fā)展歷程：早先發(fā)布在作者自己的 來發(fā)布在2001 年年底成為 金會 一個子項目：，比較著名的有： 壇系統(tǒng)； 件列表 檔 /瀏覽 /查詢系統(tǒng)，本文的主要參考文檔“ 者就是 統(tǒng)的主要開發(fā)者之一，而 已經(jīng)成為目前 目的主要郵件列表歸檔系統(tǒng)。 于 布框架，全文檢索部分使用了 于 開放開發(fā)平臺，幫助部分的全文索引使用了 于中文用戶來說，最關心的問題是其是否支持中文的全文檢索。但通過后面對于 結(jié)構的介紹，你會了解到由于 好架構設計，對中文的支持只需對其語言詞法分析接口進行擴展就能實現(xiàn)對中文檢索的支持。 第 15 頁 共 47 頁 特性分析 心部分 索引排序 索引排序是使用了倒排序原理。 該結(jié)構及相應的生成算法如下： 設有兩篇文章 1 和 2 文章 1 的內(nèi)容為： 文章 2 的內(nèi)容為： He 1. 由于 基于關鍵詞索引和查詢的，首先我們要取得這兩篇文章的關鍵詞，通常我們需要如下處理措施 a. 我們現(xiàn)在有的是文章內(nèi)容，即一個字符串，我們先要找出字符串中的所有單詞，即分詞。英文單詞由于用空格分隔，比較好處理。中文單詞間是連在一起的需要特殊的分詞處理。 b. 文章中的 ” “詞沒有什么實際意義，中文中的 “的 ”“是 ”等字通常也無具體含義， 這些不代表概念的詞可以過濾掉，這個也就是在 細分析中所講的 c. 用戶通常希望查 “能把含 “ “文章也找出來，所以所有單詞需要統(tǒng)一大小寫。 d. 用戶通常希望查 “能把含 “ “文章也找出來，所以需要把“ “原成 “ e. 文章中的標點符號通常不表示某種概念，也可以過濾掉 ,在 以上措施由 完成 ,經(jīng)過上面處理后 : 文章 1 的所有關鍵詞為： 文章 2 的所有關鍵詞為： 2. 有了關鍵詞后，我們就可以建立倒排索引了 上面的對應關系是： “文章號 ”對 “文章中所有關鍵詞 ”。倒排索引把這個關系倒過來，變成： “關鍵詞 ”對 “擁有該關鍵詞的所有文章號 ”。文章 1， 2 經(jīng)過倒排后變第 16 頁 共 47 頁 成 ： 關鍵詞 文章號 1 2 i 1 1,2 2 1 通常僅知道關鍵詞在哪些文章中出現(xiàn)還不夠，我們還需要知道關鍵詞在文章中出現(xiàn)次數(shù)和出現(xiàn)的位置，通常有兩種位置： a)字符位置，即記錄該詞是文章中第幾個字符（優(yōu)點是關鍵詞亮顯時定位快）； b)關鍵詞位置，即記錄該詞是文章中第幾個關鍵詞（優(yōu)點是節(jié)約索引空間、詞組（ 詢快）， 記錄的就是這種位置。 加上 “出現(xiàn)頻率 ”和 “出現(xiàn)位置 ”信息后，我們的索引結(jié)構變?yōu)椋?關鍵詞 文章號 出現(xiàn)頻率 出現(xiàn)位置 12 3， 6 21 1 i 11 4 12,21 2， 5， 2 21 3 11 1 以 行為例我們說明一下該結(jié)構： 文章 1 中出現(xiàn)了 2 次，文章 2中出現(xiàn)了一次，它的出現(xiàn)位置為 “2,5,2”這 表示什么呢？我們需要結(jié)合文章號和出現(xiàn)頻率來分析，文章 1 中出現(xiàn)了 2 次，那么 “2,5”就表示 文章 1 中出現(xiàn)的兩個位置，文章 2 中出現(xiàn)了一次，剩下的 “2”就表示 文章 2 中第 2 個關鍵字。 以上就是 引結(jié)構中最核心的部分。我們注意到關鍵字是按字符順序第 17 頁 共 47 頁 排列的（ 有使用 B 樹結(jié)構），因此 以用二元搜索算法快速定位關鍵詞。 實現(xiàn)時 上面三列分別作為詞典文件（ 頻率文件(位置文件 (存。其中詞典文件不僅保存有每個關鍵詞，還保留了指向頻率文件和位置文件的指針，通過指針可以找到該關鍵字的頻率信息和位置信息。 使用了 概念，用于表達信息所在位置（如標題中，文章中，），在建索引中，該 息也記錄在詞典文件中，每個關鍵詞都有一個息 (因為每個關鍵字一定屬于一個或多個 為了減小索引文件的大小， 索引還使用了壓縮技術。首先，對詞典文件中的關鍵詞進行了壓縮，關鍵詞壓縮為 ，例如：當前詞為 “阿拉伯語 ”，上 一個詞為 “阿拉伯 ”，那么 “阿拉伯語 ”壓縮為 。其次大量用到的是對數(shù)字的壓縮，數(shù)字只保存與上一個值的差值（這樣可以減小數(shù)字的長度，進而減少保存該數(shù)字需要的字節(jié)數(shù)）。例如當前文章號是 16389（不壓縮要用 3 個字節(jié)保存），上一文章號是 16382，壓縮后保存 7（只用一個字節(jié)）。 下面我們可以通過對該索引的查詢來解釋一下為什么要建立索引。 假設要查詢單詞 “ 對詞典二元查找、找到該詞，通過指向頻率文件的指針讀出所有文章號，然后返回結(jié)果。詞典通常非常小，因而，整個過程的時間是毫秒級的。 而用普