【正文】 .............................................................................59致謝 ....................................................................................60參考文獻 ................................................................................61 江漢大學本科畢業(yè)論文（設(shè)計）11 緒論 課題背景及介紹隨著互聯(lián)網(wǎng)的快速發(fā)展，越來越豐富的信息呈現(xiàn)在用戶面前，但同時伴隨的問題是用戶越來越難以獲得其最需要的信息。為了解決此問題，出現(xiàn)了網(wǎng)絡(luò)搜索引擎。網(wǎng)絡(luò)搜索引擎中以基于 WWW 的搜索引擎應用范圍最為廣泛。網(wǎng)絡(luò)搜索引擎是指對 WWW 站點資源和其它資源進行索引和檢索的一類檢索機制。 全文搜索引擎是目前最為普及的應用 ，通過從互聯(lián)網(wǎng)上提取各個網(wǎng)站的信息(以網(wǎng)頁文字為主)建立數(shù)據(jù)庫，用戶查詢的時候便在數(shù)據(jù)庫中檢索與用戶查詢條件相匹配的記錄，最終將匹配的那些記錄，按一定的排列順序顯示給用戶。國外具代表性的全文檢索搜索引擎有 Google、 Yahoo、 Bing 等 ，國內(nèi)著名的有百度、中搜等。目前網(wǎng)絡(luò)中的資源非常豐富，但是如何有效的搜索信息卻是一件困難的事情。建立搜索引擎就是解決這個問題的最好方法之一。該課題要求設(shè)計一個 Web 應用程序，學習搜索引擎的基本原理和設(shè)計方法，應用開源的全文搜索引擎 Lucene 框架和 Lucene的子項目 Nutch 實現(xiàn)一個全文搜索引擎。 課題研究目的及應用 針對搜索引擎廣闊的應用前景以及分析國內(nèi)外搜索引擎的發(fā)展現(xiàn)狀，根據(jù)搜索引擎系統(tǒng)的工作原理設(shè)計一種基于 Inter 的全文搜索引擎模型，它從互聯(lián)網(wǎng)上獲取網(wǎng)頁，建立索引數(shù)據(jù)庫，并采用數(shù)據(jù)庫管理作業(yè)和多線程技術(shù)以提高全文搜索的性能和效率，從技術(shù)上可以適用于任何有全文搜索需求的應用。 課題研究范圍一般來說搜索引擎都由：用戶接口，搜索器，索引生成器和查詢處理器 4 個部分組成。 用戶接口的作用是輸入用戶查詢、顯示查詢結(jié)果、提供用戶相關(guān)性反饋機制。主要的目的是方便用戶使用搜索引擎，高效率、多方式地從搜索引擎中得到有效、及時的信息。用戶接口的設(shè)計和實現(xiàn)使用人機交互的理論和方法，以充分適應人類的思維習慣。 江漢大學本科畢業(yè)論文（設(shè)計）2搜索器用于 WWW 的遍歷和網(wǎng)頁的下載。從一個起始 URL 集合開始，順著這些 URL中的超鏈(Hyperlink)，以寬度優(yōu)先、深度優(yōu)先或啟發(fā)式方式循環(huán)地在互聯(lián)網(wǎng)中發(fā)現(xiàn)信息。 索引生成器對搜索器收集到的網(wǎng)頁和相關(guān)的描述信息經(jīng)索引組織后存儲在索引庫中。 查詢處理器的功能是根據(jù)用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關(guān)度評價， 對將要輸出的結(jié)果進行排序，并實現(xiàn)某種用戶相關(guān)性反饋機制。 小結(jié)本章內(nèi)容主要介紹了課題背景，課題目的，及課題的研究方法與內(nèi)容這些方面。闡述了搜索引擎在顯示應用中的重要性，目前全文搜索引擎的工作組成部分以及各個工作組成部分到底是什么。下面將具體介紹全文搜索引擎的相關(guān)理論，使讀者全文搜索引擎的基本技術(shù)有所了解，為后續(xù)章節(jié)的閱讀打下基礎(chǔ)。 江漢大學本科畢業(yè)論文（設(shè)計）32 搜索引擎相關(guān)理論研究 Web 搜索引擎原理和結(jié)構(gòu)全文搜索引擎是一款網(wǎng)絡(luò)應用軟件系統(tǒng)，論文中全部以搜索引擎稱。最基本的搜索引擎應該包含三個模塊：網(wǎng)頁搜集，預處理，查詢服務。事實上，這三個部分是相互獨立、分別工作的，主要的關(guān)系體現(xiàn)在前一部分得到的數(shù)據(jù)結(jié)果為后一部分提供原始數(shù)據(jù)。 搜索引擎三段式工作流程三者的關(guān)系如圖 21：圖 21 搜索引擎三段式工作流程在介紹搜索引擎的整體結(jié)構(gòu)之前，現(xiàn)在借鑒《計算機網(wǎng)絡(luò)——自頂向下的方法描述因特網(wǎng)特色》一書的敘事方法，從普通用戶使用搜索引擎的角度來介紹搜索引擎的具體工作流程。自頂向下的方法描述搜索引擎執(zhí)行過程：1．用戶通過瀏覽器提交查詢的詞或者短語 P，搜索引擎根據(jù)用戶的查詢返回匹配的網(wǎng)頁信息列表 L；2. 上述過程涉及到兩個問題，如何匹配用戶的查詢以及網(wǎng)頁信息列表從何而來，根據(jù)什么而排序？用戶的查詢 P 經(jīng)過分詞器被切割成小詞組 p1,p2 … pn 并被剔除停用詞 ( 的、了、啊等字 )，根據(jù)系統(tǒng)維護的一個倒排索引可以查詢某個詞 pi 在哪些網(wǎng)頁中出現(xiàn)過，匹配那些 p1,p2 … pn 都出現(xiàn)的網(wǎng)頁集即可作為初始結(jié)果，更進一步，返回的初始網(wǎng)頁集通過計算與查詢詞的相關(guān)度從而得到網(wǎng)頁排名，即 Page 江漢大學本科畢業(yè)論文（設(shè)計）4Rank，按照網(wǎng)頁的排名順序即可得到最終的網(wǎng)頁列表；3. 假設(shè)分詞器和網(wǎng)頁排名的計算公式都是既定的，那么倒排索引以及原始網(wǎng)頁集從何而來？原始網(wǎng)頁集在之前的數(shù)據(jù)流程的介紹中，可以得知是由爬蟲 spider 爬取網(wǎng)頁并且保存在本地的，而倒排索引，即詞組到網(wǎng)頁的映射表是建立在正排索引的基礎(chǔ)上的，后者是分析了網(wǎng)頁的內(nèi)容并對其內(nèi)容進行分詞后，得到的網(wǎng)頁到詞組的映射表，將正排索引倒置即可得到倒排索引；4. 網(wǎng)頁的分析具體做什么呢？由于爬蟲收集來的原始網(wǎng)頁中包含很多信息，比如 html 表單以及一些垃圾信息比如廣告，網(wǎng)頁分析去除這些信息，并抽取其中的正文信息作為后續(xù)的基礎(chǔ)數(shù)據(jù)。 搜索引擎整體結(jié)構(gòu)圖 22 搜索引擎整體結(jié)構(gòu)爬蟲從 Inter 中爬取眾多的網(wǎng)頁作為原始網(wǎng)頁庫存儲于本地，然后網(wǎng)頁分析器抽取網(wǎng)頁中的主題內(nèi)容交給分詞器進行分詞，得到的結(jié)果用索引器建立正排和倒排索引，這樣就得到了索引數(shù)據(jù)庫，用戶查詢時，在通過分詞器切割輸入的查詢詞組并通過檢索器在索引數(shù)據(jù)庫中進行查詢，得到的結(jié)果返回給用戶。 江漢大學本科畢業(yè)論文（設(shè)計）5無論搜索引擎的規(guī)模大小，其主要結(jié)構(gòu)都是由這幾部分構(gòu)成的，并沒有大的差別，搜索引擎的好壞主要是決定于各部分的內(nèi)部實現(xiàn)。有了上述的對與搜索引擎的整體了解，下面對搜索引擎的各個模塊進行說明。 網(wǎng)頁收集全文檢索是工作在某個數(shù)據(jù)集合上的程序，他需要事先由頁面抓取程序，在全網(wǎng)中抓取海量網(wǎng)頁，這個抓取程序也叫網(wǎng)絡(luò)爬蟲或 Spider。只有事先抓取了足夠多的網(wǎng)頁數(shù)據(jù)，并處理之，才能對大量的用戶查詢提供及時的響應。 爬蟲的工作流程網(wǎng)頁收集的過程如同圖的遍歷，其中網(wǎng)頁就作為圖中的節(jié)點，而網(wǎng)頁中的超鏈接則作為圖中的邊，通過某網(wǎng)頁的超鏈接 得到其他網(wǎng)頁的地址，從而可以進一步的進行網(wǎng)頁收集；圖的遍歷分為廣度優(yōu)先和深度優(yōu)先兩種方法，網(wǎng)頁的收集過程也是如此。綜上，Spider 收集網(wǎng)頁的過程如下：從初始 URL 集合獲得目標網(wǎng)頁地址，通過網(wǎng)絡(luò)連接接收網(wǎng)頁數(shù)據(jù)，將獲得的網(wǎng)頁數(shù)據(jù)添加到網(wǎng)頁庫中并且分析該網(wǎng)頁中的其他 URL 鏈接，放入未訪問 URL 集合中用于網(wǎng)頁收集。下圖表示了這個過程：圖 23 Spider 工作流程 爬蟲的抓取策略爬蟲的工作策略一般分為累積式抓?。╟umulative crawling）和增量式抓?。╥ncremental crawing）兩種。 江漢大學本科畢業(yè)論文（設(shè)計）6累積式抓取是指從某一個時間點開始，通過遍歷的方式抓取系統(tǒng)所能允許存儲和處理的所有網(wǎng)頁。在理想的軟硬件環(huán)境下，經(jīng)過足夠的運行時間，積累是抓取策略可以保證抓取到相當規(guī)模的網(wǎng)頁集合。但由于 Web 數(shù)據(jù)的動態(tài)特性，集合中的網(wǎng)頁的抓取時間點是不同的，頁面被更新的情況也不同，因此累積式抓取到的網(wǎng)頁集合事實上并無法與真實環(huán)境中的網(wǎng)絡(luò)數(shù)據(jù)保持一致。與累積式抓取不同，增量式抓取是指在具有一定量規(guī)模的網(wǎng)頁集合的基礎(chǔ)上，采用更新數(shù)據(jù)的方式選取已有集合中的過時頁面進行抓取，以保證所抓取的數(shù)據(jù)與真實網(wǎng)絡(luò)數(shù)據(jù)足夠接近。進行增量式抓取的前提是，系統(tǒng)已經(jīng)抓取了足夠數(shù)量的網(wǎng)絡(luò)頁面，并具有這項頁面被抓取的時間信息。面對實際應用環(huán)境的網(wǎng)絡(luò)蜘蛛設(shè)計中，通常既包含累積式抓取，也包括增量式抓取的策略。累積式抓取一般用戶數(shù)據(jù)集合的整體建立或大規(guī)模更新階段；而增量式抓取則主要針對數(shù)據(jù)集合的日常維護和及時更新。 鏈接數(shù)據(jù)庫的建立初始 URL 的建立有兩種方式：超鏈接和站長提交。超鏈接：爬蟲會根據(jù)種子地址（可能是最先提交給爬蟲的 URL 集合）抓取頁面。站長提交：在實際運行中，爬蟲不可能抓取所有的站點，為此，網(wǎng)站站長可以向搜索引擎進行提交，要求收錄，搜索引擎經(jīng)過核查后，便將該網(wǎng)站加入到 URL 集合中，進行抓取。 鏈接數(shù)據(jù)庫的更新鏈接的注入：抓取程序會根據(jù)預先提供的 URL 集合進行標準化，根據(jù)設(shè)定的正則檢驗來過濾 URL，將這些符合標準的 URL 放入到 map 中，并在構(gòu)造 map 過程中給 URL 初始化得分，分數(shù)可以影響 URL 對應主機的搜索排序和采集優(yōu)先級。接著會判斷 URL 在抓取數(shù)據(jù)庫中是否存在，如果存在，刪除舊的，更新新的。如果不存在，將該 URL 的狀態(tài)標記為未采集過。URL 生成器：從抓取回來的網(wǎng)頁中，將符合條件的 URL 提出出來，檢測 URL 是否在有效更新時間里面，并將 URL 載入相應的任務組，計算 URL 的 hash 值，搜集 URL，直至達到規(guī)定的廣度。 江漢大學本科畢業(yè)論文（設(shè)計）7 網(wǎng)頁預處理網(wǎng)頁預處理的主要目標是將原始網(wǎng)頁通過一步步的數(shù)據(jù)處理變成可方便搜索的數(shù)據(jù)形式。預處理模塊的整體結(jié)構(gòu)如下： 圖 24 預處理模塊的整體結(jié)構(gòu)通過爬蟲的收集，保存下來的網(wǎng)頁信息具有較好的信息存儲格式，但是還是有一個缺點，就是不能按照網(wǎng)頁 URL 直接定位到所指向的網(wǎng)頁。所以，需要先建立網(wǎng)頁的索引，如此通過索引，這樣可以很方便的從原始網(wǎng)頁庫中獲得某個 URL 對應的頁面信息。之后，處理網(wǎng)頁數(shù)據(jù)，對于一個網(wǎng)頁，首先需要提取其網(wǎng)頁正文信息，其次對正文信息進行分詞，之后再根據(jù)分詞的情況建立索引和倒排索引，這樣，網(wǎng)頁的預處理也全部完成。 建立索引頁面庫索引的主要過程： 江漢大學本科畢業(yè)論文（設(shè)計）8圖 25 索引的主要過程索引過程可分為三個主要的操作階段：將數(shù)據(jù)轉(zhuǎn)換成文本分析文本將分析過的文本保存到數(shù)據(jù)庫中轉(zhuǎn)換成文本。在索引數(shù)據(jù)之前，首先必須將數(shù)據(jù)轉(zhuǎn)換成純文本字符流。但是，在現(xiàn)實世界中，信息多以富媒體文檔格式呈現(xiàn)：PDF,WORD,EXCEL,HTML,XML 等。為此需要使用文檔解析器，將富媒體轉(zhuǎn)換成純文字字符流。分析文本。在對數(shù)據(jù)進行索引錢，還必須進行預處理，對數(shù)據(jù)進行分析是之更加適合被索引。分析數(shù)據(jù)時，現(xiàn)將文本數(shù)據(jù)切分成一些大塊或者詞匯單元，然后對它們執(zhí)行一些可選的操作，例如：在索引之前將這些詞匯單元轉(zhuǎn)換成小寫，使得搜索對大小寫不敏感；具有代表性的是要從輸入中去掉一些使用很頻繁但卻沒有實際意義的詞，比如英文文本中的一些停用詞（a、an、the、in、on 等）。同樣的，也需要分析輸入的詞匯單元，一遍從詞語中去掉一些不必要的字母以找到他們的詞干。這一處理過程稱為分析。將分析后的數(shù)據(jù)寫入索引。對輸入數(shù)據(jù)分析處理完成后，就可以將結(jié)果寫入索引文件中。結(jié)果一般包括網(wǎng)頁標題，正文，所屬住地址，主機，內(nèi)容摘要，時間戳，當前 URL 地址等，并更具具體需要建立索引和存儲。 江漢大學本科畢業(yè)論文（設(shè)計）9 分詞中文分詞是指將一個漢字序列切分成一個一個單獨的詞，從而達到計算機可以自動識別的效果。中文分詞主要有三種方法：第一種基于字符串匹配，第二種基于語義理解，第三種基于統(tǒng)計。由于第二和第三種的實現(xiàn)需要大量的數(shù)據(jù)來支持，一般采用的是基于字符串匹配的方法?；谧址ヅ涞姆椒ㄓ纸凶鰴C械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況，可以分為最大（最長）匹配和最?。ㄗ疃蹋┢ヅ?。常用的幾種機械分詞方法如下：正向減字最大匹配法（由左到右的方向）；逆向減字最大匹配法（由右到左的方向）；最少切分（使每一句中切出的詞數(shù)最?。?；雙向最大減字匹配法（進行由左到右、由右到左兩次掃描）；采用其中的正向最大匹配法。算法描述如下：輸入值為一個中文語句 S，以及最大匹配詞 n取 S 中前 n 個字，根據(jù)詞典對其進行匹配，若匹配成功，轉(zhuǎn) 3，否則轉(zhuǎn) 2；n = n – 1：如果 n 為 1，轉(zhuǎn) 3；否則轉(zhuǎn) 1；將 S 中的前 n 個字作為分詞結(jié)果的一部分，S 除去前 n 個字，若 S 為空，轉(zhuǎn) 4；否則，轉(zhuǎn) 1；算法結(jié)束。需要說明的是，在第三步的起始，n 如果不為 1，則意味著有匹配到的詞；而如果 n 為 1，默認 1 個字是應該進入分詞結(jié)果的，所以第三步可以將前 n 個字作為一個詞而分割開來。還有需要注意的是對于停用詞的過濾，停用詞即漢語中“的，了，和，么”等字詞，在搜索引擎中是忽略的，所以對于分詞后的結(jié)果，需要在用停用詞列表進行一下停用詞過濾。您也許有疑問，如何獲