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