全文搜索引擎的設計與實現(xiàn)-畢業(yè)論文

1、<p><b>　　作者聲明</b></p><p>　　本人鄭重聲明：所呈交的學位論文是本人在導師的指導下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。</p><p>　　本人完全了解有關保障、使用學位論文的規(guī)定，同意學校保留并向有關學位論文管理機構送交論文的復印件和電子版。同意省

2、級優(yōu)秀學位論文評選機構將本學位論文通過影印、縮印、掃描等方式進行保存、摘編或匯編；同意本論文被編入有關數(shù)據(jù)庫進行檢索和查閱。</p><p>　　本學位論文內容不涉及國家機密。</p><p>　　論文題目：全文搜索引擎的設計與實現(xiàn)</p><p>　　作者單位：江漢大學數(shù)學與計算機科學學院</p><p><b>　　作者簽名：X

3、XX </b></p><p>　　2013年 5 月 20 日</p><p><b>　　學士學位論文</b></p><p>　　論文題目 全文搜索引擎的設計與實現(xiàn) </p><p>　　（英 文） Full-text search engine design and Implementat

4、ion </p><p>　　學 院 數(shù)學與計算機科學學院</p><p>　　專 業(yè) 計算機科學與技術 </p><p>　　班 級 B09082021 </p><p>　　姓 名 XXX </p><p>　　學

5、 號 200708202137 </p><p>　　指導老師 YYY </p><p>　　2013 年5月20日</p><p><b>　　摘要</b></p><p>　　目前定制和維護搜索引擎的需求越來越大，對于處理龐大的網(wǎng)絡數(shù)據(jù)，如何有效的去存儲它并訪

6、問到我們需要的信息，變得尤為重要。Web搜索引擎能有很好的幫助我們解決這一問題。</p><p>　　本文闡述了一個全文搜索引擎的原理及其設計和實現(xiàn)過程。該系統(tǒng)采用B/S模式的Java Web平臺架構實現(xiàn)，采用Nutch相關框架，包括Nutch，Solr，Hadoop,以及Nutch的基礎框架Lucene對全網(wǎng)信息的采集和檢索。文中闡述了Nutch相關框架的背景，基礎原理和應用。</p><p

7、>　　Nutch相關框架的出現(xiàn)，使得在java平臺上構建個性化搜索引擎成為一件簡單又可靠的事情。Nutch 致力于讓每個人能很容易, 同時花費很少就可以配置世界一流的Web搜索引擎。目前國內有很多大公司，比如百度、雅虎，都在使用Nutch相關框架。由于Nutch是開源的，閱讀其源代碼，可以讓我們對搜索引擎實現(xiàn)有更加深刻的感受，并且能夠更加深度的定制需要的搜索引擎實現(xiàn)細節(jié)。</p><p>　　本文首先介紹了

8、課題研究背景，然后對系統(tǒng)涉及到的理論知識，框架的相關理論做了詳細說明，最后按照軟件工程的開發(fā)方法逐步實現(xiàn)系統(tǒng)功能。</p><p><b>　　關鍵詞</b></p><p>　　Nutch、Solr、Hadoop、Lucene、搜索引擎</p><p><b>　　Abstract</b></p><

9、p>　　Currently, the requirement of customizing and the search engine maintenance is larger and larger. For dealing with such enormous network data, especially, how to store it and access our necessary information has b

10、ecome so significant. However,web search engine can help us to solve this problem well.</p><p>　　This acticle describes the principle of full-text search engine,and

11、60;the process for its design and implementation. This system adopts Java Web platform with B/S model, and also the relative&

12、#160;frame of Nutch, including Nutch,Solr,Hadoop, and collection and inspection for whole network information based on Lucene--the foundation

13、0;of Nutch. All in all, this text mainly elaborates the backgroud of relative frame, basical principle, and application for N

14、utch.</p><p>　　The appearance of Nutch related framework, makes that building an personalized search engine based on Java platf

15、orm to be an simple and reliable way. Nutch is committed to make everyone configure a word-class web search engine easil

16、y and low-costly.At present, there are many big companies at home, like baidu, yahoo, are using such Nutch relative frame.

17、60; Due to the fact that Nutch is open-source, reading its source code can let us have a more profound experience w

18、hen realizing the search engine, </p><p>　　At frist, this article introduces the background of research project. Then, it specifically describes the theoretical knowledge of system a

19、nd the related theory of framework. Finally, it achieves the system function step by step according to the development method of software engineering.</p><p><b>　　Keywords</b></p><p>

20、;　　Nutch、Solr、Hadoop、Lucene、Search Engine</p><p><b>　　目錄</b></p><p><b>　　1 緒論1</b></p><p>　　1.1 課題背景及介紹1</p><p>　　1.2 課題研究目的及應用1</p>&

21、lt;p>　　1.3 課題研究范圍1</p><p><b>　　1.4 小結2</b></p><p>　　2 搜索引擎相關理論研究3</p><p>　　2.1 Web搜索引擎原理和結構3</p><p>　　2.1.1 搜索引擎三段式工作流程3</p><p>　　2.1.2

22、 搜索引擎整體結構4</p><p>　　2.2 網(wǎng)頁收集5</p><p>　　2.1.2 爬蟲的工作流程5</p><p>　　2.1.3 爬蟲的抓取策略5</p><p>　　2.1.4 鏈接數(shù)據(jù)庫的建立6</p><p>　　2.1.5 鏈接數(shù)據(jù)庫的更新6</p><p>　

23、　2.3網(wǎng)頁預處理6</p><p>　　2.3.1 建立索引頁面庫7</p><p>　　2.3.2 分詞9</p><p>　　2.3.3 倒排索引10</p><p>　　2.4 查詢服務12</p><p>　　2.4.1 查詢方式和匹配12</p><p>　　2.4.2

24、結果排序13</p><p>　　2.4.3 文檔摘要14</p><p><b>　　2.5 小結15</b></p><p>　　3 Nutch相關框架研究16</p><p>　　3.1 Lucene研究16</p><p>　　3.1.1 Lucene概述16</p>

25、;<p>　　3.1.2 Lucene如何對索引進行搜索16</p><p>　　3.1.3 Lucene增刪改索引的API17</p><p>　　3.2 Nutch研究21</p><p>　　3.2.1 Nutch概述21</p><p>　　3.2.2 研究Nutch的原因21</p><p

26、>　　3.2.3 研究Nutch的目標22</p><p>　　3.2.4 Nutch和 Lucene比較22</p><p>　　3.2.5 Nutch常用命令22</p><p>　　3.3 Solr研究28</p><p>　　3.3.1 Solr概述28</p><p>　　3.3.2 Solr

27、索引28</p><p>　　3.3.3 Solr搜索29</p><p>　　3.3.4 Lucene索引查看工具Luke31</p><p>　　3.4 Hadoop研究32</p><p>　　3.4.1 Hadoop概述32</p><p>　　3.4.2 Hadoop單機本地模式34</p&

28、gt;<p>　　3.4.3 Hadoop單機偽分布式模式34</p><p><b>　　3.5 小結36</b></p><p>　　4 全文搜索引擎系統(tǒng)分析與技術選型37</p><p>　　4.1 系統(tǒng)目標需求37</p><p>　　4.2 系統(tǒng)功能項37</p><

29、p>　　4.3 可行性分析與決策37</p><p>　　4.3.1 技術可行性38</p><p>　　4.3.2 經(jīng)濟可行性38</p><p><b>　　4.4 小結39</b></p><p>　　5 全文搜索引擎系統(tǒng)設計與實現(xiàn)40</p><p>　　5.1 系統(tǒng)功能圖

30、40</p><p>　　5.2 系統(tǒng)實體設計40</p><p>　　5.2.1 實體40</p><p>　　5.2.2 實體的屬性41</p><p>　　5.2.3 實體間的聯(lián)系42</p><p>　　5.3 系統(tǒng)實現(xiàn)42</p><p>　　5.3.1 系統(tǒng)需要的環(huán)境4

31、2</p><p>　　5.3.2 系統(tǒng)中Nutch的配置43</p><p>　　5.3.3 對整個網(wǎng)絡進行抓取44</p><p>　　5.3.4 Solr安裝配置和使用47</p><p>　　5.3.5 給Solr 4.2添加mmseg4j48</p><p>　　5.3.6 客戶端應用程序的實現(xiàn)4

32、9</p><p><b>　　5.4 小結56</b></p><p>　　6 全文搜索引擎系統(tǒng)評價57</p><p>　　6.1 系統(tǒng)特色57</p><p>　　6.2 系統(tǒng)存在的不足和解決方案57</p><p>　　6.2.1 系統(tǒng)存在的不足57</p><

33、;p>　　6.2.2 改進措施58</p><p>　　6.2.3 畢業(yè)設計心得與收獲58</p><p><b>　　7 結束語59</b></p><p><b>　　致謝60</b></p><p><b>　　參考文獻61</b></p>

34、<p><b>　　1 緒論</b></p><p>　　1.1 課題背景及介紹</p><p>　　隨著互聯(lián)網(wǎng)的快速發(fā)展，越來越豐富的信息呈現(xiàn)在用戶面前，但同時伴隨的問題是用戶越來越難以獲得其最需要的信息。為了解決此問題，出現(xiàn)了網(wǎng)絡搜索引擎。網(wǎng)絡搜索引擎中以基于 WWW 的搜索引擎應用范圍最為廣泛。網(wǎng)絡搜索引擎是指對WWW站點資源和其它資源進行索引和檢索的

35、一類檢索機制。 全文搜索引擎是目前最為普及的應用 ，通過從互聯(lián)網(wǎng)上提取各個網(wǎng)站的信息(以網(wǎng)頁文字為主)建立數(shù)據(jù)庫，用戶查詢的時候便在數(shù)據(jù)庫中檢索與用戶查詢條件相匹配的記錄，最終將匹配的那些記錄，按一定的排列順序顯示給用戶。國外具代表性的全文檢索搜索引擎有 Google、 Yahoo、 Bing等 ，國內著名的有百度、中搜等。</p><p>　　目前網(wǎng)絡中的資源非常豐富，但是如何有效的搜索信息卻是一件困難的事情。

36、建立搜索引擎就是解決這個問題的最好方法之一。該課題要求設計一個Web應用程序，學習搜索引擎的基本原理和設計方法，應用開源的全文搜索引擎Lucene框架和Lucene的子項目Nutch實現(xiàn)一個全文搜索引擎。</p><p>　　1.2 課題研究目的及應用</p><p>　　針對搜索引擎廣闊的應用前景以及分析國內外搜索引擎的發(fā)展現(xiàn)狀，根據(jù)搜索引擎系統(tǒng)的工作原理設計一種基于Internet的全

37、文搜索引擎模型，它從互聯(lián)網(wǎng)上獲取網(wǎng)頁，建立索引數(shù)據(jù)庫，并采用數(shù)據(jù)庫管理作業(yè)和多線程技術以提高全文搜索的性能和效率，從技術上可以適用于任何有全文搜索需求的應用。</p><p>　　1.3 課題研究范圍</p><p>　　一般來說搜索引擎都由：用戶接口，搜索器，索引生成器和查詢處理器4個部分組成。 </p><p>　　用戶接口的作用是輸入用戶查詢、顯示查詢結果、提

38、供用戶相關性反饋機制。主要的目的是方便用戶使用搜索引擎，高效率、多方式地從搜索引擎中得到有效、及時的信息。用戶接口的設計和實現(xiàn)使用人機交互的理論和方法，以充分適應人類的思維習慣。 </p><p>　　搜索器用于WWW的遍歷和網(wǎng)頁的下載。從一個起始URL集合開始，順著這些URL中的超鏈(Hyperlink)，以寬度優(yōu)先、深度優(yōu)先或啟發(fā)式方式循環(huán)地在互聯(lián)網(wǎng)中發(fā)現(xiàn)信息。 </p><p>　　

39、索引生成器對搜索器收集到的網(wǎng)頁和相關的描述信息經(jīng)索引組織后存儲在索引庫中。 </p><p>　　查詢處理器的功能是根據(jù)用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關度評價， 對將要輸出的結果進行排序，并實現(xiàn)某種用戶相關性反饋機制。</p><p><b>　　1.4 小結</b></p><p>　　本章內容主要介紹了課題背景，課題目

40、的，及課題的研究方法與內容這些方面。闡述了搜索引擎在顯示應用中的重要性，目前全文搜索引擎的工作組成部分以及各個工作組成部分到底是什么。下面將具體介紹全文搜索引擎的相關理論，使讀者全文搜索引擎的基本技術有所了解，為后續(xù)章節(jié)的閱讀打下基礎。</p><p>　　2 搜索引擎相關理論研究</p><p>　　2.1 Web搜索引擎原理和結構</p><p>　　全文搜索引

41、擎是一款網(wǎng)絡應用軟件系統(tǒng)，論文中全部以搜索引擎稱。最基本的搜索引擎應該包含三個模塊：網(wǎng)頁搜集，預處理，查詢服務。事實上，這三個部分是相互獨立、分別工作的，主要的關系體現(xiàn)在前一部分得到的數(shù)據(jù)結果為后一部分提供原始數(shù)據(jù)。</p><p>　　2.1.1 搜索引擎三段式工作流程</p><p>　　三者的關系如圖2-1：</p><p>　　圖2-1搜索引擎三段式工作流程

42、</p><p>　　在介紹搜索引擎的整體結構之前，現(xiàn)在借鑒《計算機網(wǎng)絡——自頂向下的方法描述因特網(wǎng)特色》一書的敘事方法，從普通用戶使用搜索引擎的角度來介紹搜索引擎的具體工作流程。</p><p>　　自頂向下的方法描述搜索引擎執(zhí)行過程：</p><p>　　1．用戶通過瀏覽器提交查詢的詞或者短語 P，搜索引擎根據(jù)用戶的查詢返回匹配的網(wǎng)頁信息列表 L；</p&

43、gt;<p>　　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)頁集即可作為初始結果，更進一步，返回的初始網(wǎng)頁集通過計算與查詢詞的相關度

44、從而得到網(wǎng)頁排名，即 Page Rank，按照網(wǎng)頁的排名順序即可得到最終的網(wǎng)頁列表；</p><p>　　3. 假設分詞器和網(wǎng)頁排名的計算公式都是既定的，那么倒排索引以及原始網(wǎng)頁集從何而來？原始網(wǎng)頁集在之前的數(shù)據(jù)流程的介紹中，可以得知是由爬蟲 spider 爬取網(wǎng)頁并且保存在本地的，而倒排索引，即詞組到網(wǎng)頁的映射表是建立在正排索引的基礎上的，后者是分析了網(wǎng)頁的內容并對其內容進行分詞后，得到的網(wǎng)頁到詞組的映射表，將

45、正排索引倒置即可得到倒排索引；</p><p>　　4. 網(wǎng)頁的分析具體做什么呢？由于爬蟲收集來的原始網(wǎng)頁中包含很多信息，比如 html 表單以及一些垃圾信息比如廣告，網(wǎng)頁分析去除這些信息，并抽取其中的正文信息作為后續(xù)的基礎數(shù)據(jù)。</p><p>　　2.1.2 搜索引擎整體結構</p><p>　　圖2-2 搜索引擎整體結構</p><p>

46、;　　爬蟲從 Internet 中爬取眾多的網(wǎng)頁作為原始網(wǎng)頁庫存儲于本地，然后網(wǎng)頁分析器抽取網(wǎng)頁中的主題內容交給分詞器進行分詞，得到的結果用索引器建立正排和倒排索引，這樣就得到了索引數(shù)據(jù)庫，用戶查詢時，在通過分詞器切割輸入的查詢詞組并通過檢索器在索引數(shù)據(jù)庫中進行查詢，得到的結果返回給用戶。</p><p>　　無論搜索引擎的規(guī)模大小，其主要結構都是由這幾部分構成的，并沒有大的差別，搜索引擎的好壞主要是決定于各部分

47、的內部實現(xiàn)。</p><p>　　有了上述的對與搜索引擎的整體了解，下面對搜索引擎的各個模塊進行說明。</p><p><b>　　2.2 網(wǎng)頁收集</b></p><p>　　全文檢索是工作在某個數(shù)據(jù)集合上的程序，他需要事先由頁面抓取程序，在全網(wǎng)中抓取海量網(wǎng)頁，這個抓取程序也叫網(wǎng)絡爬蟲或Spider。只有事先抓取了足夠多的網(wǎng)頁數(shù)據(jù)，并處理之，

48、才能對大量的用戶查詢提供及時的響應。</p><p>　　2.1.2 爬蟲的工作流程</p><p>　　網(wǎng)頁收集的過程如同圖的遍歷，其中網(wǎng)頁就作為圖中的節(jié)點，而網(wǎng)頁中的超鏈接則作為圖中的邊，通過某網(wǎng)頁的超鏈接 得到其他網(wǎng)頁的地址，從而可以進一步的進行網(wǎng)頁收集；圖的遍歷分為廣度優(yōu)先和深度優(yōu)先兩種方法，網(wǎng)頁的收集過程也是如此。綜上，Spider 收集網(wǎng)頁的過程如下：從初始 URL 集合獲得目

49、標網(wǎng)頁地址，通過網(wǎng)絡連接接收網(wǎng)頁數(shù)據(jù)，將獲得的網(wǎng)頁數(shù)據(jù)添加到網(wǎng)頁庫中并且分析該網(wǎng)頁中的其他 URL 鏈接，放入未訪問 URL 集合中用于網(wǎng)頁收集。下圖表示了這個過程：</p><p>　　圖2-3 Spider工作流程</p><p>　　2.1.3 爬蟲的抓取策略</p><p>　　爬蟲的工作策略一般分為累積式抓取（cumulative crawling）和增量

50、式抓?。╥ncremental crawing）兩種。</p><p>　　累積式抓取是指從某一個時間點開始，通過遍歷的方式抓取系統(tǒng)所能允許存儲和處理的所有網(wǎng)頁。在理想的軟硬件環(huán)境下，經(jīng)過足夠的運行時間，積累是抓取策略可以保證抓取到相當規(guī)模的網(wǎng)頁集合。但由于Web數(shù)據(jù)的動態(tài)特性，集合中的網(wǎng)頁的抓取時間點是不同的，頁面被更新的情況也不同，因此累積式抓取到的網(wǎng)頁集合事實上并無法與真實環(huán)境中的網(wǎng)絡數(shù)據(jù)保持一致。<

51、/p><p>　　與累積式抓取不同，增量式抓取是指在具有一定量規(guī)模的網(wǎng)頁集合的基礎上，采用更新數(shù)據(jù)的方式選取已有集合中的過時頁面進行抓取，以保證所抓取的數(shù)據(jù)與真實網(wǎng)絡數(shù)據(jù)足夠接近。進行增量式抓取的前提是，系統(tǒng)已經(jīng)抓取了足夠數(shù)量的網(wǎng)絡頁面，并具有這項頁面被抓取的時間信息。</p><p>　　面對實際應用環(huán)境的網(wǎng)絡蜘蛛設計中，通常既包含累積式抓取，也包括增量式抓取的策略。累積式抓取一般用戶數(shù)據(jù)集

52、合的整體建立或大規(guī)模更新階段；而增量式抓取則主要針對數(shù)據(jù)集合的日常維護和及時更新。</p><p>　　2.1.4 鏈接數(shù)據(jù)庫的建立</p><p>　　初始URL的建立有兩種方式：超鏈接和站長提交。</p><p>　　超鏈接：爬蟲會根據(jù)種子地址（可能是最先提交給爬蟲的URL集合）抓取頁面。</p><p>　　站長提交：在實際運行中，爬蟲

53、不可能抓取所有的站點，為此，網(wǎng)站站長可以向搜索引擎進行提交，要求收錄，搜索引擎經(jīng)過核查后，便將該網(wǎng)站加入到URL集合中，進行抓取。</p><p>　　2.1.5 鏈接數(shù)據(jù)庫的更新</p><p>　　鏈接的注入：抓取程序會根據(jù)預先提供的URL集合進行標準化，根據(jù)設定的正則檢驗來過濾URL，將這些符合標準的URL放入到map中，并在構造map過程中給URL初始化得分，分數(shù)可以影響URL對應

54、主機的搜索排序和采集優(yōu)先級。接著會判斷URL在抓取數(shù)據(jù)庫中是否存在，如果存在，刪除舊的，更新新的。如果不存在，將該URL的狀態(tài)標記為未采集過。</p><p>　　URL生成器：從抓取回來的網(wǎng)頁中，將符合條件的URL提出出來，檢測URL是否在有效更新時間里面，并將URL載入相應的任務組，計算URL的hash值，搜集URL，直至達到規(guī)定的廣度。</p><p><b>　　2.3網(wǎng)

55、頁預處理</b></p><p>　　網(wǎng)頁預處理的主要目標是將原始網(wǎng)頁通過一步步的數(shù)據(jù)處理變成可方便搜索的數(shù)據(jù)形式。</p><p>　　預處理模塊的整體結構如下：</p><p>　　圖2-4 預處理模塊的整體結構</p><p>　　通過爬蟲的收集，保存下來的網(wǎng)頁信息具有較好的信息存儲格式，但是還是有一個缺點，就是不能按照網(wǎng)頁

56、 URL 直接定位到所指向的網(wǎng)頁。所以，需要先建立網(wǎng)頁的索引，如此通過索引，這樣可以很方便的從原始網(wǎng)頁庫中獲得某個 URL 對應的頁面信息。之后，處理網(wǎng)頁數(shù)據(jù)，對于一個網(wǎng)頁，首先需要提取其網(wǎng)頁正文信息，其次對正文信息進行分詞，之后再根據(jù)分詞的情況建立索引和倒排索引，這樣，網(wǎng)頁的預處理也全部完成。</p><p>　　2.3.1 建立索引頁面庫</p><p><b>　　索引的主

57、要過程：</b></p><p>　　圖2-5索引的主要過程</p><p>　　索引過程可分為三個主要的操作階段：</p><p><b>　　將數(shù)據(jù)轉換成文本</b></p><p><b>　　分析文本</b></p><p>　　將分析過的文本保存到數(shù)據(jù)庫

58、中</p><p>　　轉換成文本。在索引數(shù)據(jù)之前，首先必須將數(shù)據(jù)轉換成純文本字符流。但是，在現(xiàn)實世界中，信息多以富媒體文檔格式呈現(xiàn)：PDF,WORD,EXCEL,HTML,XML等。為此需要使用文檔解析器，將富媒體轉換成純文字字符流。</p><p>　　分析文本。在對數(shù)據(jù)進行索引錢，還必須進行預處理，對數(shù)據(jù)進行分析是之更加適合被索引。分析數(shù)據(jù)時，現(xiàn)將文本數(shù)據(jù)切分成一些大塊或者詞匯單元，

59、然后對它們執(zhí)行一些可選的操作，例如：在索引之前將這些詞匯單元轉換成小寫，使得搜索對大小寫不敏感；具有代表性的是要從輸入中去掉一些使用很頻繁但卻沒有實際意義的詞，比如英文文本中的一些停用詞（a、an、the、in、on等）。同樣的，也需要分析輸入的詞匯單元，一遍從詞語中去掉一些不必要的字母以找到他們的詞干。這一處理過程稱為分析。將分析后的數(shù)據(jù)寫入索引。對輸入數(shù)據(jù)分析處理完成后，就可以將結果寫入索引文件中。結果一般包括網(wǎng)頁標題，正文，所屬住

60、地址，主機，內容摘要，時間戳，當前URL地址等，并更具具體需要建立索引和存儲。</p><p><b>　　2.3.2 分詞</b></p><p>　　中文分詞是指將一個漢字序列切分成一個一個單獨的詞，從而達到計算機可以自動識別的效果。中文分詞主要有三種方法：第一種基于字符串匹配，第二種基于語義理解，第三種基于統(tǒng)計。由于第二和第三種的實現(xiàn)需要大量的數(shù)據(jù)來支持，一般采

61、用的是基于字符串匹配的方法。</p><p>　　基于字符串匹配的方法又叫做機械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況，可以分為最大（最長）匹配和最?。ㄗ疃蹋┢ヅ?。常用的幾種機械分詞方法如下：</p><p

62、>　　正向減字最大匹配法（由左到右的方向）；</p><p>　　逆向減字最大匹配法（由右到左的方向）；</p><p>　　最少切分（使每一句中切出的詞數(shù)最?。?；</p><p>　　雙向最大減字匹配法（進行由左到右、由右到左兩次掃描）；</p><p>　　采用其中的正向最大匹配法。算法描述如下：輸入值為一個中文語句 S，以及最大匹

63、配詞 n</p><p>　　取 S 中前 n 個字，根據(jù)詞典對其進行匹配，若匹配成功，轉 3，否則轉 2；</p><p>　　n = n – 1：如果 n 為 1，轉 3；否則轉 1；</p><p>　　將 S 中的前 n 個字作為分詞結果的一部分，S 除去前 n 個字，若 S 為空，轉 4；否則，轉 1；</p><p><b&

64、gt;　　算法結束。</b></p><p>　　需要說明的是，在第三步的起始，n 如果不為 1，則意味著有匹配到的詞；而如果 n 為 1，默認 1 個字是應該進入分詞結果的，所以第三步可以將前 n 個字作為一個詞而分割開來。還有需要注意的是對于停用詞的過濾，停用詞即漢語中“的，了，和，么”等字詞，在搜索引擎中是忽略的，所以對于分詞后的結果，需要在用停用詞列表進行一下停用詞過濾。</p>

65、<p>　　您也許有疑問，如何獲得分詞字典或者是停用詞字典。停用詞字典比較好辦，由于中文停用詞數(shù)量有限，可以從網(wǎng)上獲得停用詞列表，從而自己建一個停用詞字典；然而對于分詞字典，雖然網(wǎng)上有許多知名的漢字分詞軟件，但是很少有分詞的字典提供。在程序使用過程中，分詞字典可以放入一個集合中，這樣就可以比較方便的進行比對工作。</p><p>　　分詞的結果對于搜索的精準性有著至關重要的影響，好的分詞策略經(jīng)常是由若

66、干個簡單算法拼接而成的，所以您也可以試著實現(xiàn)雙向最大減字匹配法來提高分詞的準確率。而如果遇到歧義詞組，可以通過字典中附帶的詞頻來決定哪種分詞的結果更好。</p><p>　　2.3.3 倒排索引</p><p>　　倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

67、它是文檔索引系統(tǒng)中最常用的數(shù)據(jù)結構。</p><p>　　有兩種不同的反向索引形式：</p><p>　　一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。</p><p>　　一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。</p><p>　　后者的形式提供了更多的兼容性（比如短語搜索），

68、但是需要更多的時間和空間來創(chuàng)建。</p><p>　　下面將以圖示和實例的方式分別說明正向索引和倒排索引。</p><p><b>　　圖2-6正向索引</b></p><p><b>　　圖2-7倒排索引</b></p><p>　　以英文為例，下面是要被索引的文本：</p><

69、;p>　　"it is what it is"</p><p>　　"what is it"</p><p>　　"it is a banana"</p><p>　　這樣就能得到下面的反向文件索引：</p><p>　　"a": {2}</

70、p><p>　　"banana": {2}</p><p>　　"is": {0, 1, 2}</p><p>　　"it": {0, 1, 2}</p><p>　　"what": {0, 1}</p><p>　　檢索的

71、條件"what", "is" 和 "it" 將對應這個集合：。</p><p>　　對相同的文字，得到后面這些完全反向索引，有文檔數(shù)量和當前查詢的單詞結果組成的的成對數(shù)據(jù)。 同樣，文檔數(shù)量和當前查詢的單詞結果都從零開始。所以，"banana": {(2, 3)} 就是說 "b

72、anana"在第三個文檔里 ()，而且在第三個文檔的位置是第四個單詞(地址為 3)。</p><p>　　"a": {(2, 2)}</p><p>　　"banana": {(2, 3)}</p><p>　　"is": {(0, 1), (0, 4), (1, 1), (2,

73、 1)}</p><p>　　"it": {(0, 0), (0, 3), (1, 2), (2, 0)} </p><p>　　"what": {(0, 2), (1, 0)}</p><p>　　如果執(zhí)行短語搜索"what is it" 將得到這個短語的全部單詞各自的結果所在文檔為

74、文檔0和文檔1。但是這個短語檢索的連續(xù)的條件僅僅在文檔1得到。</p><p><b>　　2.4 查詢服務</b></p><p>　　查詢服務的整體結構如下：</p><p>　　圖2-8查詢服務的整體結構</p><p>　　在網(wǎng)頁預處理后，每個元素至少包含如下幾個方面：原始網(wǎng)頁文檔</p><

75、;p><b>　　URL和標題</b></p><p><b>　　編號</b></p><p>　　所含的重要關鍵詞的集合（以及他們在文檔中出現(xiàn)的位置信息）</p><p>　　其他一些指標（例如重要程度，分類代碼等）</p><p>　　而系統(tǒng)關鍵詞總體的集合和文檔的編號一起構成了一個倒排

76、文件結構，使得一旦得到一個關鍵詞輸入，系統(tǒng)能迅速給出相關文檔編號的集合輸出。 </p><p>　　2.4.1 查詢方式和匹配</p><p>　　查詢方式指的是系統(tǒng)允許用戶提交查詢的形式?？紤]到各種用戶的不同背景和不同的信息需求不可能有一種普適的方式。</p><p>　　一般認為，對于普通網(wǎng)絡用戶來說，最自然的方式就是“要什么就輸入什么”。但這是一種相當模糊的說

77、法。</p><p>　　例如用戶輸入“江漢大學”，可能是他想了解江漢大學目前的招生狀況，可能需要找到江漢大學教務系統(tǒng)的網(wǎng)址，可能需要了解大家對江漢大學的評價。這是三種相當不同的需求。在其他一些情況下，用戶可能關心的是間接的信息，例如“江漢大學錄取分數(shù)線”，450分應該是他需要的，但不可能包含在這個短語中。盡管如此，用一個次或短語來間接表達信息需求，希望網(wǎng)頁中含有該詞或該短語中的詞，依然是主流的搜索引擎查詢模式。

78、這不僅是因為他的確代表了大多數(shù)的情況，還因為它比較容易實現(xiàn)。這樣，一般來講，系統(tǒng)面對的是查詢短語。一般地，用q0表示用戶提交的原始查詢，例如，q0 =“網(wǎng)絡與分布式系統(tǒng)實驗室”。它首先需要被“切詞”（segment）或稱“分詞”，即把它分成一個詞的序列。如上例，則為“網(wǎng)絡 與 分布式 系統(tǒng) 實驗室”（注意，不同的分詞軟件可能得出不同的結果）。然后需要刪除那些沒有查詢意義或者幾乎在每篇文檔中都會出現(xiàn)的詞（例如“的”），在本例中即為“與”。

79、最后形成一個用于參加匹配的查詢詞表，q = {t1, t2, …, tm}，在本例中就是q = {網(wǎng)絡，分布式，系統(tǒng)，實驗室}。倒排文件就是用詞來作為索引的一個數(shù)據(jù)結構，</p><p>　　2.4.2 結果排序</p><p>　　就目前的技術情況看，列表是最常見的形式（但人們也在探求新的形式，如Vivisimo 引擎將結果頁面以類別的形式呈現(xiàn)）。給定一個查詢結果集合，R={r1, r2

80、, …, rn}，所謂列表，就是按照某種評價方式，確定出R中元素的一個順序，讓這些元素以這種順序呈現(xiàn)出來?；\統(tǒng)地講，ri和q的相關性（relevance）是形成這種順序的基本因素。但是，有效地定義相關性本身是很困難的，從原理上講它不僅和查詢詞有關，而且還和用戶的背景，以及用戶的查詢歷史有關。不同需求的用戶可能輸入同一個查詢，同一個用戶在不同的時間輸入的相同的查詢可能是針對不同的信息需求。為了形成一個合適的順序，在搜索引擎出現(xiàn)的早期人們采

81、用了傳統(tǒng)信息檢索領域很成熟的基于詞匯出現(xiàn)頻度的方法。大致上講就是一篇文檔中包含的查詢（q）中的那些詞越多，則該文檔就應該排在越前面；再精細一些的考慮則是若一個詞在越多的文檔中有出現(xiàn)，則該詞用于區(qū)分文檔相關性的作用就越小。這樣一種思路不僅有一定直覺上的道理，而且在倒排文件數(shù)據(jù)結構上很容易實現(xiàn)。因為，當通過前述關鍵詞的提取過程，形成一篇文檔的關鍵詞集合，p = {t1, t2, …, tn}的時候，很容</p><p&g

82、t;　　2.4.3 文檔摘要</p><p>　　搜索引擎給出的結果是一個有序的條目列表，每一個條目有三個基本的元素：標題，網(wǎng)址和摘要。其中的摘要需要從網(wǎng)頁正文中生成。一般來講，從一篇文字中生成一個恰當?shù)恼亲匀徽Z言理解領域的一個重要課題，人們已經(jīng)做了多年的工作并取得了一些成果。但相關的技術用到網(wǎng)絡搜索引擎來有兩個基本困難。一是網(wǎng)頁的寫作通常不規(guī)范，文字比較隨意，因此從語言理解的角度難以做好；二是復雜的語言理解

83、算法耗時太多，不適應搜索引擎要高效處理海量網(wǎng)頁信息的需求。據(jù)統(tǒng)計，即使是分詞這一項工作（文本理解的基礎），在高檔微機上每秒鐘也只能完成10篇左右網(wǎng)頁的處理。因此搜索引擎在生成摘要時要簡便許多，基本上可以歸納為兩種方式，一是靜態(tài)方式，即獨立于查詢，按照某種規(guī)則，事先在預處理階段從網(wǎng)頁內容提取出一些文字，例如截取網(wǎng)頁正文的開頭512個字節(jié)（對應256個漢字），或者將每一個段落的第一個句子拼起來，等等。這樣形成的摘要存放在查詢子系統(tǒng)中，一旦相

84、關文檔被選中與查詢項匹配，就讀出返回給用戶。顯然，這種方式對查詢子系統(tǒng)來說是最輕松的，不需要做另外的處理工作。但這種方式的一個最大的缺點是摘要和查詢無關。一篇網(wǎng)頁有可能是多個不同查詢的結果。當用</p><p><b>　　2.5 小結</b></p><p>　　本章主要介紹了搜索引擎的相關理論。以web搜索引擎為主要介紹對象。首先，從Web搜索引擎原理和結構介紹，

85、闡述了搜索引擎三段式的工作原理，以及給出了目前主流搜索引擎實現(xiàn)的整體結構描述。其次分別用三個章節(jié)分別介紹三段式工作流程中涉及到的各個流程的主要工作，以及工作中所采用什么樣的工作策略。</p><p>　　3 Nutch相關框架研究</p><p>　　3.1 Lucene研究</p><p>　　3.1.1 Lucene概述</p><p>

86、　　Lucene是一套用于全文檢索和搜尋的開放源碼程序庫，由Apache軟件基金會支持和提供的，高效的，基于Java的全文檢索庫。它并不是一個完整的應用程序，而是一組代碼庫，并提供了方便實現(xiàn)搜索引擎的API。</p><p>　　Lucene 是一個高效的基于 Java 的全文檢索庫。所以在了解 Lucene 之前要了解一下全文檢索。 那么什么叫做全文檢索呢？ 生活中的數(shù)據(jù)總體分為兩種：結構化數(shù)據(jù)和非結構化數(shù)據(jù)。

87、 </p><p>　　3.1.2 Lucene如何對索引進行搜索</p><p>　　第一步：用戶輸入查詢語句。 </p><p>　　查詢語句同我們普通的語言一樣，也是有一定語法的。 不同的查詢語句有不同的語法，如 SQL語句就有一定的語法。 查詢語句的語法根據(jù)全文搜索引擎的實現(xiàn)而不同。最基本的有比如：AND, OR, NOT 等。 </p>&l

88、t;p>　　舉個例子，用戶輸入語句：lucene AND learned NOT hadoop。 說明用戶想找一個包含 lucene和 learned然而不包括hadoop的文檔。 </p><p>　　第二步：對查詢語句進行詞法分析，語法分析，及語言處理。 </p><p>　　由于查詢語句有語法，因而也要進行語法分析，語法分析及語言處理。 </p><p&g

89、t;　　1. 詞法分析主要用來識別單詞和關鍵字。 如果在詞法分析中發(fā)現(xiàn)不合法的關鍵字，則會出現(xiàn)錯誤。</p><p>　　2. 語法分析主要是根據(jù)查詢語句的語法規(guī)則來形成一棵語 。 </p><p>　　如果發(fā)現(xiàn)查詢語句不滿足語法規(guī)則，則會報錯。</p><p>　　3. 語言處理同索引過程中的語言處理幾乎相同 。 </p><p>　

90、　經(jīng)過第二步，得到一棵經(jīng)過語言處理的語法樹。</p><p>　　第三步：搜索索引，得到符合語法樹的文檔。 </p><p>　　第四步：根據(jù)得到的文檔和查詢語句的相關性，對結果進行排序。</p><p>　　3.1.3 Lucene增刪改索引的API</p><p>　　Lucene可對email,網(wǎng)頁,文本資料,doc,pdf之類的文檔進

91、行索引建立,在建立索引的時候可為以后的排序做些處理。表 4-1給出了通過內存建立文本信息索引的一個例子。</p><p>　　.表 4-1建立索引</p><p>　　Lucene查詢服務是根據(jù)通過的關鍵字，從已建立的索引中查詢符合分詞規(guī)則的信息。表 3-2給出了通過檢索索引的一個例子。</p><p><b>　　表 3-2查詢服務</b>&

92、lt;/p><p>　　Lucene索引更新是根據(jù)提供的新信息，刪除，回復，修改索引的過程。表 3-3，表 3-4給出了刪除、恢復、強制刪除索引的一個例子。</p><p>　　表 3-3刪除、恢復、強制刪除索引</p><p>　　表 3-4強制合并索引</p><p>　　3.2 Nutch研究</p><p>　　3

93、.2.1 Nutch概述</p><p>　　Apache Nutch是一個用Java編寫的開源網(wǎng)絡爬蟲。通過它，就能夠自動地找到網(wǎng)頁中的超鏈接，從而極大地減輕了維護工作的負擔，例如檢查那些已經(jīng)斷開了的鏈接，或是對所有已經(jīng)訪問過的網(wǎng)頁創(chuàng)建一個副本以便用于搜索。接下來就是Apache Solr所要做的。Solr是一個開源的全文搜索框架，通過Solr能夠搜索Nutch已經(jīng)訪問過的網(wǎng)頁。Apache Nutch對于So

94、lr已經(jīng)支持得很好，這大大簡化了Nutch與Solr的整合。這也消除了過去依賴于Apache Tomcat來運行老的Nutch網(wǎng)絡應用以及依賴于Apache Lucene來進行索引的麻煩。</p><p>　　3.2.2 研究Nutch的原因</p><p>　　可能有的朋友會有疑問,已經(jīng)有google,有百度,為何還需要建立自己的搜索引擎呢？這里我列出3點原因： </p>

95、<p>　　(1) 透明度：nutch是開放源代碼的，因此任何人都可以查看他的排序算法是如何工作的。商業(yè)的搜索引擎排序算法都是保密的，無法知道為什么搜索出來的排序結果是如何算出來的。更進一步，一些搜索引擎允許競價排名，比如百度，這樣的索引結果并不是和站點內容相關的。因此 nutch 對學術搜索和政府類站點的搜索來說，是個好選擇，因為一個公平的排序結果是非常重要的。</p><p>　　(2) 對搜索引擎

96、的理解：我們并沒有google的源代碼，因此學習搜索引擎Nutch是個不錯的選擇。了解一個大型分布式的搜索引擎如何工作是一件讓人很受益的事情。在寫Nutch的過程中，從學院派和工業(yè)派借鑒了很多知識：比如，Nutch的核心部分目前已經(jīng)被重新用 Map Reduce 實現(xiàn)了。Map Reduce 是一個分布式的處理模型，最先是從 Google 實驗室提出來的。并且 Nutch 也吸引了很多研究者，他們非常樂于嘗試新的搜索算法，因為對Nutc

97、h 來說，這是非常容易實現(xiàn)擴展的。</p><p>　　(3) 擴展性：你是不是不喜歡其他的搜索引擎展現(xiàn)結果的方式呢？那就用 Nutch 寫你自己的搜索引擎吧。 Nutch 是非常靈活的：他可以被很好的客戶訂制并集成到你的應用程序中，使用Nutch 的插件機制，Nutch 可以作為一個搜索不同信息載體的搜索平臺。當然，最簡單的就是集成Nutch到你的站點，為你的用戶提供搜索服務。</p><p

98、>　　3.2.3 研究Nutch的目標</p><p>　　nutch致力于讓每個人能很容易, 同時花費很少就可以配置世界一流的Web搜索引擎. 為了完成這一宏偉的目標, nutch必須能夠做到: </p><p>　　? 每個月取幾十億網(wǎng)頁 </p><p>　　? 為這些網(wǎng)頁維護一個索引 </p><p>　　? 對索引文件進行每秒

99、上千次的搜索 </p><p>　　? 提供高質量的搜索結果 </p><p>　　? 以最小的成本運作 </p><p>　　3.2.4 Nutch和 Lucene比較 </p><p>　　簡單的說，Lucene 不是完整的應用程序，而是一個用于實現(xiàn)全文檢索的軟件庫。</p><p>　　Nutch 是一個應用程

100、序，可以以 Lucene 為基礎實現(xiàn)搜索引擎應用。</p><p>　　Lucene為 Nutch 提供了文本索引和搜索的API。一個常見的問題是；我應該使用Lucene還是Nutch？最簡單的回答是：如果你不需要抓取數(shù)據(jù)的話，應該使用Lucene。常見的應用場合是：你有數(shù)據(jù)源，需要為這些數(shù)據(jù)提供一個搜索頁面。在這種情況下，最好的方式是直接從數(shù)據(jù)庫中取出數(shù)據(jù)并用Lucene API建立索引。 </p>

101、<p>　　3.2.5 Nutch常用命令</p><p>　　1. 抓取命令crawl，輸入bin/nutch crawl，顯示crawl命令參數(shù)選項。</p><p>　　[root@bogon local]# bin/nutch crawl</p><p>　　Usage: Crawl <urlDir> -solr <solrU

102、RL> [-dir d] [-threads n] [-depth i] [-topN N]</p><p>　　抓取www.mop.com網(wǎng)站，將抓取內容存放在www.mop.com目錄下，線程數(shù)50，抓取深度為5，抓取廣度為50.</p><p>　　[root@bogon /]# cd /install/apache-nutch-1.6/runtime/local/</p

103、><p>　　[root@bogon local]# bin/nutch crawl urls -dir www.mop.com -depth 5 -topN 100 -threads 50</p><p>　　solrUrl is not set, indexing will be skipped...</p><p>　　crawl started in: www.

104、mop.com</p><p>　　rootUrlDir = urls</p><p>　　threads = 50</p><p><b>　　depth = 5</b></p><p>　　solrUrl=null</p><p>　　topN = 100</p><p&g

105、t;　　Injector: starting at 2013-05-21 19:38:00</p><p>　　Injector: crawlDb: www.mop.com/crawldb</p><p>　　Injector: urlDir: urls</p><p>　　Injector: Converting injected urls to crawl db

106、 entries.</p><p><b>　　…</b></p><p><b>　　圖3-1 抓取過程</b></p><p>　　2. 數(shù)據(jù)庫查看命令readdb, 輸入bin/nutch readdb，顯示readdb命令參數(shù)選項。</p><p>　　[root@bogon local]#

107、 bin/nutch readdb</p><p>　　Usage: CrawlDbReader <crawldb> (-stats | -dump <out_dir> | -topN <nnnn> <out_dir> [<min>] | -url <url>)</p><p>　　<crawldb>di

108、rectory name where crawldb is located</p><p>　　-stats [-sort] print overall statistics to System.out</p><p>　　[-sort]list status sorted by host</p><p>　　-dump <out_dir> [-fo

109、rmat normal|csv|crawldb]dump the whole db to a text file in <out_dir></p><p>　　[-format csv]dump in Csv format</p><p>　　[-format normal]dump in standard format (default option)</p>

110、;<p>　　[-format crawldb]dump as CrawlDB</p><p>　　[-regex <expr>]filter records with expression</p><p>　　[-status <status>]filter records by CrawlDatum status</p><

111、;p>　　-url <url>print information on <url> to System.out</p><p>　　-topN <nnnn> <out_dir> [<min>]dump top <nnnn> urls sorted by score to <out_dir></p><

112、p>　　[<min>]skip records with scores below this value.</p><p>　　This can significantly improve performance.</p><p>　　下面給出-stats的統(tǒng)計信息。</p><p>　　輸入：[root@bogon local]# bin/nu

113、tch readdb www.mop.com/crawldb/ -stats</p><p>　　圖3-2 讀取連接數(shù)據(jù)庫信息</p><p>　　通過截圖信息，可以發(fā)現(xiàn)，剛才抓取的貓撲網(wǎng)，一共獲得URL2687個，最小分值0.0，最大分值1.012，平均分值8.7420916E-4，為抓取內容的URL2602個。</p><p>　　3. segment信息查看命

114、令readseg，輸入bin/nutch readseg，顯示readseg命令參數(shù)選項。</p><p>　　[root@bogon local]# bin/nutch readseg</p><p>　　Usage: SegmentReader (-dump ... | -list ... | -get ...) [general options]</p><p&g

115、t;　　* General options:</p><p>　　-nocontentignore content directory</p><p>　　-nofetchignore crawl_fetch directory</p><p>　　-nogenerateignore crawl_generate directory</p>&l

116、t;p>　　-noparseignore crawl_parse directory</p><p>　　-noparsedataignore parse_data directory</p><p>　　-noparsetextignore parse_text directory</p><p>　　* SegmentReader -dump <

117、;segment_dir> <output> [general options]</p><p>　　Dumps content of a <segment_dir> as a text file to <output>.</p><p>　　<segment_dir>name of the segment directory.<

118、;/p><p>　　<output>name of the (non-existent) output directory.</p><p>　　* SegmentReader -list (<segment_dir1> ... | -dir <segments>) [general options]</p><p>　　List