【文章內(nèi)容簡介】 。 網(wǎng)頁 收集 全文檢索 是工作在某個數(shù)據(jù)集合上的程序，他需要事先由頁面抓取程序，在全網(wǎng)中抓取海量網(wǎng)頁，這個抓取程序也叫網(wǎng)絡爬蟲或 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)絡連接接收網(wǎng)頁數(shù)據(jù)，將獲得的網(wǎng)頁數(shù)據(jù)添加到網(wǎng)頁庫中并且分析該網(wǎng)頁中的其他 URL 鏈接，放入未訪問 URL 集合 中 用于網(wǎng)頁收集。下圖表示了這個過程： 圖 23 Spider 工作流程 爬蟲的抓取策略 爬蟲的工作策略一般分為累積式抓?。?cumulative crawling）和增量式抓取（ incremental crawing）兩種。 累積式抓取是指從某一個時間點開始，通過遍歷的方 式抓取系統(tǒng)所能允許存儲和處理的所有網(wǎng)頁。在理想的軟硬件環(huán)境下，經(jīng)過足夠的運行時間，積累是抓取策略可以保 江漢大 學本科畢業(yè)論文（設計） 6 證抓取到相當規(guī)模的網(wǎng)頁集合。但由于 Web數(shù)據(jù)的動態(tài)特性，集合中的網(wǎng)頁的抓取時間點是不同的，頁面被更新的情況也不同，因此累積式抓取到的網(wǎng)頁集合事實上并無法與真實環(huán)境中的網(wǎng)絡數(shù)據(jù)保持一致。 與累積式抓取不同，增量式抓取是指在具有一定量規(guī)模的網(wǎng)頁集合的基礎上，采用更新數(shù)據(jù)的方式選取已有集合中的過時頁面進行抓取，以保證所抓取的數(shù)據(jù)與真實網(wǎng)絡數(shù)據(jù)足夠接近。進行增量式抓取的前提是，系統(tǒng)已經(jīng)抓取了足夠數(shù)量的網(wǎng)絡頁面，并具有這項頁面被抓取的時間信息。 面對實際應用環(huán)境的網(wǎng)絡蜘蛛設計中，通常既包含累積式抓取，也包括增量式抓取的策略。累積式抓取一般用戶數(shù)據(jù)集合的整體建立或大規(guī)模更新階段；而增量式抓取則主要針對數(shù)據(jù)集合的日常維護和及時更新。 鏈接數(shù)據(jù)庫的建立 初始 URL 的建立有兩種方式：超鏈接和站長提交。 超鏈接：爬蟲會根據(jù)種子地址（可能是最先提交給爬蟲的 URL 集合）抓取頁面。 站長提交：在實際運行中，爬蟲不可能抓取所有的站點，為此，網(wǎng)站站長可以向搜索引擎進行提交，要求收錄， 搜索 引擎 經(jīng)過核查后，便將該網(wǎng)站加入到 URL 集 合中，進行抓取。 鏈接數(shù)據(jù)庫的更新 鏈接的注入：抓取程序會根據(jù)預先提供的 URL 集合進行標準化，根據(jù)設定的正則檢驗來過濾 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ī)定的廣度。 網(wǎng)頁預處理 網(wǎng)頁預 處理 的主要目標是 將 原始網(wǎng)頁通過一步步的數(shù)據(jù) 處 理變成可方便搜索的數(shù) 江漢大 學本科畢業(yè)論文（設計） 7 據(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è)論文（設計） 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è)論文（設計） 9 分詞 中文分詞是指將一個漢字序列切分成一個一個單獨的詞，從而達到計算機可以自動識別的效果。中文分詞主要有三種方法：第一種基于字符串匹配，第二種基于語義理解，第三種 基于統(tǒng)計。由于第二和第三種的實現(xiàn)需要大量的數(shù)據(jù)來支持， 一般 采用的是基于字符串匹配的方法。 基于字符串匹配的方法又叫做機械分詞方法，它是按照一定的策略將待分析的漢字串與一個 “ 充分大的 ” 機器詞典中的詞條進行配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長度優(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é)果， 需要在用停用詞列表進行一下停用詞過濾。 您也許有疑問，如何獲得分詞字典或者是停用詞字典。停用詞字典比較好辦，由于中文停用詞數(shù)量有限，可以從網(wǎng)上獲得停用詞列表，從而自己建一個停用詞字典；然而對于分詞字典，雖然網(wǎng)上有許多知名的漢字分詞軟件，但是很少有分詞的字典提供。在程序使用過程中，分詞字典可以放入一 個集合中，這樣就可以比較方便的進行比對工作。 分詞的結(jié)果對于搜索的精準性有著至關(guān)重要的影響，好的分詞策略經(jīng)常是由若干個 江漢大 學本科畢業(yè)論文（設計） 10 簡單算法拼接而成的，所以您也可以試著實現(xiàn)雙向最大減字匹配法來提高分詞的準確率。而如果遇到歧義詞組，可以通過字典中附帶的詞頻來決定哪種分詞的結(jié)果更好。 倒排索引 倒排索引（英語： Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種 索引 方法，被用來 存儲在全文搜索 下某個單詞在一個文檔或者一組文檔中的 存儲位置的映射 。它是 文檔索引系統(tǒng) 中最常用的 數(shù)據(jù)結(jié)構(gòu) 。 有兩 種不同的反向索引形式： 一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的 列表 。 一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。 后者的形式提供了更多的 兼容性 （ 比如短語搜索 ），但是需要更多的時間和空間來創(chuàng)建。 下面將以圖示和實例的方式分別說明正向索引和倒排索引。 圖 26 正向索引 江漢大 學本科畢業(yè)論文（設計） 11 圖 27 倒排索引 以 英文 為例，下面是要被索引的文本： it is what it is what is it it is a banana 這樣 就能得到下面的反向文件索引： a: {2} banana: {2} is: {0, 1, 2} it: {0, 1, 2} what: {0, 1} 檢索的條件 what, is 和 it 將 對 應 這 個 集合 ：。 對相同的文字， 得到后面這些完全反向索引，有 文檔 數(shù)量和當前查詢的單詞結(jié)果組成的的成對 數(shù)據(jù) 。 同樣，文檔數(shù)量和當前查詢的單詞結(jié)果都從零開始。所以， banana: {(2, 3)} 就是說 banana在第三個文檔里 ( )，而且在第三個文檔的位置是第四個單詞 (地址為 3)。 a: {(2, 2)} banana: {(2, 3)} is: {(0, 1), (0, 4), (1, 1), (2, 1)} 江漢大 學本科畢業(yè)論文（設計） 12 it: {(0, 0), (0, 3), (1, 2), (2, 0)} what: {(0, 2), (1, 0)} 如果 執(zhí)行短語搜索 what is it 將 得到這個短語的全部單詞各自的結(jié)果所在文檔為文檔 0 和文檔 1。但是這個短語檢索的連續(xù)的條件僅僅在文檔 1得到。 查詢服務 查詢服務的整體結(jié)構(gòu)如下： 圖 28 查詢服務的整體結(jié)構(gòu) 在網(wǎng)頁預處理后，每個元素至少包含如下幾個方面： 原始網(wǎng)頁文檔 URL 和標題 編號 所含的重要關(guān)鍵詞的集合（以及他們在文檔中出現(xiàn)的位置信息） 其他一些指標（例如重要程度，分類代碼等） 而系統(tǒng)關(guān)鍵詞總體的集合和文檔的編號一起構(gòu)成了 一個倒排文件結(jié)構(gòu)，使得一旦得到一個關(guān)鍵詞輸入，系統(tǒng)能迅速給出相關(guān)文檔編號的集合輸出。 查詢方式和匹配 查詢方式指的是系統(tǒng)允許用戶提交查詢的形式。考慮到各種用戶的不同背景和不同 江漢大 學本科畢業(yè)論文（設計） 13 的信息需求不可能有一種普適的方式。 一般認為，對于普通網(wǎng)絡用戶來說，最自然的方式就是 “ 要什么就輸入什么 ” 。但這是一種相當模糊的說法。 例如用戶輸入“江漢大學”，可能是他想了解江漢大學目前的招生狀況，可能需要找到江漢大學教務系統(tǒng)的網(wǎng)址，可能需要了解大家對江漢大學的評價。這是三種相當不同的需求。在其他一些情況下，用戶可能關(guān)心 的是間接的信息，例如“江漢大學錄取分數(shù)線”， 450 分應該是他需要的，但不可能包含在這個短語中。盡管如此，用一個次或短語來間接表達信息需求，希望網(wǎng)頁中含有該詞或該短語中的詞，依然是主流的搜索引擎查詢模式。這不僅是因為他的確代表了大多數(shù)的情況，還因為它比較容易實現(xiàn)。這樣，一般來講，系統(tǒng)面對的是查詢短語。一般地，用 q0 表示用戶提交的原始查詢，例如，q0 =“ 網(wǎng)絡與分布式系統(tǒng)實驗室 ” 。它首先需要被 “ 切詞 ” （ segment）或稱 “ 分詞 ” ，即把它分成一個詞的序列。如上例，則為 “ 網(wǎng)絡 與 分布式 系統(tǒng) 實驗室 ” （注意，不同的分詞軟件可能得出不同的結(jié)果）。然后需要刪除那些沒有查詢意義或者幾乎在每篇文檔中都會出現(xiàn)的詞（例如 “ 的 ” ），在本例中即為 “ 與 ” 。最后形成一個用于參加匹配的查詢詞表， q = {t1, t2, ?, tm} ，在本例中就是 q = {網(wǎng)絡，分布式，系統(tǒng)，實驗室 }。倒排文件就是用詞來作為索引的一個數(shù)據(jù)結(jié)構(gòu)，顯然， q 中的詞必須是包含在倒排文件詞表中才有意義。有了這樣的 q，它的每一個元素都對應倒排文件中的一個倒排表（文檔編號的集合），記作 L(ti)，它們的交集即為對應查詢的結(jié)果文檔集合，從而實現(xiàn)了查詢和文檔的匹配。上述 過程的基本假設是：用戶是希望網(wǎng)頁包含所輸入查詢文字的。 結(jié)果排序 就目前的技術(shù)情況看，列表是最常見的形式（但人們也在探求新的形式，如 Vivisimo 引擎將結(jié)果頁面以類別的形式呈現(xiàn)）。給定一個查詢結(jié)果集合， R={r1, r2, ?, r