基于開源搜索引擎的架構(gòu)設(shè)計(jì)和J2EE實(shí)現(xiàn)(一)
第一章 引言
面對(duì)浩瀚的網(wǎng)絡(luò)資源，搜索引擎為所有網(wǎng)上沖浪的用戶提供了一個(gè)入口，毫不夸張的說，所有的用戶都可以從搜索出發(fā)到達(dá)自己想去的網(wǎng)上任何一個(gè)地方。因此它也成為除了電子郵件以外最多人使用的網(wǎng)上服務(wù)。
搜索引擎技術(shù)伴隨著WWW的發(fā)展是引人注目的。搜索引擎大約經(jīng)歷了三代的更新發(fā)展：
第一代搜索引擎出現(xiàn)于1994年。這類搜索引擎一般都索引少于1，000，000個(gè)網(wǎng)頁(yè)，極少重新搜集網(wǎng)頁(yè)并去刷新索引。而且其檢索速度非常慢，一般都要等待10秒甚至更長(zhǎng)的時(shí)間。在實(shí)現(xiàn)技術(shù)上也基本沿用較為成熟的IR（Information Retrieval）、網(wǎng)絡(luò)、數(shù)據(jù)庫(kù)等技術(shù)，相當(dāng)于利用一些已有技術(shù)實(shí)現(xiàn)的一個(gè)WWW上的應(yīng)用。在1994年3月到4月，網(wǎng)絡(luò)爬蟲World Web Worm (WWWW)平均每天承受大約1500次查詢。
大約在1996年出現(xiàn)的第二代搜索引擎系統(tǒng)大多采用分布式方案（多個(gè)微型計(jì)算機(jī)協(xié)同工作）來提高數(shù)據(jù)規(guī)模、響應(yīng)速度和用戶數(shù)量，它們一般都保持一個(gè)大約50，000，000網(wǎng)頁(yè)的索引數(shù)據(jù)庫(kù)，每天能夠響應(yīng)10，000，000次用戶檢索請(qǐng)求。1997年11月，當(dāng)時(shí)最先進(jìn)的幾個(gè)搜索引擎號(hào)稱能建立從2，000，000到100，000，000的網(wǎng)頁(yè)索引。Altavista搜索引擎聲稱他們每天大概要承受20，000，000次查詢。
2000年搜索引擎2000年大會(huì)上，按照Google公司總裁Larry Page的演講，Google正在用3,000臺(tái)運(yùn)行Linux系統(tǒng)的個(gè)人電腦在搜集Web上的網(wǎng)頁(yè)，而且以每天30臺(tái)的速度向這個(gè)微機(jī)集群里添加電腦，以保持與網(wǎng)絡(luò)的發(fā)展相同步。每臺(tái)微機(jī)運(yùn)行多個(gè)爬蟲程序搜集網(wǎng)頁(yè)的峰值速度是每秒100個(gè)網(wǎng)頁(yè)，平均速度是每秒48.5個(gè)網(wǎng)頁(yè)，一天可以搜集超過4，000，000網(wǎng)頁(yè)
搜索引擎一詞在國(guó)內(nèi)外因特網(wǎng)領(lǐng)域被廣泛使用，然而他的含義卻不盡相同。在美國(guó)搜索引擎通常指的是基于因特網(wǎng)的搜索引擎，他們通過網(wǎng)絡(luò)機(jī)器人程序收集上千萬到幾億個(gè)網(wǎng)頁(yè)，并且每一個(gè)詞都被搜索引擎索引，也就是我們說的全文檢索。著名的因特網(wǎng)搜索引擎包括First Search、Google、HotBot等。在中國(guó)，搜索引擎通常指基于網(wǎng)站目錄的搜索服務(wù)或是特定網(wǎng)站的搜索服務(wù)，本人這里研究的是基于因特網(wǎng)的搜索技術(shù)。
第二章 搜索引擎的結(jié)構(gòu)
2.1系統(tǒng)概述
搜索引擎是根據(jù)用戶的查詢請(qǐng)求，按照一定算法從索引數(shù)據(jù)中查找信息返回給用戶。為了保證用戶查找信息的精度和新鮮度，搜索引擎需要建立并維護(hù)一個(gè)龐大的索引數(shù)據(jù)庫(kù)。一般的搜索引擎由網(wǎng)絡(luò)機(jī)器人程序、索引與搜索程序、索引數(shù)據(jù)庫(kù)等部分組成。
2.2搜索引擎的構(gòu)成
2.2.1網(wǎng)絡(luò)機(jī)器人
網(wǎng)絡(luò)機(jī)器人也稱為“網(wǎng)絡(luò)蜘蛛”(Spider)，是一個(gè)功能很強(qiáng)的WEB掃描程序。它可以在掃描WEB頁(yè)面的同時(shí)檢索其內(nèi)的超鏈接并加入掃描隊(duì)列等待以后掃描。因?yàn)閃EB中廣泛使用超鏈接，所以一個(gè)Spider程序理論上可以訪問整個(gè)WEB頁(yè)面。
為了保證網(wǎng)絡(luò)機(jī)器人遍歷信息的廣度和深度需要設(shè)定一些重要的鏈接并制定相關(guān)的掃描策略。
2.2.2索引與搜索
網(wǎng)絡(luò)機(jī)器人將遍歷得到的頁(yè)面存放在臨時(shí)數(shù)據(jù)庫(kù)中，如果通過SQL直接查詢信息速度將會(huì)難以忍受。為了提高檢索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及時(shí)跟新的話，用戶用搜索引擎也不能檢索到。
用戶輸入搜索條件后搜索程序?qū)⑼ㄟ^索引數(shù)據(jù)庫(kù)進(jìn)行檢索然后把符合查詢要求的數(shù)據(jù)庫(kù)按照一定的策略進(jìn)行分級(jí)排列并且返回給用戶。
2.2.3 Web服務(wù)器
客戶一般通過瀏覽器進(jìn)行查詢，這就需要系統(tǒng)提供Web服務(wù)器并且與索引數(shù)據(jù)庫(kù)進(jìn)行連接?？蛻粼跒g覽器中輸入查詢條件，Web服務(wù)器接收到客戶的查詢條件后在索引數(shù)據(jù)庫(kù)中進(jìn)行查詢、排列然后返回給客戶端。
2.3搜索引擎的主要指標(biāo)及分析
搜索引擎的主要指標(biāo)有響應(yīng)時(shí)間、召回率、準(zhǔn)確率、相關(guān)度等。這些指標(biāo)決定了搜索引擎的技術(shù)指標(biāo)。搜索引擎的技術(shù)指標(biāo)決定了搜索引擎的評(píng)價(jià)指標(biāo)。好的搜索引擎應(yīng)該是具有較快的反應(yīng)速度和高召回率、準(zhǔn)確率的，當(dāng)然這些都需要搜索引擎技術(shù)指標(biāo)來保障。
召回率：一次搜索結(jié)果中符合用戶要求的數(shù)目與用戶查詢相關(guān)信息的總數(shù)之比
準(zhǔn)確率：一次搜索結(jié)果中符合用戶要求的數(shù)目與該次搜索結(jié)果總數(shù)之比
相關(guān)度：用戶查詢與搜索結(jié)果之間相似度的一種度量
精確度：對(duì)搜索結(jié)果的排序分級(jí)能力和對(duì)垃圾網(wǎng)頁(yè)的抗干擾能力
2.4小節(jié)
以上對(duì)基于因特網(wǎng)的搜索引擎結(jié)構(gòu)和性能指標(biāo)進(jìn)行了分析，本人在這些研究的基礎(chǔ)上利用JavaTM技術(shù)和一些Open Source工具實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的搜索引擎——新聞搜索引擎。在接下來的幾章里將會(huì)就本人的設(shè)計(jì)進(jìn)行詳細(xì)的分析。
第三章 網(wǎng)絡(luò)機(jī)器人
3.1什么是網(wǎng)絡(luò)機(jī)器人
網(wǎng)絡(luò)機(jī)器人又稱為Spider程序，是一種專業(yè)的Bot程序。用于查找大量的Web頁(yè)面。它從一個(gè)簡(jiǎn)單的Web頁(yè)面上開始執(zhí)行，然后通過其超鏈接在訪問其他頁(yè)面，如此反復(fù)理論上可以掃描互聯(lián)網(wǎng)上的所有頁(yè)面。
基于因特網(wǎng)的搜索引擎是Spider的最早應(yīng)用。例如搜索巨頭Google公司，就利用網(wǎng)絡(luò)機(jī)器人程序來遍歷Web站點(diǎn)，以創(chuàng)建并維護(hù)這些大型數(shù)據(jù)庫(kù)。
網(wǎng)絡(luò)機(jī)器人還可以通過掃描Web站點(diǎn)的主頁(yè)來得到這個(gè)站點(diǎn)的文件清單和層次機(jī)構(gòu)。還可以掃描出中斷的超鏈接和拼寫錯(cuò)誤等。
3.2網(wǎng)絡(luò)機(jī)器人的結(jié)構(gòu)分析
Internet是建立在很多相關(guān)協(xié)議基礎(chǔ)上的，而更復(fù)雜的協(xié)議又建立在系統(tǒng)層協(xié)議之上。Web就是建立在HTTP ( Hypertext Transfer Protocol ) 協(xié)議基礎(chǔ)上，而HTTP又是建立在TCP/IP ( Transmission Control Protocol / Internet Protocol ) 協(xié)議之上，它同時(shí)也是一種Socket協(xié)議。所以網(wǎng)絡(luò)機(jī)器人本質(zhì)上是一種基于Socket的網(wǎng)絡(luò)程序。
3.2.1如何解析HTML
因?yàn)閃eb中的信息都是建立在HTML協(xié)議之上的，所以網(wǎng)絡(luò)機(jī)器人在檢索網(wǎng)頁(yè)時(shí)的第一個(gè)問題就是如何解析HTML。在解決如何解析之前，先來介紹下HTML中的幾種數(shù)據(jù)。
文本：除了腳本和標(biāo)簽之外的所有數(shù)據(jù)
注釋：程序員留下的說明文字，對(duì)用戶是不可見的
簡(jiǎn)單標(biāo)簽：由單個(gè)表示的HTML標(biāo)簽
開始標(biāo)簽和結(jié)束標(biāo)簽：用來控制所包含的HTML代碼
我們?cè)谶M(jìn)行解析的時(shí)候不用關(guān)心所有的標(biāo)簽，只需要對(duì)其中幾種重要的進(jìn)行解析即可。
超連接標(biāo)簽
超連接定義了WWW通過Internet鏈接文檔的功能。他們的主要目的是使用戶能夠任意遷移到新的頁(yè)面，這正是網(wǎng)絡(luò)機(jī)器人最關(guān)心的標(biāo)簽。
圖像映射標(biāo)簽
圖像映射是另一種非常重要的標(biāo)簽。它可以讓用戶通過點(diǎn)擊圖片來遷移到新的頁(yè)面中。
表單標(biāo)簽
表單是Web頁(yè)面中可以輸入數(shù)據(jù)的單元。許多站點(diǎn)讓用戶填寫數(shù)據(jù)然后通過點(diǎn)擊按鈕來提交內(nèi)容，這就是表單的典型應(yīng)用。
表格標(biāo)簽
表格是HTML的構(gòu)成部分，通常用來格式化存放、顯示數(shù)據(jù)。
我們?cè)诰唧w解析這些HTMl標(biāo)簽有兩種方法：通過JavaTM中的Swing類來解析或者通過Bot包中的HTMLPage類來解析，本人在實(shí)際編程中采用后者。
Bot包中的HTMLPage類用來從指定URL中讀取數(shù)據(jù)并檢索出有用的信息。下面給出該類幾種重要的方法。
HTMLPage構(gòu)造函數(shù) 構(gòu)造對(duì)象并指定用于通訊的HTTP對(duì)象
Public HTMLPage(HTTP http)
GetForms方法 獲取最后一次調(diào)用Open方法檢索到的表單清單
Public Vector getForms()
GetHTTP方法 獲取發(fā)送給構(gòu)造函數(shù)的HTTP對(duì)象
Public HTTP getHTTP()
GetImage方法 獲取指定頁(yè)面的圖片清單
Public Vector getImage()
GetLinks方法 獲取指定頁(yè)面的連接清單
Public Vector getLinks()
Open方法 打開一個(gè)頁(yè)面并讀入該頁(yè)面，若指定了回調(diào)對(duì)象則給出所有該對(duì)象數(shù)據(jù)
Public void open(String url,HTMLEditorKit.ParserCallback a)
3.2.2 Spider程序結(jié)構(gòu)
網(wǎng)絡(luò)機(jī)器人必須從一個(gè)網(wǎng)頁(yè)遷移到另一個(gè)網(wǎng)頁(yè)，所以必須找到該頁(yè)面上的超連接。程序首先解析網(wǎng)頁(yè)的HTML代碼，查找該頁(yè)面內(nèi)的超連接然后通過遞歸和非遞歸兩種結(jié)構(gòu)來實(shí)現(xiàn)Spider程序。
遞歸結(jié)構(gòu)
遞歸是在一個(gè)方法中調(diào)用自己本身的程序設(shè)計(jì)技術(shù)。雖然比較容易實(shí)現(xiàn)但耗費(fèi)內(nèi)存且不能使用多線程技術(shù)，故不適合大型項(xiàng)目。
非遞歸結(jié)構(gòu)
這種方法使用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，當(dāng)Spider程序發(fā)現(xiàn)超連接后并不調(diào)用自己本身而是把超連接加入到等待隊(duì)列中。當(dāng)Spider程序掃描完當(dāng)前頁(yè)面后會(huì)根據(jù)制定的策略訪問隊(duì)列中的下一個(gè)超連接地址。
雖然這里只描述了一個(gè)隊(duì)列，但在實(shí)際編程中用到了四個(gè)隊(duì)列，他們每個(gè)隊(duì)列都保存著同一處理狀態(tài)的URL。
等待隊(duì)列 在這個(gè)隊(duì)列中，URL等待被Spider程序處理。新發(fā)現(xiàn)的URL也被加入到這個(gè)隊(duì)列中
處理隊(duì)列 當(dāng)Spider程序開始處理時(shí)，他們被送到這個(gè)隊(duì)列中
錯(cuò)誤隊(duì)列 如果在解析網(wǎng)頁(yè)時(shí)出錯(cuò)，URL將被送到這里。該隊(duì)列中的URL不能被移入其他隊(duì)列中
完成隊(duì)列 如果解析網(wǎng)頁(yè)沒有出錯(cuò)，URL將被送到這里。該隊(duì)列中的URL不能被移入其它隊(duì)列中
在同一時(shí)間URL只能在一個(gè)隊(duì)列中，我們把它稱為URL的狀態(tài)。
以上的圖表示了隊(duì)列的變化過程，在這個(gè)過程中，當(dāng)一個(gè)URL被加入到等待隊(duì)列中時(shí)Spider程序就會(huì)開始運(yùn)行。只要等待隊(duì)列中有一個(gè)網(wǎng)頁(yè)或Spider程序正在處理一個(gè)網(wǎng)頁(yè)，程序就會(huì)繼續(xù)他的工作。當(dāng)?shù)却?duì)列為空并且當(dāng)前沒有任何網(wǎng)頁(yè)時(shí)，Spider程序就會(huì)停止它的工作。
3.2.3如何構(gòu)造Spider程序
在構(gòu)造Spider程序之前我們先了解下程序的各個(gè)部分是如何共同工作的。以及如何對(duì)這個(gè)程序進(jìn)行擴(kuò)展。
流程圖如下所示：
IspiderReportable接口
這是一個(gè)必須實(shí)現(xiàn)的接口，可以通過回調(diào)函數(shù)接受Spider所遇到的頁(yè)面。接口定義了Spider向他的控制者發(fā)送的幾個(gè)事件。通過提供對(duì)每個(gè)事件的處理程序，可以創(chuàng)建各種Spider程序。下面是他的接口聲明：
- public interface IspiderReportable{
- public boolean foundInternalLink(String url);
- public boolean foundExternalLink(String url);
- public boolean foundOtherLink(String url);
- public void processPage(HTTP page);
- public void completePage(HTTP page,boolean error);
- public boolean getRemoveQuery();
- public void SpiderComplete();
- }
3.2.4如何提高程序性能
Internet中擁有海量的Web頁(yè)面，如果開發(fā)出高效的Spider程序是非常重要的。下面就來介紹下幾種提高性能的技術(shù)：
Java的多線程技術(shù)
線程是通過程序的一條執(zhí)行路線。多線程是一個(gè)程序同時(shí)運(yùn)行多個(gè)任務(wù)的能力。它是在一個(gè)程序的內(nèi)部進(jìn)行分工合作。
優(yōu)化程序的通常方法是確定瓶頸并改進(jìn)他。瓶頸是一個(gè)程序中最慢的部分，他限制了其他任務(wù)的運(yùn)行。據(jù)個(gè)例子說明：一個(gè)Spider程序需要下載十個(gè)頁(yè)面，要完成這一任務(wù)，程序必須向服務(wù)器發(fā)出請(qǐng)求然后接受這些網(wǎng)頁(yè)。當(dāng)程序等待響應(yīng)的時(shí)候其他任務(wù)不能執(zhí)行，這就影響了程序的效率。如果用多線程技術(shù)可以讓這些網(wǎng)頁(yè)的等待時(shí)間合在一起，不用互相影響，這就可以極大的改進(jìn)程序性能。
數(shù)據(jù)庫(kù)技術(shù)
當(dāng)Spider程序訪問一個(gè)大型Web站點(diǎn)時(shí)，必須使用一種有效的方法來存儲(chǔ)站點(diǎn)隊(duì)列。這些隊(duì)列管理Spider程序必須維護(hù)大型網(wǎng)頁(yè)的列表。如果把他們放在內(nèi)存中將會(huì)是性能下降，所以我們可以把他們放在數(shù)據(jù)庫(kù)中減少系統(tǒng)資源的消耗。
3.2.5網(wǎng)絡(luò)機(jī)器人的代碼分析
程序代碼實(shí)現(xiàn)如下：
- package news;
- /**
- * 新聞搜索引擎
- * 計(jì)算機(jī)99630 沈晨
- * 版本 1.0
- */
- import com.heaton.bot.HTTP;
- import com.heaton.bot.HTTPSocket;
- import com.heaton.bot.ISpiderReportable;
- import com.heaton.bot.IWorkloadStorable;
- import com.heaton.bot.Spider;
- import com.heaton.bot.SpiderInternalWorkload;
- /**
- * 構(gòu)造一個(gè)Bot程序
- */
- public class Searcher
- implements ISpiderReportable {
- public static void main(String[] args) throws Exception {
- IWorkloadStorable wl = new SpiderInternalWorkload();
- Searcher _searcher = new Searcher();
- Spider _spider
- = new Spider(_searcher, "http://127.0.0.1/news.htm",
- new HTTPSocket(), 100, wl);
- _spider.setMaxBody(100);
- _spider.start();
- }
- // 發(fā)現(xiàn)內(nèi)部連接時(shí)調(diào)用，url表示程序發(fā)現(xiàn)的URL，若返回true則加入作業(yè)中，否則不加入。
- public boolean foundInternalLink(String url) {
- return false;
- }
- // 發(fā)現(xiàn)外部連接時(shí)調(diào)用，url表示程序所發(fā)現(xiàn)的URL，若返回true則把加入作業(yè)中，否則不加入。
- public boolean foundExternalLink(String url) {
- return false;
- }
- // 當(dāng)發(fā)現(xiàn)其他連接時(shí)調(diào)用這個(gè)方法。其他連接指的是非HTML網(wǎng)頁(yè)，可能是E-mail或者FTP
- public boolean foundOtherLink(String url) {
- return false;
- }
- // 用于處理網(wǎng)頁(yè)，這是Spider程序要完成的實(shí)際工作。
- public void processPage(HTTP http) {
- System.out.println("掃描網(wǎng)頁(yè)：" + http.getURL());
- new HTMLParse(http).start();
- }
- // 用來請(qǐng)求一個(gè)被處理的網(wǎng)頁(yè)。
- public void completePage(HTTP http, boolean error) {
- }
- // 由Spider程序調(diào)用以確定查詢字符串是否應(yīng)刪除。如果隊(duì)列中的字符串應(yīng)當(dāng)刪除，方法返回真。
- public boolean getRemoveQuery() {
- return true;
- }
- // 當(dāng)Spider程序沒有剩余的工作時(shí)調(diào)用這個(gè)方法。
- public void spiderComplete() {
- }
- }
3.3小節(jié)
在本章中，首先介紹了網(wǎng)絡(luò)機(jī)器人的基本概念，然后具體分析了Spider程序的結(jié)構(gòu)和功能。在最后還結(jié)合具體代碼進(jìn)行了詳細(xì)說明。
本人在編程中運(yùn)用了Java技術(shù)，主要涉及到了net和io兩個(gè)包。此外還用了第三方開發(fā)包Bot（由Jeff Heaton提供的開發(fā)包）。
【編輯推薦】
