胡朝暉（浙江大學(xué)計算機系）
王海瑛（寧波海峰塑化有限公司）

---- 一、引言

---- 隨著(zhù)Internet的飛速發(fā)展，人們越來(lái)越依靠網(wǎng)絡(luò )來(lái)查找他們所需要的信息，但是，由于網(wǎng)上的信息源多不勝數，也就是我們經(jīng)常所說(shuō)的"Rich Data, Poor Information"。所以如何有效的去發(fā)現我們所需要的信息，就成了一個(gè)很關(guān)鍵的問(wèn)題。為了解決這個(gè)問(wèn)題，搜索引擎就隨之誕生。

---- 現在在網(wǎng)上的搜索引擎也已經(jīng)有很多，比較著(zhù)名的有AltaVista, Yahoo, InfoSeek, Metacrawler, SavvySearch等等。國內也建立了很多的搜索引擎，比如：搜狐、新浪、北極星等等,當然由于它們建立的時(shí)間不長(cháng)，在信息搜索的取全率和取準率上都有待于改進(jìn)和提高。

---- Alta Vista是一個(gè)速度很快的搜索引擎，由于它強大的硬件配置，使它能夠做及其復雜的查詢(xún)。它主要是基于關(guān)鍵字進(jìn)行查詢(xún)，它漫游的領(lǐng)域有Web和Usenet。支持布爾查詢(xún)的"AND"，"OR"和"NOT"，同時(shí)還加上最相近定位"NEAR"，允許通配符和"向后"搜索（比如：你可以查找鏈接到某一頁(yè)的所有Web站點(diǎn)）。你可以決定是否對搜索的短語(yǔ)加上權值，在文檔的什么部位去查找它們。能夠進(jìn)行短語(yǔ)查詢(xún)而不是簡(jiǎn)單的單詞查詢(xún)的優(yōu)點(diǎn)是很明顯的，比如，我們想要查找一個(gè)短語(yǔ)"to be or not to be"，如果只是把它們分解成單詞的話(huà)，這些單詞都是屬于Stop Word，這樣這個(gè)查詢(xún)就不會(huì )有任何結果，但是把它當作一個(gè)整體來(lái)查詢(xún)，就很容易返回一些結果，比如關(guān)于哈姆雷特或者是莎士比亞等等的信息。系統對查詢(xún)結果所得到的網(wǎng)頁(yè)的打分是根據在網(wǎng)頁(yè)中所包含的你的搜索短語(yǔ)的多少，它們在文檔的什么位置以及搜索短語(yǔ)在文檔內部之間的距離來(lái)決定的。同時(shí)可以把得到的搜索結果翻譯成其他的語(yǔ)言。

---- Exite是稱(chēng)為具有"智能"的搜索引擎，因為它建立了一個(gè)基于概念的索引。當然，它所謂的"智能"是基于對概率統計的靈活應用。它能夠同時(shí)進(jìn)行基于概念和關(guān)鍵字的索引。它能夠索引Web,Usenet和分類(lèi)的廣告。支持"AND"，"OR"，"NOT"等布爾操作，同時(shí)也可以使用符號"+"和"-"。缺點(diǎn)是在返回的查詢(xún)結果中沒(méi)有指定網(wǎng)頁(yè)的尺寸和格式。

---- InfoSeek是一個(gè)簡(jiǎn)單但是功能強大的索引，它的一個(gè)優(yōu)點(diǎn)是有一個(gè)面向主題搜索的可擴展的分類(lèi)。你可以把你的搜索短語(yǔ)和相似的分類(lèi)目錄的主題短語(yǔ)相互參照，而那些主題短語(yǔ)會(huì )自動(dòng)加到你的查詢(xún)中去。使你的搜索有更好的主題相關(guān)性。同時(shí)它也支持對圖象的查詢(xún)。它能夠漫游Web,Usenet,Usenet FAQs等等。不支持布爾操作，但是可以使用符號"+"和"-"（相當于"AND"和"NOT"）

---- Yahoo實(shí)際上不能稱(chēng)為是一個(gè)搜索引擎站點(diǎn)，但是它提供了一個(gè)分層的主題索引，使你能夠從一個(gè)通常的主題進(jìn)入到一個(gè)特定的主題，Yahoo對Web進(jìn)行了有效的組織和分類(lèi)。比如你想要建立一個(gè)網(wǎng)頁(yè)，但是你不知道如何操作，為了在Yahoo上找到關(guān)于建立網(wǎng)頁(yè)的信息，你可以先在Yahoo上選擇一個(gè)主題：計算機和Internet，然后在這個(gè)主題下，你可以發(fā)現一些子主題，比如：Web網(wǎng)頁(yè)制作，CGI編程，JAVA，HTML，網(wǎng)頁(yè)設計等，選擇一個(gè)和你要找的相關(guān)的子主題，最終你就可以得到和該子主題相關(guān)的所有的網(wǎng)頁(yè)的鏈接。也就是說(shuō)，如果你對要查找的內容屬于哪個(gè)主題十分清楚的話(huà)，通過(guò)目錄查詢(xún)的方法要比一般的使用搜索引擎有更好的準確率。你可以搜索Yahoo的索引，但是事實(shí)上，你并沒(méi)有在搜索整個(gè)Web。但是Yahoo提供了選項使你可以同時(shí)搜索其他的搜索引擎，比如：Alta Vista。但是要注意的是Yahoo實(shí)際上只是對Web的一小部分進(jìn)行了分類(lèi)和組織，而且它的實(shí)效性也不是很好。

---- 搜索引擎的基本原理是通過(guò)網(wǎng)絡(luò )機器人定期在web網(wǎng)頁(yè)上爬行，然后發(fā)現新的網(wǎng)頁(yè)，把它們取回來(lái)放到本地的數據庫中，用戶(hù)的查詢(xún)請求可以通過(guò)查詢(xún)本地的數據庫來(lái)得到。如yahoo每天會(huì )找到大約500萬(wàn)個(gè)新的網(wǎng)頁(yè)。

---- 搜索引擎的實(shí)現機制一般有兩種，一種是通過(guò)手工方式對網(wǎng)頁(yè)進(jìn)行索引，比如yahoo的網(wǎng)頁(yè)是通過(guò)手工分類(lèi)的方式實(shí)現的，它的缺點(diǎn)是Web的覆蓋率比較低，同時(shí)不能保證最新的信息。查詢(xún)匹配是通過(guò)用戶(hù)寫(xiě)入的關(guān)鍵字和網(wǎng)頁(yè)的描述和標題來(lái)進(jìn)行匹配，而不是通過(guò)全文的匹配進(jìn)行的。第二種是對網(wǎng)頁(yè)進(jìn)行自動(dòng)的索引，象AltaVista則是完全通過(guò)自動(dòng)索引實(shí)現的。這種能實(shí)現自動(dòng)的文檔分類(lèi)，實(shí)際上采用了信息提取的技術(shù)。但是在分類(lèi)準確性上可能不如手工分類(lèi)。

---- 搜索引擎一般都有一個(gè)Robot定期的訪(fǎng)問(wèn)一些站點(diǎn)，來(lái)檢查這些站點(diǎn)的變化，同時(shí)查找新的站點(diǎn)。一般站點(diǎn)有一個(gè)robot.txt文件用來(lái)說(shuō)明服務(wù)器不希望Robot訪(fǎng)問(wèn)的區域，Robot 都必須遵守這個(gè)規定。如果是自動(dòng)索引的話(huà)，Robot在得到頁(yè)面以后，需要對該頁(yè)面根據其內容進(jìn)行索引，根據它的關(guān)鍵字的情況把它歸到某一類(lèi)中。頁(yè)面的信息是通過(guò)元數據的形式保存的，典型的元數據包括標題、IP地址、一個(gè)該頁(yè)面的簡(jiǎn)要的介紹，關(guān)鍵字或者是索引短語(yǔ)、文件的大小和最后的更新的日期。盡管元數據有一定的標準，但是很多站點(diǎn)都采用自己的模板。文檔提取機制和索引策略對Web搜索引擎的有效性有很大的關(guān)系。高級的搜索選項一般包括：布爾方法或者是短語(yǔ)匹配和自然語(yǔ)言處理。一個(gè)查詢(xún)所產(chǎn)生的結果按照提取機制被分成不同的等級提交給用戶(hù)。最相關(guān)的放在最前面。每一個(gè)提取出來(lái)的文檔的元數據被顯示給用戶(hù)。同時(shí)包括該文檔所在的URL地址。

---- 另外有一些關(guān)于某一個(gè)主題的專(zhuān)門(mén)的引擎，它們只對某一個(gè)主題的內容進(jìn)行搜索和處理，這樣信息的取全率和精度相對就比較高。

---- 同時(shí)，有一類(lèi)搜索引擎，它本身不用Robot去定期的采集網(wǎng)頁(yè)。象SavvySearch 和 MetaCrawler是通過(guò)向多個(gè)搜索引擎同時(shí)發(fā)出詢(xún)問(wèn)并對結果進(jìn)行綜合返回給用戶(hù)實(shí)現搜索功能。當然實(shí)際上象SavvySearch能夠對各個(gè)搜索引擎的功能進(jìn)行分析和比較，根據不同的用戶(hù)查詢(xún)提交給不同的搜索引擎進(jìn)行處理，當然用戶(hù)自己也可以指定利用哪一個(gè)搜索引擎。

---- 一個(gè)優(yōu)秀的搜索引擎必須處理以下幾個(gè)問(wèn)題：1 網(wǎng)頁(yè)的分類(lèi)2 自然語(yǔ)言的處理3 搜索策略的調度和協(xié)作 4 面向特定用戶(hù)的搜索。所以很多搜索引擎不同程度的使用了一些人工智能的技術(shù)來(lái)解決這些方面的問(wèn)題。

---- 二、網(wǎng)絡(luò )Spider的實(shí)現描述

---- 現在有很多文章對Web引擎做了大量的介紹和分析，但是很少有對它們的實(shí)現做一個(gè)詳細的描述，這里我們主要來(lái)介紹一個(gè)具有基本功能的Web引擎的實(shí)現。本文，我們以類(lèi)C++語(yǔ)言的形式來(lái)描述Web引擎如何采集網(wǎng)頁(yè)并存放到數據庫中的過(guò)程。同時(shí)描述了如何根據用戶(hù)輸入的關(guān)鍵字查詢(xún)數據庫并得到相關(guān)網(wǎng)頁(yè)的過(guò)程。

---- 2.1數據庫結構

---- 首先，我們要建立一個(gè)數據庫表用來(lái)存放我們得到的網(wǎng)頁(yè)。這里一般需要建立如下的表：

---- 1.字典表的建立，事實(shí)上這里是用文檔中有意義的單詞和它們的出現頻率來(lái)代表一個(gè)文檔。

---- 該表（WordDictionaryTbl）主要要包括三個(gè)字段，主要是用來(lái)存放和一個(gè)網(wǎng)頁(yè)相關(guān)的單詞的情況

    url_id    對每一個(gè)URL的唯一的ID號
    word      該URL中的經(jīng)過(guò)stem的單詞
    intag    該單詞在該網(wǎng)頁(yè)中的出現的次數

---- 2.存儲每一個(gè)URL信息的表

---- 該表(URLTbl)中主要的關(guān)鍵字段有：

  rec_id        每一條記錄的唯一的ID號
  status    得到該URL內容的狀態(tài)，比如HTTP_STATUS_TIMEOUT表示
            下載網(wǎng)頁(yè)的最大允許超時(shí)
  url        URL的字符串名稱(chēng)
  content_type      內容的類(lèi)型
  last_modified    最新的更改時(shí)間
  title            該URL的標題
  docsize          該URL的文件的尺寸
  last_index_time  最近一次索引的時(shí)間
  next_index_time  下一次索引的時(shí)間
  tag    對于網(wǎng)頁(yè)，用來(lái)表示它的類(lèi)型，比如：是text，或者是html，
                    或者是圖片等等
  hops              得到文件時(shí)候的曾經(jīng)失敗的次數
  keywords          對于網(wǎng)頁(yè)，和該網(wǎng)頁(yè)相關(guān)的關(guān)鍵字
  description      對于網(wǎng)頁(yè)，指網(wǎng)頁(yè)的內容的描述
  lang              文檔所使用的語(yǔ)言

---- 3.因為網(wǎng)頁(yè)中有很多單詞是一些介詞和語(yǔ)氣助詞或者是非常常用的常用詞，它們本身沒(méi)有多少意義。比如：英語(yǔ)中的about,in,at,we,this等等。中文中的如"和"，"一起"，"關(guān)于"等等。我們統一的把它們稱(chēng)為停止詞（stop word）。所以我們要建立一個(gè)表，來(lái)包括所有這些停止詞。該表(StopWordTbl)主要有兩個(gè)字段。
word char(32)    表示那些停止詞
lang char(2)      表示所使用的語(yǔ)言

---- 4.我們要建立一個(gè)關(guān)于robot的表，我們在前面說(shuō)過(guò)，所有的網(wǎng)站一般都有一個(gè)robot.txt文件用來(lái)表示網(wǎng)絡(luò )上的robot可以訪(fǎng)問(wèn)的權限。該表(RobotTbl)主要有以下字段。
    hostinfo          Web站點(diǎn)主機的信息
    path              不允許robot訪(fǎng)問(wèn)的目錄

---- 5.建立我們需要屏蔽的那些網(wǎng)頁(yè)(比如一些內容不健康的或者沒(méi)有必要去搜索的站點(diǎn))的一張表(ForbiddenWWWTbl)，主要的字段就是網(wǎng)頁(yè)的URL。

---- 6.另外我們需要建立一個(gè)我們所要得到的文件類(lèi)型的表(FileTypeTbl)，比如，對于一個(gè)簡(jiǎn)單的Web搜索引擎，我們可能只需要得到后綴為.html，htm，.shtml和txt的類(lèi)型文件。其他的我們只是簡(jiǎn)單的忽略它們。主要的字段就是文件的類(lèi)型和說(shuō)明。

---- 其中關(guān)于停止詞的表的內容是我們要實(shí)現要根據各種語(yǔ)言的統計結果，把那些意義不大的單詞放進(jìn)去。關(guān)于文檔單詞、URL和Robot的表的內容都是在獲取Web網(wǎng)頁(yè)的時(shí)候動(dòng)態(tài)增加記錄的。

---- 2.2 具體網(wǎng)頁(yè)獲取算法描述

---- 具體的網(wǎng)頁(yè)的獲取步驟是這樣的：

---- 我們可以設定我們的搜索程序最大可以開(kāi)的線(xiàn)程的數目，然后這些線(xiàn)程可以同時(shí)在網(wǎng)上進(jìn)行搜索，它們根據數據庫中已有的關(guān)于網(wǎng)頁(yè)的信息，找出那些需要更新的網(wǎng)頁(yè)（如何判斷哪些網(wǎng)頁(yè)需要更新是一個(gè)值得研究的過(guò)程，現在有很多啟發(fā)式和智能的算法，基本上是基于統計規律進(jìn)行建模。最簡(jiǎn)單的當然是設定一個(gè)時(shí)間范圍，在某個(gè)時(shí)間范圍以前的網(wǎng)頁(yè)被重新去搜索一遍），然后判斷那些網(wǎng)頁(yè)是否在屏蔽表中，如果是的話(huà)，就從關(guān)于URL的表中刪除該條記錄。否則，我們就到相應的WWW站點(diǎn)去得到URL指定的文件(這里需要注意的是根據不同的URL的特點(diǎn)，需要使用不同的協(xié)議，比如對于FTP站點(diǎn)要采用FTP協(xié)議，對于HTTP站點(diǎn)要采用HTTP協(xié)議，新聞?wù)军c(diǎn)要采用NNTP協(xié)議等等)事實(shí)上，我們先得到關(guān)于該網(wǎng)頁(yè)的頭信息，如果該網(wǎng)頁(yè)的最新修改時(shí)間和我們最近提取的時(shí)間是一樣的話(huà)，表示該網(wǎng)頁(yè)內容沒(méi)有任何更新，則我們就不必去得到它的內容，只需要修改最近一次更新它的時(shí)間為當前的時(shí)間就可以了。如果該網(wǎng)頁(yè)最近做了修改，我們就要得到該網(wǎng)頁(yè)，并對它的內容進(jìn)行分析，主要要包括和它相關(guān)的鏈接，把它們加到相應的數據庫中，同時(shí)判斷網(wǎng)頁(yè)所包含的各種其他的文件，如文本文件、圖形文件、聲音文件和其他多媒體文件是否是我們所需要的文件，如果是的話(huà)，就把它加到我們響應的數據庫中。同時(shí)要根據網(wǎng)頁(yè)的內容提取所有的有意義的單詞和它們的出現的次數，放到相應的數據庫中。為了更好的描述這個(gè)過(guò)程，我們來(lái)看跟這個(gè)過(guò)程相關(guān)的主要的幾個(gè)對象和數據結構。對象主要是針對三個(gè)層次來(lái)講的。第一層是針對WWW服務(wù)器，第二層是針對每一個(gè)頁(yè)面，第三層是針對每一個(gè)頁(yè)面的全文的索引。

---- 2.3 和實(shí)現相關(guān)的主要類(lèi)對象和功能描述下面的結構是針對一個(gè)站點(diǎn)來(lái)說(shuō)的。

    Class  CServer {
    主要的屬性有：
    char *url;            //WWW站點(diǎn)的URL名稱(chēng)
    char *proxy;          //使用的代理的名稱(chēng)
    char *basic_auth;      //進(jìn)行基本的HTTP認證
    int  proxy_port;      //代理的端口號
    int  period;          //再次索引的周期
    int  net_errors;      //網(wǎng)絡(luò )連接不通的次數
    int  max_net_errors;  //可以允許的最大的網(wǎng)絡(luò )錯誤
    int  read_timeout;    //下載文件允許的最大的延遲
    int  maxhops;          //表示URL可以最大跳轉的深度
    int  userobots;        //是否遵守robot.txt中的約定
    int  bodyweight;  // 在< body >....< /body >之間的單詞的權重
    int  titleweight; // 在< title >....< /title >之間的單詞的權重
    int  urlweight;  // 在文檔的URL中的單詞的權重
    int descweight;//在    < META
NAME="Description"        Content="..." >之間單詞的權重
    int  keywordweight; //在< META NAME="Keywords" Content="..." >
  之間的單詞的權重

---- 主要方法有：
FindServer();//用來(lái)查找該服務(wù)器是否存在并可以連接
FillDefaultAttribute() //用來(lái)針對所有的WWW服務(wù)器填寫(xiě)默認的屬}；

以上的對象中的成員變量是和一個(gè)站點(diǎn)相關(guān)的參數的設置，我們對所有的站點(diǎn)有一個(gè)默認的設置，但是可以對某些站點(diǎn)做一些特殊的設置。這些設置可以在配置文件中設定。
---- 下面是關(guān)于文檔的結構的主要的數據成員：

Class CNetDocument
    主要屬性有：
    int    url_id; //該URL的ID號
    int    status;  //獲取該文檔時(shí)候的狀態(tài)
    int    size;  //文檔的尺寸
int    tag;  //和該文檔相關(guān)的標簽，表示該文檔是
HTML，TEXT或者是其他類(lèi)型
    int    hops;    //URL跳轉的次數
    char    *url; //和該文檔相關(guān)的URL的名稱(chēng)
    char    *content_type;      //該內容的類(lèi)型
    char    *last_modified;    //最近一次的更新時(shí)間
    char    *title;            //該文檔的標題
    char    *last_index_time;  //上次索引的時(shí)間
    char    *next_index_time;  //下次索引的時(shí)間
    char    *keywords;          //該文檔中的關(guān)鍵字
    char    *description;      //該文檔的描述

  主要方法有：
  FillDocInfo(…) //根據數據庫，得到該文檔相關(guān)信息
  AddHerf(…)    //加入網(wǎng)頁(yè)中存在的新的鏈接的網(wǎng)址
  DeleteURL(…)  //刪除一個(gè)存在的網(wǎng)址
  CanGetThisURL(…) //根據配置決定是否去得到該網(wǎng)頁(yè)
  //下面三個(gè)方法是根據不同的URL，用不同的協(xié)議去獲得文檔
  NNTPGet(…)     
  FTPGet(….)
  HTTPGet(….)
  ParseHead(…)  //如果是HTTP協(xié)議得到的話(huà)，分析頭信息
  ParseMainBody(…)    //對獲得的文檔的主體進(jìn)行分析
  ServerResponseType (….)  //得到服務(wù)器端的響應消息
  UpdateURLDB(….)  //更新的數據入庫
} ；

---- 事實(shí)上，我們在要提取一個(gè)網(wǎng)頁(yè)的時(shí)候，都要建立一個(gè)CNetDocument對象，然后再對這個(gè)網(wǎng)頁(yè)進(jìn)行分析的時(shí)候，把相關(guān)的內容放到這個(gè)CNetDocument的成員變量里面。下面是關(guān)于頁(yè)面全文索引的結構的主要數據成員：
Class CIndexer {
主要屬性有：
  char    *url;      //我們要處理的文檔相關(guān)的URL的名稱(chēng)
  int mwords;      //  我們事先設定的一個(gè)網(wǎng)頁(yè)的最大的單詞數目
    int nwords;          // 實(shí)際的得到的單詞的數目
    int swords;          // 我們已經(jīng)排序的單詞的數目
    WORD *Word;      //所有單詞的內容
    char *buf;      //我們?yōu)槲臋n所分配的空間
主要方法有：
  InitIndexer(…)    //進(jìn)行初始設置和分配