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

---- 一、引言

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

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

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

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

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

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

---- 搜索引擎的基本原理是通過網(wǎng)絡(luò)機器人定期在web網(wǎng)頁上爬行，然后發(fā)現(xiàn)新的網(wǎng)頁，把它們?nèi)』貋矸诺奖镜氐臄?shù)據(jù)庫中，用戶的查詢請求可以通過查詢本地的數(shù)據(jù)庫來得到。如yahoo每天會找到大約500萬個新的網(wǎng)頁。

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

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

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

---- 同時，有一類搜索引擎，它本身不用Robot去定期的采集網(wǎng)頁。象SavvySearch 和 MetaCrawler是通過向多個搜索引擎同時發(fā)出詢問并對結(jié)果進行綜合返回給用戶實現(xiàn)搜索功能。當(dāng)然實際上象SavvySearch能夠?qū)Ω鱾€搜索引擎的功能進行分析和比較，根據(jù)不同的用戶查詢提交給不同的搜索引擎進行處理，當(dāng)然用戶自己也可以指定利用哪一個搜索引擎。

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

---- 二、網(wǎng)絡(luò)Spider的實現(xiàn)描述

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

---- 2.1數(shù)據(jù)庫結(jié)構(gòu)

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

---- 1.字典表的建立，事實上這里是用文檔中有意義的單詞和它們的出現(xiàn)頻率來代表一個文檔。

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

    url_id    對每一個URL的唯一的ID號
    word      該URL中的經(jīng)過stem的單詞
    intag    該單詞在該網(wǎng)頁中的出現(xiàn)的次數(shù)

---- 2.存儲每一個URL信息的表

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

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

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

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

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

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

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

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

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

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

---- 2.3 和實現(xiàn)相關(guān)的主要類對象和功能描述下面的結(jié)構(gòu)是針對一個站點來說的。

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

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

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

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

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

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