基于多Agent的搜索引擎設計與實現

摘要:搜索引擎的出現改變了人們獲取信息的方式，利用搜索引擎可以快速地找到需要的信息，為我們在Internet上獲取信息提供了一種有效的手段。但隨著Internet的發展和網上信息量的激增，人們在使用中卻發現要準確、快速地查找自己所需的信息是越來越困難。文章依據搜索引擎、Agent技術，提出了基于多Agent技術的智能搜索引擎概念，能夠有效地提高搜索引擎的搜索質量和用戶服務，為解決當前搜索引擎存在的一些問題提供了一種新的有效的方法。

關鍵詞:搜索引擎，Agent，智能特征，智能搜索

中圖分類號:TP18文獻標識碼:A文章編號:1009-3044(2010)05-1186-03

Design and Reallization of Search Engine Based on Multi-Agent

YU La-sheng， TANG Xu-rong

(School of Information Science and Engineering of Central South University， Changsha 410083， China)

Abstract: The emergence of search engines has changed the way that people obtain to information.And search engines can quickly find the information needed for us on the Internet as an effective means. But with the Internet’s development and proliferation of the amount of information online， it was increasingly difficult that the information was found to accurately and quickly. Articles based on search engine， Agent technology， proposed the concept of intelligent search engines based on multi-Agent technology.It can effectively improve the search engine’s search quality and customer service， in order to resolve the current number of problems in search engine provides a new and effective method.

Key words: search engines; agent; intelligence features; intelligence search

隨著信息科技的進步和互聯網的日益普及，人類正在進行信息史上巨大的一項工程，將現實世界現有的信息，諸如報紙、期刊、書籍、專利文獻等，都放到網絡上去，同時也不停地在網絡上生產出數不勝數的新信息。整個網絡正在堆積成一個前所未有的超級大型數據庫。但是它們卻沒有建立起一條有效的信息提供途徑。網民對信息的需求越來越大，同時也越來越沒有耐心。

搜索引擎的出現改變了人們獲取信息的方式，利用搜索引擎可以快速地找到需要的信息。目前，搜索引擎是互聯網核心技術之一，伴隨互聯網的普及和網上信息的爆炸式增長，它越來越引起人們的重視。搜索引擎的出現為我們在Internet上獲取信息提供了一種有效的手段，但隨著Internet的發展和網上信息量的激增，人們在使用中卻發現要準確、快速地查找自己所需的信息是越來越困難。

為進一步提高搜索引擎的搜索質量和用戶服務[1]，將人工智能的成果引入到搜索引擎中也就成為一種趨勢。智能Agent技術作為近年來AI領域的研究熱點，因其自主性、反應性、適應性和社會性等特點正得到廣泛的應用[2-3]。它不僅能作用于自身，而且還可以作用于環境，并能接受環境的反饋的信息，重新評估自己的行為[4-6]，同時，它能與其他Agent協同工作。Agent技術的出現為這些問題的解決提供了一種新的有效的方法。

1 搜索引擎及Agent技術

1.1 搜索引擎技術

所謂搜索引擎(Search Engines)是一個對互聯網上的信息資源進行搜集整理，然后供你查詢的系統，它包括信息搜集、信息整理和用戶查詢三部分。一個好的搜索引擎系統還應能夠對用戶提出的搜索請求進行處理，同時應能夠將搜索的結果進行合理的組織，提交給用戶。

1)搜索引擎分類:現在Internet上已有數千個能提供檢索服務的站點，這些站點的搜索引擎在收錄的范圍、內容、檢索方法上都各有不同，但總的來看，可以將其分成三大類型:基于robot的搜索引擎、目錄和元搜索引擎。

基于robot的搜索引擎:基于robot的搜索引擎不是靠人工發現和甄別信息，而是由一個被稱作“robot”的計算機程序在網頁中爬行，依據一定的網絡協議在Internet中發現、加工、整理信息，并為用戶提供檢索服務。

目錄式搜索引擎:與基于Robot的搜索引擎所不同的是，目錄的數據庫是依靠專職編輯或志愿人員建立起來的，這些編輯人員在訪問了某個web站點后撰寫一段對該站點的描述，并根據站點的內容和性質將其歸為一個預先分好的類別，把站點的URL和描述放在這個類別中，當用戶查詢某個關鍵詞時，搜索軟件只在這些描述中進行搜索。

元搜索引擎:又叫做Multiple Search Engine，它的特點是本身并沒有存放網頁信息的數據庫，當用戶查詢一個關鍵詞時，它把用戶的查詢請求轉換成其它搜索引擎能夠接受的命令格式，并行地訪問數個搜索引擎采查詢這個關鍵詞，并把這些搜索引擎返回的結果經過處理后再返回給用戶。

2)搜索引擎工作原理:

搜索引擎并不真正搜索互聯網，它搜索的實際上是預先整理好的網頁索引數據庫。搜索引擎，也不能真正理解網頁上的內容，它只能機械的匹配網頁上的文字。搜索引擎的原理，可以看作三步:

從互聯網上抓取網頁，利用能夠從互聯網上自動收集網頁的Spider系統程序，自動訪問互聯網，并沿著任何網頁中的所有URL爬到其它網頁，重復這過程，并把爬過的所有網頁收集回來。

建立索引數據庫，由分析索引系統程序對收集回來的網頁進行分析，提取相關網頁信息，根據一定的相關度算法進行大量復雜計算，得到每一個網頁針對頁面文字中及超鏈中每一個關鍵詞的相關度(或重要性)，然后用這些相關信息建立網頁索引數據庫。

在索引數據庫中搜索排序，當用戶輸入關鍵詞搜索后，由搜索系統程序從網頁索引數據庫中找到符合該關鍵詞的所有相關網頁。因為所有相關網頁針對該關鍵詞的相關度早已算好，所以只需按照現成的相關度數值排序，相關度越高，排名越靠后。

1.2 Agent技術

Agent的概念來自于分布式人工智能(Distributed Artificial Intelligent)，其定義如下:Agent是存在于某一環境中的實體，能夠感知環境，接收來自環境的消息，并且做出反應，進而能夠反作用于環境。從最終用戶角度看，Agent是用戶的代理和助手，代表和幫助用戶實現其意圖、完成某些任務。從系統角度看，Agent作為一個抽象實體，實現形式可以是軟件，也可以是硬件(需要軟件的控制)，一般研究的是軟件Agent。

1)Agent的特征:

自主性(autonomy):Agent有屬于自身的資源(數據)和行為控制機制(處理過程)，可以在沒有人或其它Agent直接干預的情況下運作。而且根據其內部狀態和感知到的環境信息，對自己的行為和內部狀態有某種控制能力。

社交性(sociability):Agent和其它Agent(包括人)通過某種交流語一言進行交互，以獲得協調和合作。

反應性(reactivity):Agent觀察其環境(可能是物理世界、圖形世界、一系列其它AgentInternet等)，并在一定時間在做出反應，以改變該環境。

主動性(pro-activity):Agent不僅能夠對環境做出反應，而且能夠接受某些提示信息，采取主動行動，體現出面向目標的行為。

智能性(intelligence):Agent具有一定程度的智能，能完成包括推理到自學習等一系列的智能行為。

通信性(Communicability):Agents之間(包括人)可以交換信息。

2)Agent之間的通信機制:

當多個Agent組成Multi-Agent系統時，Agent之間就出現了相互通信與協調問題。Agent之間的通信所傳遞的不能僅僅是字符流或二進制數流，因為Agent是有一定智能和自主性的實體，它們之間的通信更應該在知識層上進行表述、理解和交流。因此Agent通信語言ACL(Agent Communication Language)就應運而生了，它是Agent之間進行知識共享和知識交換的協議性語言，也是Multi-Agent系統的重要組成部分。

Agent具有的功能模塊可以分成3組:表達模塊、通信模塊和其他的應用模塊。如圖1所示。

2 基于多Agent智能搜索引擎設計及實現

2.1 總體設計方案

基于Agent的系統采用了智能和自主的問題求解Agent，通過自動化的工具把用戶需要的信息自動地搜索并提交給用戶。在此設計的新一代搜索引擎，具有搜索引擎和信息過濾的兩大功能，具有個性化的特點，能夠自主地建立用戶興趣模型，通過自帶的搜索引擎提交用戶興趣，并返回過濾后的信息。從技術實現來看，本次設計實質是在傳統的搜索引擎中加入了智能Agent機制，并在用戶端形成了一個個性化層，通過用戶和用戶界面、用戶界面和搜索引擎、信息過濾Agent和搜索引擎、用戶界面和信息過濾Agent之間的交互機制，智能地適應用戶興趣的變化和環境的變化。其基本的體系結構如圖2所示。

2.2 以“網頁智能特征提取”為標志的網頁分析Agent

網頁與普通文檔不同，其所含信息體現在下面這三個部分:網頁正文(含標題)、網頁所含的超文本標記、網頁間的超鏈接，如圖3所示:

圖3 網頁信息體系結構

網頁分析Agent結構如圖4所示。

圖4 網頁分析Agent結構

網頁進行特征提取首先要對超文本進行網頁過濾，過濾處理后分別獲得網頁正文、超文本標記和超鏈接信息。過濾后的網頁正文與普通文檔一樣。對其的處理即可轉化為對中文文檔的處理。其步驟如下:

1) 分詞詞典的建立:進行中文文檔處理，首先要進行的就是建立一個比較好的分詞詞典。在我們的背景系統中，出于簡單方便的考慮，我們建立一個證券信息類分詞詞典，其中內容相對比較固定，主要包括了股票名稱、股票代碼和一些常用的證券詞匯。

2) 標記信息的特征提取:超文本是一種半結構數據，由標記符、所標記的內容、標記結束符等標記構成，標記起始符中常含有標記元素的屬性。在此我們提取出有效的特征信息。

3 基于多Agent智能搜索引擎實現

有許多現有語言可以對基于Agent的應用程序進行原形構造，但不能說它們都是Agent語言，并不是所有的語言都為有效地實現智能Agent提供了足夠的功能。Wooldridge和Jennings認為，Agent語言是一個可以用來編制符合Agent理論家們所給出的概念的硬件和軟件的計算機系統的語言，它應該包括與Agent一致的一些結構。一些學者總結了面向Agent編程語言的適用標準。

根據這一標準，由于Java憑借平臺獨立性和安全性等優勢，比起任何其它現有語言都更適合開發Agent系統，更符合面向Agent編程語言的適用標準。

3.1 二維向量表的構造

在對一個HTML文檔進行特征提取時，我們首先要做的事情，就是將該Web頁面集合文本信息轉化成一個二維的數據表，其中列集為特征集，每一列是一個特征;行集為所有的頁面集合，每一行為一個Web頁面的特征集合。這種構造二維表的方法是:

i) 首先對頁面進行分詞，采用改進后匹配算法進行分詞;

ii) 每一列為一個詞，列集(特征集)為我們分詞詞典中的全部有價值的詞，因此，在我們的系統中，整個列集共有2000多列;

iii) 每一行存儲一個頁面內的詞的信息，這時，該頁面中的所有詞對應到列集(特征集)上。列集上的每一個列詞，如果在該頁面上不出現，則其值為0;如果出現了k次，那么其值就為k;頁面中的詞如果不出現在列集上，就說明該詞不具有區分價值，可以被拋棄。這樣，就可以表征出頁面中詞的頻度。

3.2 一些改進

由于我們分析的對象是一個HTML文檔，HTML格式中的一些特殊的標記代表了不同的意義，而這些標記對于整個HTML頁面的分析作用不容忽視。因此，我們在上面的二維表的基礎上，對頁面進行更深層次的頻度修改。其內容包括:

i)根據前面提出的八層標記符號分類，對該頁面對應的二維表中的值進行加權更新，其權值范圍從64到1，每級按照((9一層次值)的指數值遞增。比如，如果某頁面對應的二維表中的“四川長虹”詞的值為1，現在發現“TITLE”標記修飾的是“四川長虹”，則此時該行的“四川長虹”詞的值更新為1+(9-1)Z=65。以此類推可以修改其他詞的頻度。

ii)對于“錨”中的詞，由于“錨”通常與該頁面緊密相關，因此，我們認為“錨”中的詞具有與“一級標題”相同的權值，即對于“錨”中每次出現的詞都要加上49的權值。

iii)對于每一行中的詞，將其頻度最高的前四個詞作為這個HTML文檔的關鍵詞，和這個HTML文檔的標題和地址放入到主索引表中，供查詢使用。

根據上述核心設計，我們使用Java語言實現了基于多Agent技術的搜索引擎。

參考文獻:

[1] Wang Chuan， Chang Gui-ran，Ma Yan， et al. Research on search engines based on the user behaviormodel[J].Journal of Information Computational Science，2009，6(3):1389-1398.

[2] Wooldridge M， Jennings N.R.. Intelligent agents: Theory and practice.The Knowledge Engineering Review，1995，10(2):115-152.

[3] Nwana H S. Software agents: An overview. Knowledge Engineering Review，1996，11(3):205-244.

[4] Chuang Ya-lan， Wu Ling-ling. User-based evaluations of search engines:hygiene factors andmotivation factors[C].40th AnnualHawaii InternationalConference.Hawai，i USA，2007:82-82.

[5] Wu Ling-ling， Chuang Ya-lan， Chen Pin-yuen. Motivation forusingsearch engines:a two-factormodel[J].Journalof theAmerican Society for Information Science and Technology，2008，59(11):1829-1840.

[6] BadenHughes， AmolKama. A metadata search engine for digital language archives[J].D-LibMagazine，2005，11(2):78-84.