全文搜索引擎的設計與實現-畢業論文(編輯修改稿)

　

【文章內容簡介】 某網頁的超鏈接 得到其他網頁的地址，從而可以進一步的進行網頁收集；圖的遍歷分為廣度優先和深度優先兩種方法，網頁的收集過程也是如此。綜上，Spider 收集網頁的過程如下：從初始 URL 集合獲得目標網頁地址，通過網絡連接接收網頁數據，將獲得的網頁數據添加到網頁庫中并且分析該網頁中的其他 URL 鏈接，放入未訪問 URL 集合中用于網頁收集。下圖表示了這個過程：圖 23 Spider 工作流程 爬蟲的抓取策略爬蟲的工作策略一般分為累積式抓取（cumulative crawling）和增量式抓取（incremental crawing）兩種。 江漢大學本科畢業論文（設計）6累積式抓取是指從某一個時間點開始，通過遍歷的方式抓取系統所能允許存儲和處理的所有網頁。在理想的軟硬件環境下，經過足夠的運行時間，積累是抓取策略可以保證抓取到相當規模的網頁集合。但由于 Web 數據的動態特性，集合中的網頁的抓取時間點是不同的，頁面被更新的情況也不同，因此累積式抓取到的網頁集合事實上并無法與真實環境中的網絡數據保持一致。與累積式抓取不同，增量式抓取是指在具有一定量規模的網頁集合的基礎上，采用更新數據的方式選取已有集合中的過時頁面進行抓取，以保證所抓取的數據與真實網絡數據足夠接近。進行增量式抓取的前提是，系統已經抓取了足夠數量的網絡頁面，并具有這項頁面被抓取的時間信息。面對實際應用環境的網絡蜘蛛設計中，通常既包含累積式抓取，也包括增量式抓取的策略。累積式抓取一般用戶數據集合的整體建立或大規模更新階段；而增量式抓取則主要針對數據集合的日常維護和及時更新。 鏈接數據庫的建立初始 URL 的建立有兩種方式：超鏈接和站長提交。超鏈接：爬蟲會根據種子地址（可能是最先提交給爬蟲的 URL 集合）抓取頁面。站長提交：在實際運行中，爬蟲不可能抓取所有的站點，為此，網站站長可以向搜索引擎進行提交，要求收錄，搜索引擎經過核查后，便將該網站加入到 URL 集合中，進行抓取。 鏈接數據庫的更新鏈接的注入：抓取程序會根據預先提供的 URL 集合進行標準化，根據設定的正則檢驗來過濾 URL，將這些符合標準的 URL 放入到 map 中，并在構造 map 過程中給 URL 初始化得分，分數可以影響 URL 對應主機的搜索排序和采集優先級。接著會判斷 URL 在抓取數據庫中是否存在，如果存在，刪除舊的，更新新的。如果不存在，將該 URL 的狀態標記為未采集過。URL 生成器：從抓取回來的網頁中，將符合條件的 URL 提出出來，檢測 URL 是否在有效更新時間里面，并將 URL 載入相應的任務組，計算 URL 的 hash 值，搜集 URL，直至達到規定的廣度。 江漢大學本科畢業論文（設計）7 網頁預處理網頁預處理的主要目標是將原始網頁通過一步步的數據處理變成可方便搜索的數據形式。預處理模塊的整體結構如下： 圖 24 預處理模塊的整體結構通過爬蟲的收集，保存下來的網頁信息具有較好的信息存儲格式，但是還是有一個缺點，就是不能按照網頁 URL 直接定位到所指向的網頁。所以，需要先建立網頁的索引，如此通過索引，這樣可以很方便的從原始網頁庫中獲得某個 URL 對應的頁面信息。之后，處理網頁數據，對于一個網頁，首先需要提取其網頁正文信息，其次對正文信息進行分詞，之后再根據分詞的情況建立索引和倒排索引，這樣，網頁的預處理也全部完成。 建立索引頁面庫索引的主要過程： 江漢大學本科畢業論文（設計）8圖 25 索引的主要過程索引過程可分為三個主要的操作階段：將數據轉換成文本分析文本將分析過的文本保存到數據庫中轉換成文本。在索引數據之前，首先必須將數據轉換成純文本字符流。但是，在現實世界中，信息多以富媒體文檔格式呈現：PDF,WORD,EXCEL,HTML,XML 等。為此需要使用文檔解析器，將富媒體轉換成純文字字符流。分析文本。在對數據進行索引錢，還必須進行預處理，對數據進行分析是之更加適合被索引。分析數據時，現將文本數據切分成一些大塊或者詞匯單元，然后對它們執行一些可選的操作，例如：在索引之前將這些詞匯單元轉換成小寫，使得搜索對大小寫不敏感；具有代表性的是要從輸入中去掉一些使用很頻繁但卻沒有實際意義的詞，比如英文文本中的一些停用詞（a、an、the、in、on 等）。同樣的，也需要分析輸入的詞匯單元，一遍從詞語中去掉一些不必要的字母以找到他們的詞干。這一處理過程稱為分析。將分析后的數據寫入索引。對輸入數據分析處理完成后，就可以將結果寫入索引文件中。結果一般包括網頁標題，正文，所屬住地址，主機，內容摘要，時間戳，當前 URL 地址等，并更具具體需要建立索引和存儲。 江漢大學本科畢業論文（設計）9 分詞中文分詞是指將一個漢字序列切分成一個一個單獨的詞，從而達到計算機可以自動識別的效果。中文分詞主要有三種方法：第一種基于字符串匹配，第二種基于語義理解，第三種基于統計。由于第二和第三種的實現需要大量的數據來支持，一般采用的是基于字符串匹配的方法。基于字符串匹配的方法又叫做機械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長度優先匹配的情況，可以分為最大（最長）匹配和最小（最短）匹配。常用的幾種機械分詞方法如下：正向減字最大匹配法（由左到右的方向）；逆向減字最大匹配法（由右到左的方向）；最少切分（使每一句中切出的詞數最小）；雙向最大減字匹配法（進行由左到右、由右到左兩次掃描）；采用其中的正向最大匹配法。算法描述如下：輸入值為一個中文語句 S，以及最大匹配詞 n取 S 中前 n 個字，根據詞典對其進行匹配，若匹配成功，轉 3，否則轉 2；n = n – 1：如果 n 為 1，轉 3；否則轉 1；將 S 中的前 n 個字作為分詞結果的一部分，S 除去前 n 個字，若 S 為空，轉 4；否則，轉 1；算法結束。需要說明的是，在第三步的起始，n 如果不為 1，則意味著有匹配到的詞；而如果 n 為 1，默認 1 個字是應該進入分詞結果的，所以第三步可以將前 n 個字作為一個詞而分割開來。還有需要注意的是對于停用詞的過濾，停用詞即漢語中“的，了，和，么”等字詞，在搜索引擎中是忽略的，所以對于分詞后的結果，需要在用停用詞列表進行一下停用詞過濾。您也許有疑問，如何獲得分詞字典或者是停用詞字典。停用詞字典比較好辦，由于中文停用詞數量有限，可以從網上獲得停用詞列表，從而自己建一個停用詞字典；然而對于分詞字典，雖然網上有許多知名的漢字分詞軟件，但是很少有分詞的字典提供。在程序使用過程中，分詞字典可以放入一個集合中，這樣就可以比較方便的進行比對工作。 江漢大學本科畢業論文（設計）10分詞的結果對于搜索的精準性有著至關重要的影響，好的分詞策略經常是由若干個簡單算法拼接而成的，所以您也可以試著實現雙向最大減字匹配法來提高分詞的準確率。而如果遇到歧義詞組，可以通過字典中附帶的詞頻來決定哪種分詞的結果更好。 倒排索引倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔索引系統中最常用的數據結構。有兩種不同的反向索引形式：一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創建。下面將以圖示和實例的方式分別說明正向索引和倒排索引。 圖 26 正向索引 江漢大學本科畢業論文（設計）11圖 27 倒排索引 以英文為例，下面是要被索引的文本：it is what it iswhat is itit is a banana這樣就能得到下面的反向文件索引： a: {2} banana: {2} is: {0, 1, 2} it: {0, 1, 2} what: {0, 1}檢索的條件what, is 和 it 將對應這個集合：。對相同的文字，得到后面這些完全反向索引，有文檔數量和當前查詢的單詞結果組成的的成對數據。 同樣，文檔數量和當前查詢的單詞結果都從零開始。所以，banana: {(2, 3)} 就是說 banana在第三個文檔里 ( )，而且在第三個文檔的位置是第四個單詞(地址為 3)。a: {(2, 2)}banana: {(2, 3)}is: {(0, 1), (0, 4), (1, 1), (2, 1)} 江漢大學本科畢業論文（設計）12it: {(0, 0), (0, 3), (1, 2), (2, 0)} what: {(0, 2), (1, 0)}如果執行短語搜索what is it 將得到這個短語的全部單詞各自的結果所在文檔為文檔 0 和文檔 1。但是這個短語檢索的連續的條件僅僅在文檔 1 得到。 查詢服務查詢服務的整體結構如下：圖 28 查詢服務的整體結構 在網頁預處理后，每個元素至少包含如下幾個方面：原始網頁文檔URL 和標題編號所含的重要關鍵詞的集合（以及他們在文檔中出現的位置信息）其他一些指標（例如重要程度，分類代碼等）而系統關鍵詞總體的集合和文檔的編號一起構成了一個倒排文件結構，使得一旦得到一個關鍵詞輸入，系統能迅速給出相關文檔編號的集合輸出。 查詢方式和匹配查詢方式指的是系統允許用戶提交查詢的形式。考慮到各種用戶的不同背景和不 江漢大學本科畢業論文（設計）13同的信息需求不可能有一種普適的方式。一般認為，對于普通網絡用戶來說，最自然的方式就是“要什么就輸入什么”。但這是一種相當模糊的說法。例如用戶輸入“江漢大學”，可能是他想了解江漢大學目前的招生狀況，可能需要找到江漢大學教務系統的網址，可能需要了解大家對江漢大學的評價。這是三種相當不同的需求。在其他一些情況下，用戶可能關心的是間接的信息，例如“江漢大學錄取分數線”，450 分應該是他需要的，但不可能包含在這個短語中。盡管如此，用一個次或短語來間接表達信息需求，希望網頁中含有該詞或該短語中的詞，依然是主流的搜索引擎查詢模式。這不僅是因為他的確代表了大多數的情況，還因為它比較容易實現。這樣，一般來講，系統面對的是查詢短語。一般地，用 q0 表示用戶提交的原始查詢，例如，q0 =“網絡與分布式系統實驗室”。它首先需要被“切詞”（segment）或稱“分詞”，即把它分成一個詞的序列。如上例，則為“網絡 與 分布式 系統 實驗室”（注意，不同的分詞軟件可能得出不同的結果）。然后需要刪除那些沒有查詢意義或者幾乎在每篇文檔中都會出現的詞（例如“的”），在本例中即為“與”。最后形成一個用于參加匹配的查詢詞表，q = {t1, t2, …, tm}，在本例中就是 q = {網絡，分布式，系統，實驗室}。倒排文件就是用詞來作為索引的一個數據結構，顯然，q 中的詞必須是包含在倒排文件詞表中才有意義。有了這樣的 q，它的每一個元素都對應倒排文件中的一個倒排表（文檔編號的集合），記作 L(ti)，它們的交集即為對應查詢的結果文檔集合，從而實現了查詢和文檔的匹配。上述過程的基本假設是：用戶是希望網頁包含所輸入查詢文字的。 結果排序就目前的技術情況看，列表是最常見的形式（但人們也在探求新的形式，如Vivisimo 引擎將結果頁面以類別的形式呈現）。給定一個查詢結果集合，R={r1, r2, …, rn}，所謂列表，就是按照某種評價方式，確定出 R 中元素的一個順序，讓這些元素以這種順序呈現出來。籠統地講，ri 和 q 的相關性（relevance）是形成這種順序的基本因素。但是，有效地定義相關性本身是很困難的，從原理上講它不僅和查詢詞有關，而且還和用戶的背景，以及用戶的查詢歷史有關。不同需求的用戶可能輸入同一個查詢，同一個用戶在不同的時間輸入的相同的查詢可能是針對不同的信息需求。為了形成一個合適的順序，在搜索引擎出現的早期人們采用了傳統信息檢索領域很成熟 江漢大學本科畢業論文（設計）14的基于詞匯出現頻度的方法。大致上講就是一篇文檔中包含的查詢（q）中的那些詞越多，則該文檔就應該排在越前面；再精細一些的考慮則是若一個詞在越多的文檔中有出現，則該詞用于區分文檔相關性的作用就越小。這樣一種思路不僅有一定直覺上的道理，而且在倒排文件數據結構上很容易實現。因為，當通過前述關鍵詞的提取過程，形成一篇文檔的關鍵詞集合，p = {t1, t2, …, tn}的時候，很容易同時得到每一個ti 在該文檔中出現的次數，即詞頻，而倒排文件中每個倒排表的長度則對應著一個詞所涉及的文檔的篇數，即文檔頻率。然而，由于網頁編寫的自發性、隨意性較強，僅僅針對詞的出現來決定文檔的順序，