第一章 引言

面對浩瀚的網絡資源，搜索引擎為所有網上沖浪的用戶提供了一個入口，毫不夸張的說，所有的用戶都可以從搜索出發(fā)到達自己想去的網上任何一個地方。因此它也成為除了電子郵件以外最多人使用的網上服務。

搜索引擎技術伴隨著WWW的發(fā)展是引人注目的。搜索引擎大約經歷了三代的更新發(fā)展：

第一代搜索引擎出現(xiàn)于1994年。這類搜索引擎一般都索引少于1，000，000個網頁，極少重新搜集網頁并去刷新索引。而且其檢索速度非常慢，一般都要等待10秒甚至更長的時間。在實現(xiàn)技術上也基本沿用較為成熟的IR（Information Retrieval）、網絡、數(shù)據(jù)庫等技術，相當于利用一些已有技術實現(xiàn)的一個WWW上的應用。在1994年3月到4月，網絡爬蟲World Web Worm (WWWW)平均每天承受大約1500次查詢。

大約在1996年出現(xiàn)的第二代搜索引擎系統(tǒng)大多采用分布式方案（多個微型計算機協(xié)同工作）來提高數(shù)據(jù)規(guī)模、響應速度和用戶數(shù)量，它們一般都保持一個大約50，000，000網頁的索引數(shù)據(jù)庫，每天能夠響應10，000，000次用戶檢索請求。1997年11月，當時最先進的幾個搜索引擎號稱能建立從2，000，000到100，000，000的網頁索引。Altavista搜索引擎聲稱他們每天大概要承受20，000，000次查詢。

2000年搜索引擎2000年大會上，按照Google公司總裁Larry Page的演講，Google正在用3,000臺運行Linux系統(tǒng)的個人電腦在搜集Web上的網頁，而且以每天30臺的速度向這個微機集群里添加電腦，以保持與網絡的發(fā)展相同步。每臺微機運行多個爬蟲程序搜集網頁的峰值速度是每秒100個網頁，平均速度是每秒48.5個網頁，一天可以搜集超過4，000，000網頁

搜索引擎一詞在國內外因特網領域被廣泛使用，然而他的含義卻不盡相同。在美國搜索引擎通常指的是基于因特網的搜索引擎，他們通過網絡機器人程序收集上千萬到幾億個網頁，并且每一個詞都被搜索引擎索引，也就是我們說的全文檢索。著名的因特網搜索引擎包括First Search、Google、HotBot等。在中國，搜索引擎通常指基于網站目錄的搜索服務或是特定網站的搜索服務，本人這里研究的是基于因特網的搜索技術。

第二章 搜索引擎的結構

2.1系統(tǒng)概述

搜索引擎是根據(jù)用戶的查詢請求，按照一定算法從索引數(shù)據(jù)中查找信息返回給用戶。為了保證用戶查找信息的精度和新鮮度，搜索引擎需要建立并維護一個龐大的索引數(shù)據(jù)庫。一般的搜索引擎由網絡機器人程序、索引與搜索程序、索引數(shù)據(jù)庫等部分組成。

2.2搜索引擎的構成

2.2.1網絡機器人

網絡機器人也稱為“網絡蜘蛛”(Spider)，是一個功能很強的WEB掃描程序。它可以在掃描WEB頁面的同時檢索其內的超鏈接并加入掃描隊列等待以后掃描。因為WEB中廣泛使用超鏈接，所以一個Spider程序理論上可以訪問整個WEB頁面。

為了保證網絡機器人遍歷信息的廣度和深度需要設定一些重要的鏈接并制定相關的掃描策略。

2.2.2索引與搜索

網絡機器人將遍歷得到的頁面存放在臨時數(shù)據(jù)庫中，如果通過SQL直接查詢信息速度將會難以忍受。為了提高檢索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及時跟新的話，用戶用搜索引擎也不能檢索到。

用戶輸入搜索條件后搜索程序將通過索引數(shù)據(jù)庫進行檢索然后把符合查詢要求的數(shù)據(jù)庫按照一定的策略進行分級排列并且返回給用戶。

2.2.3 Web服務器

客戶一般通過瀏覽器進行查詢，這就需要系統(tǒng)提供Web服務器并且與索引數(shù)據(jù)庫進行連接?？蛻粼跒g覽器中輸入查詢條件，Web服務器接收到客戶的查詢條件后在索引數(shù)據(jù)庫中進行查詢、排列然后返回給客戶端。

2.3搜索引擎的主要指標及分析

搜索引擎的主要指標有響應時間、召回率、準確率、相關度等。這些指標決定了搜索引擎的技術指標。搜索引擎的技術指標決定了搜索引擎的評價指標。好的搜索引擎應該是具有較快的反應速度和高召回率、準確率的，當然這些都需要搜索引擎技術指標來保障。

召回率：一次搜索結果中符合用戶要求的數(shù)目與用戶查詢相關信息的總數(shù)之比

準確率：一次搜索結果中符合用戶要求的數(shù)目與該次搜索結果總數(shù)之比

相關度：用戶查詢與搜索結果之間相似度的一種度量

精確度：對搜索結果的排序分級能力和對垃圾網頁的抗干擾能力

2.4小節(jié)

以上對基于因特網的搜索引擎結構和性能指標進行了分析，本人在這些研究的基礎上利用JavaTM技術和一些Open Source工具實現(xiàn)了一個簡單的搜索引擎——新聞搜索引擎。在接下來的幾章里將會就本人的設計進行詳細的分析。

第三章 網絡機器人

3.1什么是網絡機器人

網絡機器人又稱為Spider程序，是一種專業(yè)的Bot程序。用于查找大量的Web頁面。它從一個簡單的Web頁面上開始執(zhí)行，然后通過其超鏈接在訪問其他頁面，如此反復理論上可以掃描互聯(lián)網上的所有頁面。

基于因特網的搜索引擎是Spider的最早應用。例如搜索巨頭Google公司，就利用網絡機器人程序來遍歷Web站點，以創(chuàng)建并維護這些大型數(shù)據(jù)庫。

網絡機器人還可以通過掃描Web站點的主頁來得到這個站點的文件清單和層次機構。還可以掃描出中斷的超鏈接和拼寫錯誤等。

3.2網絡機器人的結構分析

Internet是建立在很多相關協(xié)議基礎上的，而更復雜的協(xié)議又建立在系統(tǒng)層協(xié)議之上。Web就是建立在HTTP ( Hypertext Transfer Protocol ) 協(xié)議基礎上，而HTTP又是建立在TCP/IP ( Transmission Control Protocol / Internet Protocol ) 協(xié)議之上，它同時也是一種Socket協(xié)議。所以網絡機器人本質上是一種基于Socket的網絡程序。

3.2.1如何解析HTML

因為Web中的信息都是建立在HTML協(xié)議之上的，所以網絡機器人在檢索網頁時的第一個問題就是如何解析HTML。在解決如何解析之前，先來介紹下HTML中的幾種數(shù)據(jù)。

文本：除了腳本和標簽之外的所有數(shù)據(jù)

注釋：程序員留下的說明文字，對用戶是不可見的

簡單標簽：由單個表示的HTML標簽

開始標簽和結束標簽：用來控制所包含的HTML代碼

我們在進行解析的時候不用關心所有的標簽，只需要對其中幾種重要的進行解析即可。

超連接標簽

超連接定義了WWW通過Internet鏈接文檔的功能。他們的主要目的是使用戶能夠任意遷移到新的頁面，這正是網絡機器人最關心的標簽。

圖像映射標簽

圖像映射是另一種非常重要的標簽。它可以讓用戶通過點擊圖片來遷移到新的頁面中。

表單標簽

表單是Web頁面中可以輸入數(shù)據(jù)的單元。許多站點讓用戶填寫數(shù)據(jù)然后通過點擊按鈕來提交內容，這就是表單的典型應用。

表格標簽

表格是HTML的構成部分，通常用來格式化存放、顯示數(shù)據(jù)。

我們在具體解析這些HTMl標簽有兩種方法：通過JavaTM中的Swing類來解析或者通過Bot包中的HTMLPage類來解析，本人在實際編程中采用后者。

Bot包中的HTMLPage類用來從指定URL中讀取數(shù)據(jù)并檢索出有用的信息。下面給出該類幾種重要的方法。

HTMLPage構造函數(shù) 構造對象并指定用于通訊的HTTP對象

Public HTMLPage(HTTP http)

GetForms方法 獲取最后一次調用Open方法檢索到的表單清單

Public Vector getForms()

GetHTTP方法 獲取發(fā)送給構造函數(shù)的HTTP對象

Public HTTP getHTTP()

GetImage方法 獲取指定頁面的圖片清單

Public Vector getImage()

GetLinks方法 獲取指定頁面的連接清單

Public Vector getLinks()

Open方法 打開一個頁面并讀入該頁面，若指定了回調對象則給出所有該對象數(shù)據(jù)

Public void open(String url,HTMLEditorKit.ParserCallback a)

3.2.2 Spider程序結構

網絡機器人必須從一個網頁遷移到另一個網頁，所以必須找到該頁面上的超連接。程序首先解析網頁的HTML代碼，查找該頁面內的超連接然后通過遞歸和非遞歸兩種結構來實現(xiàn)Spider程序。

遞歸結構

遞歸是在一個方法中調用自己本身的程序設計技術。雖然比較容易實現(xiàn)但耗費內存且不能使用多線程技術，故不適合大型項目。

非遞歸結構

這種方法使用隊列的數(shù)據(jù)結構，當Spider程序發(fā)現(xiàn)超連接后并不調用自己本身而是把超連接加入到等待隊列中。當Spider程序掃描完當前頁面后會根據(jù)制定的策略訪問隊列中的下一個超連接地址。

雖然這里只描述了一個隊列，但在實際編程中用到了四個隊列，他們每個隊列都保存著同一處理狀態(tài)的URL。

等待隊列 在這個隊列中，URL等待被Spider程序處理。新發(fā)現(xiàn)的URL也被加入到這個隊列中

處理隊列 當Spider程序開始處理時，他們被送到這個隊列中

錯誤隊列 如果在解析網頁時出錯，URL將被送到這里。該隊列中的URL不能被移入其他隊列中

完成隊列 如果解析網頁沒有出錯，URL將被送到這里。該隊列中的URL不能被移入其它隊列中

在同一時間URL只能在一個隊列中，我們把它稱為URL的狀態(tài)。

以上的圖表示了隊列的變化過程，在這個過程中，當一個URL被加入到等待隊列中時Spider程序就會開始運行。只要等待隊列中有一個網頁或Spider程序正在處理一個網頁，程序就會繼續(xù)他的工作。當?shù)却犃袨榭詹⑶耶斍皼]有任何網頁時，Spider程序就會停止它的工作。

3.2.3如何構造Spider程序

在構造Spider程序之前我們先了解下程序的各個部分是如何共同工作的。以及如何對這個程序進行擴展。

流程圖如下所示：

IspiderReportable接口

這是一個必須實現(xiàn)的接口，可以通過回調函數(shù)接受Spider所遇到的頁面。接口定義了Spider向他的控制者發(fā)送的幾個事件。通過提供對每個事件的處理程序，可以創(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頁面，如果開發(fā)出高效的Spider程序是非常重要的。下面就來介紹下幾種提高性能的技術：

Java的多線程技術

線程是通過程序的一條執(zhí)行路線。多線程是一個程序同時運行多個任務的能力。它是在一個程序的內部進行分工合作。

優(yōu)化程序的通常方法是確定瓶頸并改進他。瓶頸是一個程序中最慢的部分，他限制了其他任務的運行。據(jù)個例子說明：一個Spider程序需要下載十個頁面，要完成這一任務，程序必須向服務器發(fā)出請求然后接受這些網頁。當程序等待響應的時候其他任務不能執(zhí)行，這就影響了程序的效率。如果用多線程技術可以讓這些網頁的等待時間合在一起，不用互相影響，這就可以極大的改進程序性能。

數(shù)據(jù)庫技術

當Spider程序訪問一個大型Web站點時，必須使用一種有效的方法來存儲站點隊列。這些隊列管理Spider程序必須維護大型網頁的列表。如果把他們放在內存中將會是性能下降，所以我們可以把他們放在數(shù)據(jù)庫中減少系統(tǒng)資源的消耗。

3.2.5網絡機器人的代碼分析

程序代碼實現(xiàn)如下：

package news;   
/**   
* 新聞搜索引擎   
* 計算機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;   
/**   
* 構造一個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)內部連接時調用，url表示程序發(fā)現(xiàn)的URL，若返回true則加入作業(yè)中，否則不加入。   
public boolean foundInternalLink(String url) {   
return false;   
}   
// 發(fā)現(xiàn)外部連接時調用，url表示程序所發(fā)現(xiàn)的URL，若返回true則把加入作業(yè)中，否則不加入。   
public boolean foundExternalLink(String url) {   
return false;   
}   
// 當發(fā)現(xiàn)其他連接時調用這個方法。其他連接指的是非HTML網頁，可能是E-mail或者FTP   
public boolean foundOtherLink(String url) {   
return false;   
}   
// 用于處理網頁，這是Spider程序要完成的實際工作。   
public void processPage(HTTP http) {   
System.out.println("掃描網頁：" + http.getURL());   
new HTMLParse(http).start();   
}   
// 用來請求一個被處理的網頁。   
public void completePage(HTTP http, boolean error) {   
}   
// 由Spider程序調用以確定查詢字符串是否應刪除。如果隊列中的字符串應當刪除，方法返回真。   
public boolean getRemoveQuery() {   
return true;   
}   
// 當Spider程序沒有剩余的工作時調用這個方法。   
public void spiderComplete() {   
}   
}  

3.3小節(jié)

在本章中，首先介紹了網絡機器人的基本概念，然后具體分析了Spider程序的結構和功能。在最后還結合具體代碼進行了詳細說明。

本人在編程中運用了Java技術，主要涉及到了net和io兩個包。此外還用了第三方開發(fā)包Bot（由Jeff Heaton提供的開發(fā)包）。

【編輯推薦】

1. 學習J2EE必須掌握的36個Package
2. solaris上開發(fā)J2EE應用中文問題的解決
3. J2EE框架的種類一覽
4. J2EE架構和過程
5. J2EE架構的6個最佳實踐