一個Ｗｅｂ社區搜索引擎系統

摘 要：在分析Web社區搜索資源分散特點的基礎上，運用Web抓取器、向量空間模型和相關性排序等技術設計了Web社區搜索引擎的體系結構，實現了一個Web社區搜索引擎系統——ChinalabSearch。根據對系統的性能評估，系統滿足Web社區的搜索要求，提高了在社區內查找信息的效率，為組織間的合作提供了方便。

關鍵詞：Web社區；搜索引擎；信息獲取；ChinalabSearch

中圖法分類號：TP391.3文獻標識碼：A

文章編號：1001—3695(2007)02—0275—04

隨著Web的發展，Web站點的數量不斷增加，公共可以訪問的Web站點的數量從1998年的140多萬個增長到2002年的300多萬個[1]，越來越多的組織和企業擁有自己的網站。同時一些組織在某一個場合下擁有共同的目標，需要合作完成一個較大的任務時，這些組織傾向于組織一個Web社區為合作、交流和共享信息提供環境，在Web社區環境中共享信息變得更加簡單。Web社區中包含的信息主要有兩種：①社區成員在社區網站中的討論內容和上傳到社區網站的文檔等信息；②不同組織獨立的網站，在這些網站中存在更多的相關信息。對第①種信息，現有的站內搜索技術和門戶提供的搜索功能能夠很好地實現站內的搜索，為站內文檔信息的訪問提供方便。而Web社區中多個獨立的組織和企業內部網絡相比更加松散，內容也更加豐富，站內搜索是面向企業內部網絡(Intranet)，無法解決Web社區中各組織的網站的搜索。本文提出的系統主要解決由多個獨立組織組成的Web社區內的搜索問題。本文將闡述通用的Web搜索引擎和站內搜索引擎的發展現狀，這些技術要解決的問題與Web社區的搜索有很大的相似之處。

1 相關工作

Web信息獲取一直都是研究的熱點之一，在這方面既產生了很多的理論成果，也有很多成熟的系統。搜索引擎通過將Web頁面抓取到本地計算機上建立全文索引，然后將Web用戶的查找需求與所有抓取的Web頁面匹配，返回一個相關Web頁面的列表。主要有以下兩種類型的搜索引擎：

（1）Web搜索引擎。它試圖為整個Web建立索引。系統首先用抓取器(Crawler)將Web上的頁面抓取到本地計算機上，抓取的內容一般只涉及公共Web(Public Web)；然后為這些頁面建立全文索引，將索引Web頁面的索引存儲在索引庫中，并且定期更新。Web用戶將查詢請求發送給引擎的查詢(Query)部件，查詢部件在索引庫中進行匹配，返回一個相關頁面的列表，并且將這個列表提交給排序部件（Ranker），排序部件負責將頁面按照相關的程度排序。Web搜索引擎系統很龐大，如Google就為80億網頁建立了索引，并且不斷更新這些索引。為了確保建立索引和大量查詢（每天的查詢量為1.1億次[4]）的效率，Google采用了分布式集群的體系結構，極大地提高了系統的性能。在對返回頁面的排序上，Google除了考慮相關的程度外，還考慮了整個Web鏈路結構的特點[5]。社區Web是若干個Web站點的集合，現有的通用Web搜索系統的搜索定制很強大，能夠實現搜索單個網站、域名內網站和某一種語言的網站的定制，但都還沒有提供在一個Web社區內的搜索的功能，所以現在還不能簡單地利用通用Web搜索引擎提供的功能解決社區Web的問題。

（2）站內搜索引擎[2]。它對單個網站或者局域網內的內容建立索引，可以提高網站訪問者訪問網站的效率。簡單的站內搜索引擎和通用的Web搜索引擎沒有很大的區別，只是將搜索的范圍縮小，較為復雜的站內搜索充分考慮了單個網站的資源特點，可以引入領域知識來提高搜索的性能，如ATT的FindUR就引入了語義信息提高用戶在ATT網站上查找信息的效率，取得了很好的效果[6]。Web社區網站的分布很松散，也無法利用站內搜索可以提供的語義信息，顯然站內搜索無法實現Web社區的搜索需求。

2 Web社區搜索引擎

2.1 系統體系結構

Web社區的搜索引擎框架如圖1所示。在該體系結構中，主要有抓取器(Crawler)、索引(Indexer)、搜索(Searcher)、相似度計算(Similarity)和排序(Ranker)等重要組件。其中，抓取器負責從Web社區中獲取符合要求的文檔；索引部件負責對所有的文檔按照向量空間模型建立索引；搜索部件負責根據用戶輸入的關鍵詞在索引庫中搜索符合的文檔列表；相似度計算部件負責搜索部件返回的文檔與查詢的相似度的計算；排序部件則根據相似度對返回的文檔進行排序，將相似度最大的文檔排在返回文檔列表的第一個。

文檔庫（Document Repository）存儲所有文檔，并且不斷更新文本庫系統的詞匯表（Word Table）。搜索引擎系統的詞匯表存儲系統中所有出現過的詞和術語，在系統運行之前就已經形成了初步的術語表，在對文檔庫中的文檔進行處理時不斷地更新詞匯表，對中文文檔還要采用中文分詞技術[7]。

索引庫(Index Repository)中存儲的是所有文檔的反索引[8]。文檔庫的反索引是一些列表的集合，對每一個術語有一個列表，這個列表中存儲包含有這個術語的文檔的相關信息，這些信息稱為Posting[8]。在最簡單的情況下，Posting中應該包含有文檔的唯一標識符和術語在文檔中的位置；在稍微復雜一點的情況下，不僅要考慮術語在文本出現的位置，而且術語周圍的環境對術語的權重和搜索結果的排序都有影響，此時反索引的信息就更復雜。 查詢時，Web用戶通過向搜索中提交關鍵詞，搜索部件在索引庫中查詢，將返回的文檔列表提交給相似度計算部件，相似度計算部件計算返回的文檔和查詢相似的程度，最后排序部件利用這些相似程度進行返回結果的排序，并將排序后的文檔列表返回給Web用戶。

2.2 網絡抓取器

網絡抓取器負責從Web上搜集頁面，抓取器在運行過程中需要維護一個URI隊列。首先輸入一個種子URI初始化這個隊列，然后獲取這個URI的內容，將返回內容存儲到系統的文檔庫中；同時從返回的內容中提取出這個頁面中含有的URI，將還沒有處理過的URI加入待處理的隊列中，繼續處理隊列中的URI，直到隊列為空或其他的終止條件。在抓取過程中還需要將已經處理的URI存儲到數據庫中，將從頁面中提取的URI與數據庫中存儲的進行比較，將未處理過的放入待處理隊列中[9]。具體實現的過程中可以使用多個種子URI，復雜的抓取器還會對隊列中的URI進行排序，從而首先抓取最重要的URI并且對不感興趣的頁面進行過濾[9]。

2.3 向量空間模型和相關度計算

這種相似度計算是通過考查特征向量的余弦夾角實現的，還有不同的計算方式可以參考文獻

2.4 搜索引擎的性能評估標準

在信息獲取和Web搜索引擎的研究中，除考慮系統的運行時間和空間需求外，對系統的性能評估主要采用兩個標準，即準確率和召回率[10]。準確率返回的是認為相關的文檔與所有返回文本的比值，準確率p的計算公式為p=返回的正確文檔數返回的所有文檔數；召回率返回的是認為相關的文檔與整個文檔集合中所有相關文檔的數目的比值，召回率r的計算公式為r=返回的正確文檔數應該要返回的文檔數。在計算準確率p時一般是采用人工標記返回文檔的方法，如人工地找出前20個文檔中與查詢相關的文檔數n，計算p=n/20為準確率。由于很難計算系統文檔庫中含有的相關文檔的數目，所以召回率在Web搜索系統中很少使用。

3 系統實現和性能評估

Chinalab是由160多個國家重點實驗室組成的Web社區，大部分實驗室均擁有獨立的網站，ChinalabSearch實現了在Chinalab社區內的信息檢索。筆者利用開源的Web抓取器，將Web頁面收集到本地計算機，提取純文本；在將文本進行預處理的基礎上，將文本表示為向量，實現了搜索引擎系統。為了防止一個實驗室返回的頁面占據返回結果的大多數，系統將搜索結果按照實驗室組織，這樣還可以實現單個實驗室范圍內的搜索。同一個實驗室內部的頁面結果按照相關度排序，相關度的計算按照式（2）進行。

3.1 系統實現

系統實現時的主要數據結構有Document，Field，Index，Term，Posting等。其中，Document類對應于文檔庫中存儲的文檔，Document的屬性與HTML頁面的屬性類似，包括URI和頁面類型等；這些屬性和屬性的值構成一個Field，一個Document含有一個Field的列表。Term類對應于詞匯表中的詞匯，需要存儲詞匯的文本和用來計算詞匯在文本中的權重的信息（如出現的文本數）；Index類對應于一個Term的反索引，含有Term在文本中出現的信息，對每一個文本有一個Posting存儲Term的出現，Posting中存儲Term的出現位置之類的信息。這五個主要類的關系用UML描述，如圖2所示。在建立索引的過程中系統首先利用Crawler將網頁抓取到本地計算機，存儲(Store)在頁面庫中，通過索引部件為頁面建立索引(Indexing)，存儲在索引庫中。具體的流程圖如圖3所示。

在搜索的過程中，Web用戶通過瀏覽器輸入要查詢內容的關鍵詞，搜索部件在索引庫中查找所有包含有這些關鍵詞的頁面，將這些頁面提交給相似度計算部件計算查詢和返回頁面的相似度，相似度計算部件將計算出的所有相似度提交給排序部件，排序部件依據相似度對返回的所有頁面進行排序，得到最后返回的結果，具體流程如圖4所示。3.2 對搜索系統的性能評估

系統的用戶界面與Google[6]相似，搜索“研究方向”的界面如圖5所示。對搜索的結果按實驗室分組，每頁顯示十個實驗室的第一頁，如果要在同一個實驗室中查找更多的內容，則在“更多內容”中瀏覽本實驗室的所有結果。

筆者收集了Chinalab社區內的Web用戶有可能感興趣的查詢請求，這些請求用相應的關鍵詞描述，一般都只有一到兩個關鍵詞。將這些請求提交給ChinalabSearch，對返回的結果進行人工分析，并且計算對某一個查詢的正確率p。

通過對查詢結果分析筆者發現，系統對返回結果較少的查詢效果較好，這主要是由于對那些返回結果較多的查詢，用空間向量模型計算頁面和查詢相似度時效果并不是很好，主題最相近的頁面在計算相似度時反而有可能較小，將相關度較小的頁面排在返回結果的最前端導致用戶根本沒有耐心去瀏覽所有的結果。對前面四個查詢，筆者的目標是要定位所有實驗室都有的內容，希望對Chinalab社區內的資源有一個初步的了解，從得到的結果來看，大部分返回的內容都是有效的。后面的四個查詢則是希望定位到具體感興趣的內容，從返回的結果來看，符合查詢要求。

系統在CPU為奔騰2.8GHz，內存為1GB，操作系統為Windows 2000的計算機上運行良好，系統時間延遲控制在1s以內，個別的數據量較大和返回結果較多的查詢延遲較大，而返回結果較少的大多數查詢延遲很小。

3.3 ChinalabSearch和Google的性能比較

通過在Google中搜索相應的內容，筆者將ChinalabSearch和Google在Chinalab Web社區內的搜索作了初步的比較。Google的搜索范圍是針對整個Web，而ChinalabSearch的搜索范圍本身是在國家重點實驗室的范圍內，所以在Google中查找相關內容時需要將搜索范圍通過添加關鍵詞的形式（在Google中不能通過限制域名的方式實現Web社區內的搜索）限制在國家重點實驗室這個Web社區之內（如在Google中搜索“研究項目”，“國家重點實驗室”對應在ChinalabSearch中搜索“研究項目”）。

Google和ChinalabSearch在查詢正確率和時間延遲上的對比可以由圖6表示。對第一個搜索(國家重點實驗室)，Google的較優，Google列出了所有國家重點實驗室的首頁，并且排序很好。這主要是由于Google采用了較為復雜的返回結果排序算法PageRank[8]，這種排序算法不僅考慮返回頁面和查詢的相似度，而且主要考慮返回頁面在整個Web中的重要程度，將最重要的頁面排在首位，當返回結果較多而導致在按相似度排序性能較差的情況下，采用PageRank能夠極大地提高排序性能。在搜索其他關鍵字（新聞動態、研究方向和研究項目）時，ChinalabSearch都能直接定位到相應的頁面，而Google返回的結果中，仍然返回很多首頁并且排序在最前面。這是由于首頁中有這些關鍵詞的超鏈接，但實際上首頁并不是最相關的頁面，將首頁排序在最前面則是由于PageRank算法使相關度較小的重要頁面排在最前面，產生了負面影響。在搜索最后的三個關鍵詞時，Google返回的結果很多，但排在最前面的結果的相關性與ChinalabSearch相比較差，由于ChinalabSearch按照實驗室分組，每一組的第一個是本實驗室中最相關的頁面，所以在排序上比Google的要好一些。

在系統延遲的比較中，Google在平均性能上要優于ChinalabSearch，這主要是由于Google采用了性能更優的服務器和多種優化查詢時間的手段（如緩存）。所以大部分情況下，Google在要查找的范圍遠大于Chinalab的情況下，仍然有很快的系統響應時間，但當返回結果較少時，ChinalabSearch對結果進行排序的性能比較快時，返回時間也比較小。

4 結論和將來的工作

專門為Web社區設計的搜索引擎給Web社區內的信息查找提供了方便，為社區內的用戶和組織更好地合作和共享信息提供了便利。在這個框架下，利用通用的檢索組件和抓取組件可以構造Web社區的搜索引擎系統，這個框架具備實用的價值。在將ChinalabSearch和Google的返回結果相比較以后，筆者發現Google采用的PageRank算法在處理返回結果較多的情況下效果優于ChinalabSearch，而ChinalabSearch由于本身數據范圍較小，采用的排序算法比較簡單，在返回結果較少的情況下優于Google的搜索結果。另外由于Google是搜索整個Web的內容，當在整個Web中相關內容比較多時（如新聞動態、研究項目、計算機科學），Google的搜索結果較差，ChinalabSearch由于搜索范圍的限制效果較好。ChinalabSearch搜索系統已經部署在國家重點實驗室網上合作研究平臺中，給平臺中的查找信息提供了較大的幫助。當返回結果較多時，利用相關性排序的方法對返回結果進行排序效果已經不是很好，用戶雖然可以通過進一步精確查詢得到更好的結果，但在系統方面則需要通過引入更加有效的排序策略來提高系統的運行性能。另外，在極少數返回結果數量在1 000以上的情況下，系統的延遲時間很長，通過引入并行的索引和搜索機制可以優化系統查詢的性能。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。