久久精品一区,欧美大片第1页,久久精品日韩欧美

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

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

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

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

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

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

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

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

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

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

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

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

假設(shè)分詞器和網(wǎng)頁排名的計(jì)算公式都是既定的，那么倒排索引以及原始網(wǎng)頁集從何而來？原始網(wǎng)頁集在之前的數(shù)據(jù)流程的介紹中，可以得知是由爬蟲 spider 爬取網(wǎng)頁并且保存在本地的，而倒排索引，即詞組到網(wǎng)頁的映射表是建立在正排索引的基礎(chǔ)上的，后者是分析了網(wǎng)頁的內(nèi)容并對(duì)其內(nèi)容進(jìn)行分詞后，得到的網(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)頁庫存儲(chǔ)于本地，然后網(wǎng)頁分析器抽取網(wǎng)頁中的主題內(nèi)容交給分詞器進(jìn)行分詞，得到的結(jié)果用索引器建立正排和倒排索引，這樣就得到了索引數(shù)據(jù)庫，用戶查詢時(shí)，在通過分詞器切割輸入的查詢?cè)~組并通過檢索器在索引數(shù)據(jù)庫中進(jìn)行查詢，得到的結(jié)果返回給用戶。

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

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

回頁首

Spider 的設(shè)計(jì)

網(wǎng)頁收集的過程如同圖的遍歷，其中網(wǎng)頁就作為圖中的節(jié)點(diǎn)，而網(wǎng)頁中的超鏈接則作為圖中的邊，通過某網(wǎng)頁的超鏈接得到其他網(wǎng)頁的地址，從而可以進(jìn)一步的進(jìn)行網(wǎng)頁收集；圖的遍歷分為廣度優(yōu)先和深度優(yōu)先兩種方法，網(wǎng)頁的收集過程也是如此。綜上，Spider 收集網(wǎng)頁的過程如下：從初始 URL 集合獲得目標(biāo)網(wǎng)頁地址，通過網(wǎng)絡(luò)連接接收網(wǎng)頁數(shù)據(jù)，將獲得的網(wǎng)頁數(shù)據(jù)添加到網(wǎng)頁庫中并且分析該網(wǎng)頁中的其他 URL 鏈接，放入未訪問 URL 集合用于網(wǎng)頁收集。下圖表示了這個(gè)過程：

圖 3. Spider 工作流程

回頁首

Spider 的具體實(shí)現(xiàn)

網(wǎng)頁收集器 Gather

網(wǎng)頁收集器通過一個(gè) URL 來獲取該 URL 對(duì)應(yīng)的網(wǎng)頁數(shù)據(jù)，其實(shí)現(xiàn)主要是利用 Java 中的 URLConnection 類來打開 URL 對(duì)應(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ò)編程的讀者也可以不用上述的方法，自己實(shí)現(xiàn) URL 類及相關(guān)操作，這也是一種很好的鍛煉。

網(wǎng)頁處理

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

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

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

一條記錄由數(shù)據(jù)頭、數(shù)據(jù)、空行組成，順序?yàn)椋侯^部 + 空行 + 數(shù)據(jù) + 空行；

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

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

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

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

清單 2. URL 識(shí)別

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">

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

//可以對(duì)于前兩個(gè)"之間的部分進(jìn)行記錄得到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*>)”這個(gè)正則表達(dá)式可以匹配出 URL 所在的整個(gè)標(biāo)簽，形如“<a href="http://bbs.life.xxx.com.cn/" target="_blank">”，所以在循環(huán)獲得整個(gè)標(biāo)簽之后，需要進(jìn)一步提取出真正的 URL，我們可以通過截取標(biāo)簽中前兩個(gè)引號(hào)中間的內(nèi)容來獲得這段內(nèi)容。如此之后，我們可以得到一個(gè)初步的屬于該網(wǎng)頁的 URL 集合。

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

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

Dispatcher 分配器

分配器管理 URL，負(fù)責(zé)保存著 URL 池并且在 Gather 取得某一個(gè)網(wǎng)頁之后派分新的 URL，還要避免網(wǎng)頁的重復(fù)收集。分配器采用設(shè)計(jì)模式中的單例模式編碼，負(fù)責(zé)提供給 Gather 新的 URL，因?yàn)樯婕暗街蟮亩嗑€程改寫，所以單例模式顯得尤為重要。

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

Spider 啟動(dòng)多個(gè) Gather 線程

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

/**

* 啟動(dòng)線程 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ùn)作，并在一個(gè)作業(yè)完成之后，向 Dispatcher 申請(qǐng)下一個(gè)作業(yè)，因?yàn)橛辛硕嗑€程的 Gather，為了避免線程不安全，需要對(duì) Dispatcher 進(jìn)行互斥訪問，在其函數(shù)之中添加 synchronized 關(guān)鍵詞，從而達(dá)到線程的安全訪問。

回頁首

小結(jié)

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

回頁首

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

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

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


相關(guān)文章: Lucene入門級(jí)筆記五 -- 分詞器，使用中文分詞器，擴(kuò)展詞庫，停用詞網(wǎng)頁解析開源項(xiàng)目一個(gè) Java 搜索引擎的實(shí)現(xiàn)，第 2 部分: 網(wǎng)頁預(yù)處理一個(gè) Java 搜索引擎的實(shí)現(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 管理

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

登山之道

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

日歷

常用鏈接

隨筆分類

隨筆檔案

文章分類

文章檔案

程序的靈魂--算法

沙場秋點(diǎn)兵，壯士凱歌還

他山之石，可以攻玉

圍觀強(qiáng)人

搜索

最新評(píng)論

閱讀排行榜