国产精品亚洲视频,美日韩在线观看,亚洲色图在线视频

一個 Java 搜索引擎的實現(xiàn)，第 1 部分: 網(wǎng)絡(luò)爬蟲

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

自己動手寫一個搜索引擎，想想這有多 cool：在界面上輸入關(guān)鍵詞，點擊搜索，得到自己想要的結(jié)果；那么它還可以做什么呢？也許是自己的網(wǎng)站需要一個站內(nèi)搜索功能，抑或是對于硬盤中文檔的搜索 —— 最重要的是，是不是覺得眾多 IT 公司都在向你招手呢？如果你心動了，那么，Let's Go！

這里首先要說明使用 Java 語言而不是 C/C++ 等其它語言的原因，因為 Java 中提供了對于網(wǎng)絡(luò)編程眾多的基礎(chǔ)包和類，比如 URL 類、InetAddress 類、正則表達式，這為我們的搜索引擎實現(xiàn)提供了良好的基礎(chǔ)，使我們可以專注于搜索引擎本身的實現(xiàn)，而不需要因為這些基礎(chǔ)類的實現(xiàn)而分心。

這個分三部分的系列將逐步說明如何設(shè)計和實現(xiàn)一個搜索引擎。在第一部分中，您將首先學習搜索引擎的工作原理，同時了解其體系結(jié)構(gòu)，之后將講解如何實現(xiàn)搜索引擎的第一部分，網(wǎng)絡(luò)爬蟲模塊，即完成網(wǎng)頁搜集功能。在系列的第二部分中，將介紹預(yù)處理模塊，即如何處理收集來的網(wǎng)頁，整理、分詞以及索引的建立都在這部分之中。在系列的第三部分中，將介紹信息查詢服務(wù)的實現(xiàn)，主要是查詢界面的建立、查詢結(jié)果的返回以及快照的實現(xiàn)。

dySE 的整體結(jié)構(gòu)

在開始學習搜索引擎的模塊實現(xiàn)之前，您需要了解 dySE 的整體結(jié)構(gòu)以及數(shù)據(jù)傳輸?shù)牧鞒獭Ｊ聦嵣希阉饕娴娜齻€部分是相互獨立的，三個部分分別工作，主要的關(guān)系體現(xiàn)在前一部分得到的數(shù)據(jù)結(jié)果為后一部分提供原始數(shù)據(jù)。三者的關(guān)系如下圖所示：

圖 1. 搜索引擎三段式工作流程

在介紹搜索引擎的整體結(jié)構(gòu)之前，我們借鑒《計算機網(wǎng)絡(luò)——自頂向下的方法描述因特網(wǎng)特色》一書的敘事方法，從普通用戶使用搜索引擎的角度來介紹搜索引擎的具體工作流程。

自頂向下的方法描述搜索引擎執(zhí)行過程：

用戶通過瀏覽器提交查詢的詞或者短語 P，搜索引擎根據(jù)用戶的查詢返回匹配的網(wǎng)頁信息列表 L；

上述過程涉及到兩個問題，如何匹配用戶的查詢以及網(wǎng)頁信息列表從何而來，根據(jù)什么而排序？用戶的查詢 P 經(jīng)過分詞器被切割成小詞組 <p1,p2 … pn> 并被剔除停用詞 ( 的、了、啊等字 )，根據(jù)系統(tǒng)維護的一個倒排索引可以查詢某個詞 pi 在哪些網(wǎng)頁中出現(xiàn)過，匹配那些 <p1,p2 … pn> 都出現(xiàn)的網(wǎng)頁集即可作為初始結(jié)果，更進一步，返回的初始網(wǎng)頁集通過計算與查詢詞的相關(guān)度從而得到網(wǎng)頁排名，即 Page Rank，按照網(wǎng)頁的排名順序即可得到最終的網(wǎng)頁列表；

假設(shè)分詞器和網(wǎng)頁排名的計算公式都是既定的，那么倒排索引以及原始網(wǎng)頁集從何而來？原始網(wǎng)頁集在之前的數(shù)據(jù)流程的介紹中，可以得知是由爬蟲 spider 爬取網(wǎng)頁并且保存在本地的，而倒排索引，即詞組到網(wǎng)頁的映射表是建立在正排索引的基礎(chǔ)上的，后者是分析了網(wǎng)頁的內(nèi)容并對其內(nèi)容進行分詞后，得到的網(wǎng)頁到詞組的映射表，將正排索引倒置即可得到倒排索引；

網(wǎng)頁的分析具體做什么呢？由于爬蟲收集來的原始網(wǎng)頁中包含很多信息，比如 html 表單以及一些垃圾信息比如廣告，網(wǎng)頁分析去除這些信息，并抽取其中的正文信息作為后續(xù)的基礎(chǔ)數(shù)據(jù)。

在有了上述的分析之后，我們可以得到搜索引擎的整體結(jié)構(gòu)如下圖：

圖 2. 搜索引擎整體結(jié)構(gòu)

爬蟲從 Internet 中爬取眾多的網(wǎng)頁作為原始網(wǎng)頁庫存儲于本地，然后網(wǎng)頁分析器抽取網(wǎng)頁中的主題內(nèi)容交給分詞器進行分詞，得到的結(jié)果用索引器建立正排和倒排索引，這樣就得到了索引數(shù)據(jù)庫，用戶查詢時，在通過分詞器切割輸入的查詢詞組并通過檢索器在索引數(shù)據(jù)庫中進行查詢，得到的結(jié)果返回給用戶。

無論搜索引擎的規(guī)模大小，其主要結(jié)構(gòu)都是由這幾部分構(gòu)成的，并沒有大的差別，搜索引擎的好壞主要是決定于各部分的內(nèi)部實現(xiàn)。

有了上述的對與搜索引擎的整體了解，我們來學習 dySE 中爬蟲模塊的具體設(shè)計和實現(xiàn)。

回頁首

Spider 的設(shè)計

網(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)絡(luò)連接接收網(wǎng)頁數(shù)據(jù)，將獲得的網(wǎng)頁數(shù)據(jù)添加到網(wǎng)頁庫中并且分析該網(wǎng)頁中的其他 URL 鏈接，放入未訪問 URL 集合用于網(wǎng)頁收集。下圖表示了這個過程：

圖 3. Spider 工作流程

回頁首

Spider 的具體實現(xiàn)

網(wǎng)頁收集器 Gather

網(wǎng)頁收集器通過一個 URL 來獲取該 URL 對應(yīng)的網(wǎng)頁數(shù)據(jù)，其實現(xiàn)主要是利用 Java 中的 URLConnection 類來打開 URL 對應(yīng)頁面的網(wǎng)絡(luò)連接，然后通過 I/O 流讀取其中的數(shù)據(jù)，BufferedReader 提供讀取數(shù)據(jù)的緩沖區(qū)提高數(shù)據(jù)讀取的效率以及其下定義的 readLine() 行讀取函數(shù)。代碼如下 ( 省略了異常處理部分 )：

清單 1. 網(wǎng)頁數(shù)據(jù)抓取

URL url = new URL(“http://www.xxx.com”);

URLConnection conn = url.openConnection();

BufferedReader reader = new BufferedReader(new InputStreamReader(conn.getInputStream()));

String line = null;

while((line = reader.readLine()) != null)

document.append(line + "\n");

使用 Java 語言的好處是不需要自己處理底層的連接操作，喜歡或者精通 Java 網(wǎng)絡(luò)編程的讀者也可以不用上述的方法，自己實現(xiàn) URL 類及相關(guān)操作，這也是一種很好的鍛煉。

網(wǎng)頁處理

收集到的單個網(wǎng)頁，需要進行兩種不同的處理，一種是放入網(wǎng)頁庫，作為后續(xù)處理的原始數(shù)據(jù)；另一種是被分析之后，抽取其中的 URL 連接，放入 URL 池等待對應(yīng)網(wǎng)頁的收集。

網(wǎng)頁的保存需要按照一定的格式，以便以后數(shù)據(jù)的批量處理。這里介紹一種存儲數(shù)據(jù)格式，該格式從北大天網(wǎng)的存儲格式簡化而來：

網(wǎng)頁庫由若干記錄組成，每個記錄包含一條網(wǎng)頁數(shù)據(jù)信息，記錄的存放為順序添加；

一條記錄由數(shù)據(jù)頭、數(shù)據(jù)、空行組成，順序為：頭部 + 空行 + 數(shù)據(jù) + 空行；

頭部由若干屬性組成，有：版本號，日期，IP 地址，數(shù)據(jù)長度，按照屬性名和屬性值的方式排列，中間加冒號，每個屬性占用一行；

數(shù)據(jù)即為網(wǎng)頁數(shù)據(jù)。

需要說明的是，添加數(shù)據(jù)收集日期的原因，由于許多網(wǎng)站的內(nèi)容都是動態(tài)變化的，比如一些大型門戶網(wǎng)站的首頁內(nèi)容，這就意味著如果不是當天爬取的網(wǎng)頁數(shù)據(jù)，很可能發(fā)生數(shù)據(jù)過期的問題，所以需要添加日期信息加以識別。

URL 的提取分為兩步，第一步是 URL 識別，第二步再進行 URL 的整理，分兩步走主要是因為有些網(wǎng)站的鏈接是采用相對路徑，如果不整理會產(chǎn)生錯誤。URL 的識別主要是通過正則表達式來匹配，過程首先設(shè)定一個字符串作為匹配的字符串模式，然后在 Pattern 中編譯后即可使用 Matcher 類來進行相應(yīng)字符串的匹配。實現(xiàn)代碼如下：

清單 2. URL 識別

public ArrayList<URL> urlDetector(String htmlDoc){

final String patternString = "<[a|A]\\s+href=([^>]*\\s*>)";

Pattern pattern = Pattern.compile(patternString,Pattern.CASE_INSENSITIVE);

ArrayList<URL> allURLs = new ArrayList<URL>();

Matcher matcher = pattern.matcher(htmlDoc);

String tempURL;

//初次匹配到的url是形如：<a href="http://bbs.life.xxx.com.cn/" target="_blank">

//為此，需要進行下一步的處理，把真正的url抽取出來，

//可以對于前兩個"之間的部分進行記錄得到url

while(matcher.find()){

try {

tempURL = matcher.group();

tempURL = tempURL.substring(tempURL.indexOf("\"")+1);

if(!tempURL.contains("\""))

continue;

tempURL = tempURL.substring(0, tempURL.indexOf("\""));

} catch (MalformedURLException e) {

e.printStackTrace();

}

return allURLs;

}

按照“<[a|A]\\s+href=([^>]*\\s*>)”這個正則表達式可以匹配出 URL 所在的整個標簽，形如“<a href="http://bbs.life.xxx.com.cn/" target="_blank">”，所以在循環(huán)獲得整個標簽之后，需要進一步提取出真正的 URL，我們可以通過截取標簽中前兩個引號中間的內(nèi)容來獲得這段內(nèi)容。如此之后，我們可以得到一個初步的屬于該網(wǎng)頁的 URL 集合。

接下來我們進行第二步操作，URL 的整理，即對之前獲得的整個頁面中 URL 集合進行篩選和整合。整合主要是針對網(wǎng)頁地址是相對鏈接的部分，由于我們可以很容易的獲得當前網(wǎng)頁的 URL，所以，相對鏈接只需要在當前網(wǎng)頁的 URL 上添加相對鏈接的字段即可組成完整的 URL，從而完成整合。另一方面，在頁面中包含的全面 URL 中，有一些網(wǎng)頁比如廣告網(wǎng)頁是我們不想爬取的，或者不重要的，這里我們主要針對于頁面中的廣告進行一個簡單處理。一般網(wǎng)站的廣告連接都有相應(yīng)的顯示表達，比如連接中含有“ad”等表達時，可以將該鏈接的優(yōu)先級降低，這樣就可以一定程度的避免廣告鏈接的爬取。

經(jīng)過這兩步操作時候，可以把該網(wǎng)頁的收集到的 URL 放入 URL 池中，接下來我們處理爬蟲的 URL 的派分問題。

Dispatcher 分配器

分配器管理 URL，負責保存著 URL 池并且在 Gather 取得某一個網(wǎng)頁之后派分新的 URL，還要避免網(wǎng)頁的重復(fù)收集。分配器采用設(shè)計模式中的單例模式編碼，負責提供給 Gather 新的 URL，因為涉及到之后的多線程改寫，所以單例模式顯得尤為重要。

重復(fù)收集是指物理上存在的一個網(wǎng)頁，在沒有更新的前提下，被 Gather 重復(fù)訪問，造成資源的浪費，主要原因是沒有清楚的記錄已經(jīng)訪問的 URL 而無法辨別。所以，Dispatcher 維護兩個列表 ,“已訪問表”，和“未訪問表”。每個 URL 對應(yīng)的頁面被抓取之后，該 URL 放入已訪問表中，而從該頁面提取出來的 URL 則放入未訪問表中；當 Gather 向 Dispatcher 請求 URL 的時候，先驗證該 URL 是否在已訪問表中，然后再給 Gather 進行作業(yè)。

Spider 啟動多個 Gather 線程

現(xiàn)在 Internet 中的網(wǎng)頁數(shù)量數(shù)以億計，而單獨的一個 Gather 來進行網(wǎng)頁收集顯然效率不足，所以我們需要利用多線程的方法來提高效率。Gather 的功能是收集網(wǎng)頁，我們可以通過 Spider 類來開啟多個 Gather 線程，從而達到多線程的目的。代碼如下：

/**

* 啟動線程 gather，然后開始收集網(wǎng)頁資料

public void start() {

Dispatcher disp = Dispatcher.getInstance();

for(int i = 0; i < gatherNum; i++){

Thread gather = new Thread(new Gather(disp));

gather.start();

}

在開啟線程之后，網(wǎng)頁收集器開始作業(yè)的運作，并在一個作業(yè)完成之后，向 Dispatcher 申請下一個作業(yè)，因為有了多線程的 Gather，為了避免線程不安全，需要對 Dispatcher 進行互斥訪問，在其函數(shù)之中添加 synchronized 關(guān)鍵詞，從而達到線程的安全訪問。

回頁首

小結(jié)

Spider 是整個搜索引擎的基礎(chǔ)，為后續(xù)的操作提供原始網(wǎng)頁資料，所以了解 Spider 的編寫以及網(wǎng)頁庫的組成結(jié)構(gòu)為后續(xù)預(yù)處理模塊打下基礎(chǔ)。同時 Spider 稍加修改之后也可以單獨用于某類具體信息的搜集，比如某個網(wǎng)站的圖片爬取等。

回頁首

后續(xù)內(nèi)容

在本系列的第 2 部分中，您將了解到爬蟲獲取的網(wǎng)頁庫如何被預(yù)處理模塊逐步提取內(nèi)容信息，通過分詞并建成倒排索引；而在第 3 部分中，您將了解到，如何編寫網(wǎng)頁來提供查詢服務(wù)，并且如何顯示的返回的結(jié)果和完成快照的功能。

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


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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

登山之道

一個 Java 搜索引擎的實現(xiàn)，第 1 部分: 網(wǎng)絡(luò)爬蟲

日歷

常用鏈接

隨筆分類

隨筆檔案

文章分類

文章檔案

程序的靈魂--算法

沙場秋點兵，壯士凱歌還

他山之石，可以攻玉

圍觀強人

搜索

最新評論

閱讀排行榜