久久不射2019中文字幕,国内久久婷婷综合,欧美国产成人精品

一個 Java 搜索引擎的實現，第 2 部分: 網頁預處理

Posted on 2011-04-16 20:36 Kevin_Zhang 閱讀(737) 評論(0) 編輯收藏引用所屬分類: 搜索引擎

在上一部分中，您了解到如何編寫一個 spider 程序來進行網頁的爬取，作為 spider 的爬取結果，我們獲得了一個按照一定格式存儲的原始網頁庫，原始網頁庫也是我們第二部分網頁預處理的數據基礎。網頁預處理的主要目標是將原始網頁通過一步步的數據處理變成可方便搜索的數據形式。下面就讓我們逐步介紹網頁預處理的設計和實現。

預處理模塊的整體結構

預處理模塊的整體結構如下：

圖 1. 預處理模塊的整體結構

通過 spider 的收集，保存下來的網頁信息具有較好的信息存儲格式，但是還是有一個缺點，就是不能按照網頁 URL 直接定位到所指向的網頁。所以，在第一個流程中，需要先建立網頁的索引，如此通過索引，我們可以很方便的從原始網頁庫中獲得某個 URL 對應的頁面信息。之后，我們處理網頁數據，對于一個網頁，首先需要提取其網頁正文信息，其次對正文信息進行分詞，之后再根據分詞的情況建立索引和倒排索引，這樣，網頁的預處理也全部完成。可能讀者對于其中的某些專業術語會有一些不明白之處，在后續詳述各個流程的時候會給出相應的圖或者例子來幫助大家理解。

回頁首

建立索引網頁庫

原始網頁庫是按照格式存儲的，這對于網頁的索引建立提供了方便，下圖給出了一條網頁信息記錄：

清單 1. 原始網頁庫中的一條網頁記錄

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx // 之前的記錄

version:1.0 // 記錄頭部

url:http://ast.nlsde.buaa.edu.cn/

date:Mon Apr 05 14:22:53 CST 2010

IP:218.241.236.72

length:3981

<!DOCTYPE …… // 記錄數據部分

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx // 之后的記錄

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

我們采用“網頁庫名—偏移”的信息對來定位庫中的某條網頁記錄。由于數據量比較大，這些索引網頁信息需要一種保存的方法，dySE 使用數據庫來保存這些信息。數據庫們采用 mysql，配合 SQL-Front 軟件可以輕松進行圖形界面的操作。我們用一個表來記錄這些信息，表的內容如下：url、content、offset、raws。URL 是某條記錄對應的 URL，因為索引數據庫建立之后，我們是通過 URL 來確定需要的網頁的；raws 和 offset 分別表示網頁庫名和偏移值，這兩個屬性唯一確定了某條記錄，content 是網頁內容的摘要，網頁的數據量一般較大，把網頁的全部內容放入數據庫中顯得不是很實際，所以我們將網頁內容的 MD5 摘要放入到 content 屬性中，該屬性相當于一個校驗碼，在實際運用中，當我們根據 URL 獲得某個網頁信息是，可以將獲得的網頁做 MD5 摘要然后與 content 中的值做一個匹配，如果一樣則網頁獲取成功，如果不一樣，則說明網頁獲取出現問題。

這里簡單介紹一下 mySql 的安裝以及與 Java 的連接：

安裝 mySql，最好需要三個組件，mySql，mySql-front，mysql-connector-java-5.1.7-bin.jar，分別可以在網絡中下載。注意：安裝 mySql 與 mySql-front 的時候要版本對應，MySql5.0 + MySql-Front3.2 和 MySql5.1 + MySql-Front4.1，這個組合是不能亂的，可以根據相應的版本號來下載，否則會爆“‘ 10.000000 ’ ist kein gUltiger Integerwert ”的錯誤。

導入 mysql-connector-java-5.1.7-bin.jar 到 eclipse 的項目中，打開 eclipse，右鍵點需要導入 jar 包的項目名，選屬性（properties)，再選 java 構建路徑（java Build Path)，后在右側點 (libraries)，選 add external JARs，之后選擇你要導入的 jar 包確定。

接著就可以用代碼來測試與 mySql 的連接了，代碼見本文附帶的 testMySql.java 程序，這里限于篇幅就不在贅述。

對于數據庫的操作，我們最好進行一定的封裝，以提供統一的數據庫操作支持，而不需要在其他的類中顯示的進行數據庫連接操作，而且這樣也就不需要建立大量的數據庫連接從而造成資源的浪費，代碼詳見 DBConnection.java。主要提供的操作是：建立連接、執行 SQL 語句、返回操作結果。

介紹了數據庫的相關操作時候，現在我們可以來完成網頁索引庫的建立過程。這里要說明的是，第一條記錄的偏移是 0，所以在當前記錄 record 處理之前，該記錄的偏移是已經計算出來的，處理 record 的意義在于獲得下一個記錄在網頁庫中的偏移。假設當前 record 的偏移為 offset，定位于頭部的第一條屬性之前，我們通過讀取記錄的頭部和記錄的數據部分來得到該記錄的長度 length，從而，offset+length 即為下一條記錄的偏移值。讀取頭部和讀取記錄都是通過數據間的空行來標識的，其偽代碼如下：

清單 2. 索引網頁庫建立

For each record in Raws do

begin

讀取 record 的頭部和數據，從頭部中抽取 URL；

計算頭部和數據的長度，加到當前偏移值上得到新的偏移；

從 record 中數據中計算其 MD5 摘要值；

將數據插入數據庫中，包括：URL、偏移、數據 MD5 摘要、Raws；

end；

您可能會對 MD5 摘要算法有些疑惑，這是什么？這有什么用？ Message Digest Algorithm MD5（中文名為消息摘要算法第五版）為計算機安全領域廣泛使用的一種散列函數，用以提供消息的完整性保護。MD5 的典型應用是對一段信息 (Message) 產生一個 128 位的二進制信息摘要 (Message-Digest)，即為 32 位 16 進制數字串，以防止被篡改。對于我們來說，比如通過 MD5 計算，某個網頁數據的摘要是 00902914CFE6CD1A959C31C076F49EA8，如果我們任意的改變這個網頁中的數據，通過計算之后，該摘要就會改變，我們可以將信息的 MD5 摘要視作為該信息的指紋信息。所以，存儲該摘要可以驗證之后獲取的網頁信息是否與原始網頁一致。

對 MD5 算法簡要的敘述可以為：MD5 以 512 位分組來處理輸入的信息，且每一分組又被劃分為 16 個 32 位子分組，經過了一系列的處理后，算法的輸出由四個 32 位分組組成，將這四個 32 位分組級聯后將生成一個 128 位散列值。其中“一系列的處理”即為計算流程，MD5 的計算流程比較多，但是不難，同時也不難實現，您可以直接使用網上現有的 java 版本實現或者使用本教程提供的源碼下載中的 MD5 類。對于 MD5，我們知道其功能，能使用就可以，具體的每個步驟的意義不需要深入理解。

回頁首

正文信息抽取

PageGetter

在正文信息抽取之前，我們首先需要一個簡單的工具類，該工具類可以取出數據庫中的內容并且去原始網頁集中獲得網頁信息，dySE 對于該功能的實現在 originalPageGetter.java 中，該類通過 URL 從數據庫中獲得該 URL 對應的網頁數據的所在網頁庫名以及偏移，然后就可以根據偏移來讀取該網頁的數據內容，同樣以原始網頁集中各記錄間的空行作為數據內容的結束標記，讀取內容之后，通過 MD5 計算當前讀取的內容的摘要，校驗是否與之前的摘要一致。對于偏移的使用，BufferedReader 類提供一個 skip(int offset) 的函數，其作用是跳過文檔中，從當前開始計算的 offset 個字符，用這個函數我們就可以定位到我們需要的記錄。

清單 3. 獲取原始網頁庫中內容

public String getContent(String fileName, int offset)

{

String content = "";

try {

FileReader fileReader = new FileReader(fileName);

BufferedReader bfReader = new BufferedReader(fileReader);

bfReader.skip(offset);

readRawHead(bfReader);

content = readRawContent(bfReader);

} catch (Exception e) {e.printStackTrace();}

return content;

}

上述代碼中，省略了 readRawHead 和 readRawContent 的實現，這些都是基本的 I/O 操作，詳見所附源碼。

正文抽取

對于獲得的單個網頁數據，我們就可以進行下一步的處理，首先要做的就是正文內容的抽取，從而剔除網頁中的標簽內容，這一步的操作主要采用正則表達式來完成。我們用正則表達式來匹配 html 的標簽，并且把匹配到的標簽刪除，最后，剩下的內容就是網頁正文。限于篇幅，我們以過濾 script 標簽為示例，其代碼如下 :

清單 4. 標簽過濾

public String html2Text(String inputString) {

String htmlStr = inputString; // 含 html 標簽的字符串

Pattern p_script; Matcher m_script;

try {

String regEx_script = "<script[^>]*?>[\\s\\S]*?</script>";

p_script = Pattern.compile(regEx_script,Pattern.CASE_INSENSITIVE);

m_script = p_script.matcher(htmlStr);

htmlStr = m_script.replaceAll(""); // 過濾 script 標簽

}catch(Exception e) {e.printStackTrace();}

return htmlStr;// 返回文本字符串

}

通過一系列的標簽過濾，我們可以得到網頁的正文內容，就可以用于下一步的分詞了。

回頁首

分詞

中文分詞是指將一個漢字序列切分成一個一個單獨的詞，從而達到計算機可以自動識別的效果。中文分詞主要有三種方法：第一種基于字符串匹配，第二種基于語義理解，第三種基于統計。由于第二和第三種的實現需要大量的數據來支持，所以我們采用的是基于字符串匹配的方法。

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

正向減字最大匹配法（由左到右的方向）；

逆向減字最大匹配法（由右到左的方向）；

最少切分（使每一句中切出的詞數最小）；

雙向最大減字匹配法（進行由左到右、由右到左兩次掃描）；

我們采用其中的正向最大匹配法。算法描述如下：輸入值為一個中文語句 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 個字作為一個詞而分割開來。還有需要注意的是對于停用詞的過濾，停用詞即漢語中“的，了，和，么”等字詞，在搜索引擎中是忽略的，所以對于分詞后的結果，我們需要在用停用詞列表進行一下停用詞過濾。

您也許有疑問，如何獲得分詞字典或者是停用詞字典。停用詞字典比較好辦，由于中文停用詞數量有限，可以從網上獲得停用詞列表，從而自己建一個停用詞字典；然而對于分詞字典，雖然網上有許多知名的漢字分詞軟件，但是很少有分詞的字典提供，這里我們提供一些在 dySE 中使用的分詞字典給您。在程序使用過程中，分詞字典可以放入一個集合中，這樣就可以比較方便的進行比對工作。

分詞的結果對于搜索的精準性有著至關重要的影響，好的分詞策略經常是由若干個簡單算法拼接而成的，所以您也可以試著實現雙向最大減字匹配法來提高分詞的準確率。而如果遇到歧義詞組，可以通過字典中附帶的詞頻來決定哪種分詞的結果更好。

回頁首

倒排索引

這個章節我們為您講解預處理模塊的最后兩個步驟，索引的建立和倒排索引的建立。有了分詞的結果，我們就可以獲得一個正向的索引，即某個網頁以及其對應的分詞結果。如下圖所示：

圖 2. 正向索引

圖 3. 倒排索引

在本文的開頭，我們建立了索引網頁庫，用于通過 URL 可以直接定位到原始網頁庫中該 URL 對應的數據的位置；而現在的正向索引，我們可以通過某個網頁的 URL 得到該網頁的分詞信息。獲得正向索引看似對于我們的即將進行的查詢操作沒有什么實際的幫助，因為查詢服務是通過關鍵詞來獲得網頁信息，而正向索引并不能通過分詞結果反查網頁信息。其實，我們建立正向索引的目的就是通過翻轉的操作建立倒排索引。所謂倒排就是相對于正向索引中網頁——分詞結果的映射方式，采用分詞——對應的網頁這種映射方式。與圖 2 相對應的倒排索引如上圖 3 所示。

接下來我們分析如何從正向索引來得到倒排索引。算法過程如下：

對于網頁 i，獲取其分詞列表 List；

對于 List 中的每個詞組，查看倒排索引中是否含有這個詞組，如果沒有，將這個詞組插入倒排索引的索引項，并將網頁 i 加到其索引值中；如果倒排索引中已經含有這個詞組，直接將網頁 i 加到其索引值中；

如果還有網頁尚未分析，轉 1；否則，結束

建立倒排索引的算法不難實現，主要是其中數據結構的選用，在 dySE 中，正向索引和倒排索引都是采用 HashMap 來存儲，映射中正向索引的鍵是采用網頁 URL 對應的字符串，而倒排索引是采用分詞詞組，映射中的值，前者是一個分詞列表，后者是一個 URL 的字符串列表。這里可以采用一個優化，分別建立兩個表，按照標號存儲分詞列表和 URL 列表，這樣，索引中的值就可以使用整型變量列表來節省空間。

回頁首

初步實驗

到目前為止，雖然我們還沒有正式的查詢輸入界面以及結果返回頁面，但這絲毫不影響我們來對我們的搜索引擎進行初步的實驗。在倒排索引建立以后，我們在程序中獲得一個倒排索引的實例，然后定義一個搜索的字符串，直接在倒排索引中遍歷這個字符串，然后返回該詞組所指向的倒排索引中的 URL 列表即可。

回頁首

小結

網頁的預處理是搜索引擎的核心部分，建立索引網頁庫是為了網頁數據更方便的從原始網頁庫中獲取，而抽取正文信息是后續操作的基礎。從分詞開始就正式涉及到搜索引擎中文本數據的處理，分詞的好壞以及效率很大程度上決定著搜索引擎的精確性，是非常需要關注的一點，而倒排索引時根據分詞的結果建立的一個“詞組——對應網頁列表”映射，倒排索引是網頁搜索的最關鍵數據結構，搜索引擎執行的速度與倒排索引的建立以及倒排索引的搜索方式息息相關。

回頁首

后續內容

在本系列的第三部分中，您將了解到如何從創建網頁，從網頁中輸入查詢信息通過倒排索引的搜索完成結果的返回，并且完成網頁排名的功能。

只有注冊用戶登錄后才能發表評論。


相關文章: Lucene入門級筆記五 -- 分詞器，使用中文分詞器，擴展詞庫，停用詞網頁解析開源項目一個 Java 搜索引擎的實現，第 2 部分: 網頁預處理一個 Java 搜索引擎的實現，第 1 部分: 網絡爬蟲 java 下載網頁 Apache+php+mysql在XP下搭配詳解 MonoDevelop heritrix1.14.4 tomcatPlugin下載地址 Heritrix-1.14.1怎么配置?

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

登山之道

一個 Java 搜索引擎的實現，第 2 部分: 網頁預處理

日歷

常用鏈接

隨筆分類

隨筆檔案

文章分類

文章檔案

程序的靈魂--算法

沙場秋點兵，壯士凱歌還

他山之石，可以攻玉

圍觀強人

搜索

最新評論

閱讀排行榜