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