異質性搜尋引擎代理人之設計與實作




謝欣君、 張玉山、袁賢銘

國立交通大學資訊科學系
新竹市大學路1001號
TEL:(03) 5712121 EXT.56601
EMAIL:gis86562@cis.nctu.edu.tw ysc@mhit.edu.tw smyuan@cis.nctu.edu.tw




摘要

  搜尋引擎的使用已成為目前在全球資訊網上最重要的工具之一﹐使用者日益增多﹐而目前不論在學術界或工商業界亦有各種不同的系統正在發展及使用中﹐例如Yahoo, AltaVista, Yam, Gais, Wais等。在這些系統上﹐大致被分成主動式全文檢索及被動式全文檢索二類﹐每一個系統雖然在使用的方式類似﹐但在介面上卻不儘相同﹐使得使用者在使用上會造成一些困擾。在本論文中我們準備完成一異質性搜尋引擎代理人﹐可以將這些不同系統整合在一個環境中﹐使得使用者透過我們的環境可以用同一種介面存取各種檢索系統。我們選擇以CORBA架構做為連結這些系統的平台﹐在CORBA上訂定一共同的網際網路搜尋服務(Internet Search Service, 簡稱ISS)﹐並且為每一種系統實作一object implementation﹐最後再以CGI介面連結WWW及我們的全文檢索引擎代理人﹐使得使用者可以透過WWW來使用我們的異質全文檢索引擎代理人。





一、研究動機

  近年來由於網路快速發展,及全球資訊網WWW使用者日益增多,促使WWW上網站也快速的增加,但因為網站過多,使得使用者在使用網路時經常因不知網站的網址或一些相關訊息,也因此網站的搜尋成為網路使用者經常要面臨的問題。為了克服此一問題,便促使搜尋引擎的發展。目前常使用的搜尋引擎主要分成二類,一類是主動式,如AltaVista,他是以主動的方式定時的搜尋Internet的各個網站,然後將所搜尋的資訊建構在資料庫,以供其他使用者使用。另一類是被動式的,如Yahoo,這種系統主要是以註冊的方式向檢索系統註冊,檢索系統並不會去搜尋其他的站。這些系統都有其優缺點,因此各有其使用者,以下我們列出一般搜尋引擎之問題:

  1. 由於不同的搜尋引擎可能有不同的介面及其特性, 使得使用者在使用這些搜尋引擎經常造成不便。
  2. 並非所有的搜尋引擎都可以找到所要的網站。
  3. 由搜尋引擎所傳回的訊息可能不相關。
  4. 有可能所找到的是一些過時的訊息。
以上這些問題促使使用者希望有一個較好的全文檢索系統。

  由前面可知,由於不同搜尋引擎會有不同介面及其特性, 經常會造成使用者使用上的不便,因此有一些研究是希望對所有的搜尋引擎有一個單一的檢索介面,讓使用者在使用上可以更方便。這方面的系統如PLS[4],Lexis-Nexis[5]及Verity[6], 除了業界外, 國內外學術上的研究也有很多,如[7][8][9][10]等, 這些都是希望找到一個比較好的方法可以讓使用者在檢索上有一致的使用者介面或是得到更正確更完整的訊息,不過這些系統都缺乏擴充性。所以本論文的目的是要整合各種不同的搜尋引擎, 設計一個異質性的(Hetrogeneous)搜尋引擎代理人(agent), 透過這個代理人, 使用者可以很容易而且具有單一介面的使用各種不同的檢索系統, 不需因不同的搜尋引擎有不同介面而產生困擾。 而我們將利用OMG所制定的CORBA[11]架構來整合這些系統, 其主要的考量是CORBA已儼然成為工業標準, 而且由CORBA的發展我們可以發現, CORBA不但透過IIOP來整合自已的差異(不同廠商的不同的ORB), 亦透過IIOP來整合不同的分散式物件導向計算環境, 因此在分散式平台中都可以透過CORBA順利的達到整合的目的, 將此技術應用在異質全文檢索引擎代理人的發展, 也替檢索系統保留了發展的空間。





二、系統架構

  在前我們已經說明了利用CORBA架構來製作異質性搜尋引擎之主要原因是因為CORBA架構已漸漸成為工業標準﹐而這個標準目前還在成長之中﹐並且我們從CORBA 2.0的標準中可以發現﹐CORBA的包容性相當高﹐他不但支援分散式物件的計算環境﹐ 並且可以在不同ORB的環境中利用IIOP的技術達到Interoperability﹔另外OMG亦制定了CORBA到DCOM及CORBA到DCE的Interoperability標準﹐在此我們可以預見的是CORBA亦可能制定CORBA到JAVA Bean的Interoperability﹐如圖一如示。 因此以CORBA為分散式物件導向計算環境的骨幹應是未來的趨勢﹐因此如果我們以CORBA為異質性全文檢索引擎之平台﹐則未來在各種分散式環境下的全文檢索服務系統都可以很容易的透過我們的異質性搜尋引擎代理人來達到檢索的目的。這也是我們以CORBA架構來設計的原因之一。 在圖一顯示我們所要完成的異質性搜尋引擎代理人的架構圖﹐在此架構中可以有各種不同的Search Engine﹐在本論文中我們初步是針對Yahoo及AltaVista這二個系統來測試,不過正如我們前面所提,CORBA架構的擴充性很高,因此我們很容易擴充到其他的系統上。



圖一、異質性全搜尋引擎代理人的架構圖

  本架構分成下列三個部份:

  1. server端為search engine layer。各個search engine獨立運作,每個搜尋引擎接收從ISS Layer中相對應的search service object發出的CGI query string,再執行此一已轉換成自己介面的搜尋動作,最後再將搜尋結果傳回。透過ISS Layer可擴充至多個搜尋引擎同時運作。
  2. 中間層為CORBA架構,處理檢索代理動作,在此亦分為三層。
    1. 在server端為ISS Layer,每個搜尋引擎都有一個相對應的search service object。此一search service object 會接收CORBA client發出的request(即對那些attribute作設定動作),而每個search service object必須支援ISS介面,並且依ISS介面的attribute將client所設定的查詢動作轉成該對應之搜尋引擎所能接受的查詢字串,最後將query string再送給搜尋引擎去執行。
    2. 而CORBA架構的中間層則為ORB,處理client與server之間的通訊機制,如client request的遞送等。
    3. 至於client端則是CORBA client加上CGI程式。CGI程式收到從此一異質全文檢索引擎代理人的檢索網頁所送出的query string後,啟動CORBA的client,使client呼叫ISS的服務。而client在收到各搜尋引擎的搜尋結果後,經由CGI程式將重覆的資料剔除,再由CGI程式送結果文件回真正的client用戶(即Web操作者)。
  3. client端則是使用者利用瀏覽器在異質全文檢索引擎代理人的homepage上檢索,使用ISS定出來的語法組成一個query string,當然也提供簡易搜尋模式及進階搜尋模式。

  接著我們說明此系統研究的步驟如下:

  1. 抽象化各檢索系統之介面: 由於各系統間其介面可能不同﹐其特性也不儘相同﹐我們首先要將各異質系統的介面抽象化﹐以便我們可以對根據這些抽象化後之介面訂定一致的搜尋引擎代理人介面。在這一點我們所要進行的步驟可以分成下列二項:
    1. 分析各種系統之介面: 我們首先對二種不同典型的系統進行分析﹐即主動式的﹐以AltaVista為典型﹐及被動式的﹐以Yahoo為典型﹐其主要的差異﹐並了解其介面及特性之不同﹐然後再分析其他的系統﹐如Yam﹐Gais﹐Wais等系統。
    2. 抽出各介面共同的特性:對於各種系統介面相同之處﹐我們可以在分析後找出﹐不同之處可以制訂新介面來達到其目的。
  2. 設計異質性搜尋引擎代理人的使用者介面: 在第一步驟中我們將各系統的介面抽出並且找出共同點﹐接著我們可以根據其共同點設計一些共同的介面﹐其不同點﹐亦可整合使其成為一共同的介面﹐大約可以分成如下二個步驟。
    1. 整合不同搜尋引擎系統之介面:根據其共同及不同的介面﹐找出相通之處理﹐使其可以在相同的介面下達到所需之功能。
    2. 訂定ISS的介面:接著我們再根據所找出的介面特性及共同的介面﹐依據CORBA的COSS規格﹐訂定一個網際網路搜尋服務(Internet Search Service, 簡稱ISS)﹐此介面即是各種系統的合一版本﹐亦即是用以整合所有異質系統的介面。此一介面亦是使用者所要呼叫之介面﹐使用者透過此介面可以與各種系統溝通﹐來達到檢索之目的。
  3. 實作異質性全文檢索引擎代理人: 在一致的共同介面制訂出來後﹐我們可以來實作此一介面﹐在介面完成時﹐此檢索系統即以ORB為其驅動之引擎﹐因此我們要先實作ISS之介面﹐此介面實作完成後向ORB註冊﹐使得使用者的搜尋動作可以透過已完成的服務來執行﹐達到檢索的目的。在此可以分成二個步驟來完成。
    1. 實作ISS服務: 由於在CORBA上IDL介面可以透過編譯程式將介面轉成一般的語言﹐因此我們可以透過編譯器編譯成C++的語言﹐再根據每一種檢索系統來完成一個object implementation﹐在這些object implementation中﹐ORB會透通的選擇所要的搜尋引擎來搜尋使用者所需之全文﹐所以在此步驟上﹐我們必需對各種不同的搜尋引擎實作一個object implementation。
    2. 實作CORBA/CGI之介面: 在完成ISS的服務之後﹐我們最後所要完成的便是CORBA的client及與CGI間的介面程式﹐利用CGI來啟動CORBA的client以便呼叫ISS的服務。最後是完成一個CGI的介面。

  2.1 ISS介面之制定

  由於在那些介面的異同點中,部份屬性具有同質性,但也有些部份是完全不同的,我們為了訂定一個共同的ISS,因此必需整合所有的介面,根據我們的詳細的分析後,可以整合如下幾點:

  1. 由於Host是Domain的子集,性質類似且不能同時存在所以可以把它定成String型態的attribute,不是完整的Host name就是Domain name。
  2. 將搜尋對像歸成一類,其型態定成long型態,從這個attribute來決定要對何種Tag檢索,以bit-map的方式對應。
  3. 有些部份搜尋引擎有提供字距限制的語法,而AltaVista僅提供固定的字距(10個字元),為了日後的擴充性及彈性,我們把它設成Iong型態,可以指定要間隔多少字。
  4. 每個搜尋引擎必有的邏輯關係:AND、OR,至於NOT則以Exclude取代,也由於不能同時存在AND及OR所以我們將此邏輯關係設成Char型態的attribute。
  5. 關於日期限制的部份可自成一項attribute,型態設為String並以固定的三種格式指定。
  6. 現今大部份的搜尋引擎大都同時具有Web site及Categories,所以可以以一個attribute來表示搜尋的資料庫,因為有可能兩者皆檢索所以定成Char型態。
  7. 檢索的資料庫可以從Web site及Usenet中選擇其一,除此之外愈來愈多的搜尋引擎還可搜尋其它種類的資料庫(如E-Mail、人名等),所以我們把它定成long型態,同樣地以bit-map的方式對應。
  8. 欲檢索的文字則以一個包含關係搭配一個字串成為一組keyword結構。由於keyword可以有很多個,所以需要以陣列型態儲存。
  9. 包含關係有Include、Exclude及未設定三種,於是我們便將其設為Char型態,至於字串部份當然是定成String型態。
  10. 輸出的自訂選項可以選擇要一頁顯示幾筆檢索到的結果,我們將此attribute設成Iong。

  如此便將大部份的搜尋引擎介面都囊括了,而且有系統的整理出來。另外還要制定operation,我們必需透過一個operation來invoke搜尋引擎提供的服務,它根據那些attribute來invoke service,並且這個operation必須要有傳回的參數,以可傳回搜尋結果。接下來就是實際的制定結果,以IDL表示。


module InternetSearchService
{
	struct Result
	{
		string Title;
		string URL;
		string Description;
		string Date;
		float weight;
	};

	struct Keyword
	{
		char Inclu_Exclu;
		string item;
	};

	interface ResultCollection
	{
		readonly attribute long No_Result;

		Result retrieve_element_at(in long where);
	};

	interface Search
	{	
    		attribute string Domain;
     		attribute long Tag;
     		attribute string Date; 
     		attribute long Near;
     		attribute long DispNum;
     		attribute long Area;
     		attribute boolean DataBase;
     		readonly attribute long No_Keyword;
		
    		boolean AddKeyword(in Keyword add);
		boolean RemoveKeyword(in Keyword removed);
		Keyword GetKeyword(in long index);
		ResultCollection ExcuteSearch();
		Boolean AbortSearch();
	};

	interface SearchFactory
	{
		Search NewSearch();
	};
};

  2.2 ISS layer service之產生

  在圖二中可以完全的描述如何產生ISS layer service,當然這也是CORBA產生client 程式及server程式的方式。我們是將所訂定出來的ISS的IDL檔經過IDL編譯器產生client stub及server skeleton,然後再撰寫client程式及server程式與IDL所產生的client stub及server skeleton連接,最後產生client程式及server程式。


圖二、 ISS layer service之產生

  2.3 WWW環境之系統實作架構


圖三、 WWW環境之系統實作架構圖

  2.3.1 CGI程式之實作

  我們的Web Server建置在Sun OS下,搜尋引擎首頁置於http://plato.cis.nctu.edu.tw/CORBA/Search.html,CGI程式以C語言撰寫,將從首頁所接收到的資訊轉存成attribute及keyword set的封包(package)然後透過Socket傳給mediator程式。CGI程式在傳送attribute及keyword set封包完畢後,便等待接收由mediator處理過的搜尋結果,然後再依user的輸出選擇來產生HTML文件,user便可得到結果清單。

  2.3.2 Mediator程式之實作

  每當有一個CGI要求建立連線,就必須產生一個instance出來替不同的查詢做服務,並且亦要將從各個搜尋引擎所得來的結果做整合處理,如此便須一個仲裁者(mediator)將使用者之檢索屬性及關鍵字組合傳給各個對應搜尋引擎的CORBA client function,並整合所有的結果,再將之傳回給CGI程式。Mediator程式就像deamon一樣平時啟動著,每當接收到一個新的CGI Socket連線,便建立一個新的mediator執行緒(Thread),新的執行緒會等待接收此一新的CGI連線所丟過來的attribute及keyword set封包,當收到設定完成的封包後,分別再產生Yahoo CORBA client function及AltaVista CORBA client function的執行緒以同時發出query string至搜尋引擎,並同時等候結果回傳。而mediator function便等待全部的ISS CORBA client function皆執行完畢後(即結果收集完成)方處理後續動作,上述功能是由兩層的多執行緒(multithread)技巧來達成。





三、結論與未來發展方向

  本系統為保留本身的擴充性的和其他系統的相互操作性(Interoperability),我們使用CORBA為執行的軟體平台,這是其他系統所沒有的。我們也根據CORBA的COSS規格,訂定了ISS,期待未來可以成為CORBA上的一個標準。此外,本系統的一個特點便是為不同的搜尋引擎實作個別的CORBA Agent Object,使其成為一個個的Component,我們提供了多個具有相同介面的搜尋引擎代理人元件,基植於此我們提供了最大的彈性給client端做多樣化的組合。目前已有多個MetaSearch的演算法[18]使用在MetaSearch的搜尋引擎上,client端可依這些或自訂的演算法來動態選擇一組最佳化的搜尋引擎,提升效率性及精確度。甚至可以加上knowledge Base使其具有個人化功能,更服合使用者的行為及需求。最後,由於此一ISS介面已囊括絕大部份的搜尋語法,所以不僅可適用在搜尋引擎上,甚至可用於房屋仲介、數位圖書館搜尋等使其成為異質性檢索系統代理人,只是實作不同的物件而已,而操作介面不變,這一點是本系統的最大特色。也由於訂出ISS介面,我們可已將其用於其它的物件模組技術,如COM、JavaBeans等,提供實作者最大的彈性。




參考文獻

[1]  Michael Schwartz et al., WWW Home Pages Harvest Broker. http://town.hall.org/Harvest/broker/www-home-pages/.

[2]  IBM, Inc. Query By Images Content Home Page. http://wwwqbic.almaden.ibm.com/~qbic/qbic.html.

[3]  Brandon Plewe, The Virtual Tourist Home Page. http://wings.buffalo.edu/world.

[4]  Personal Library Software, Ine. Personal Library Software Home Page. http://www.pls.com.

[5]  LEXIS-NEXIS. LEXIS-NEXIS Communication Center. http://www.lexis-nexis.com.

[6]  Verity, Inc. Verity Home Page. http://www.verity.com

[7]  Chia-Hui Chang and Ching-Chi Hsu, "Customizable Multi-engine Search Tool with Clustering", Proceeding of the sixth international world wide web conference'97,Santa Clara, California, USA, April 1997, pp.257-264.

[8]  Massimo Marchiori, "The quest for Correct Information on the Web: Hyper Search Engineers", Proceeding of the sixth international world wide web conference'97,Santa Clara, California, USA, April 1997, pp.265-276.

[9]  Daniel Dreilinger," Integrating Heterogeneous WWW Search Engines", May 1995. ftp://132.239.54.5/savvy/report.ps.gz.

[10] E. Selberg, O. Etzioni," Multi-Engines Search and Comparison Using the MetaCrawler", proceeding of the Fourth World Wide Web Conference'95, Boston USA. Dec 1995.

[11] Object Management Group, Inc. The Common Object request Broker(CORBA): Architecture and Specification, v2.0, November 1995.

[12] Object Management Group, Inc. CORBA services: Common Object Services Specification, OMG Document Number 95-3-31, March 31, 1995.

[13] Deron Liang, Winston Lo, and Shyan-Ming Yuan "Introduction to CORBA 2.0 Specification and its Future Trends" in Proc. of 1996 Workshop on Distributed System Technology and Applications, pp. 3-10, Taipei, Taiwan, May 1996.

[14] Deron Liang, S.C. Chou, and Shyan-Ming Yuan, "Adding Fault-Tolerant Object Services to CORBA" ,in Proc. of the 1996 International Workshop on Dependability in Advanced Computing Paradigms (DACP-96), Ibaraki, Japan, June, 1996.

[15] Yue-Shan Chang, Yu-Ming Kao, Shyan-Ming Yuan, and Deron Liang, 1996, "An Object Transaction Service based on CORBA Architecture", in Proc. of 1996 IFIP/IEEE Int'l Conf. on Distributed Platforms, (Dresden, Germany), Feb.

[16] Kai-Chih Liang, Shyan-Ming Yuan, Deron Liang, and Winston Lo. "Nested Transaction and Concurrency Control Services on CORBA", in Proc. Of Joint International Conference on Open Distributed Processing (ICODP) and Distributed Platforms (ICDP), 27-30 May 1997 Toronto, Ontario, Canada. (zipped postscript version is here)

[17] Guang-Way Sheu, Yue-Shan Chang, Deron Liang, Shyan-Ming Yuan, Winson Lo. "A Fault-Tolerant object service on CORBA" to apear in ICDCS 97

[18] Daniel Dreilinger, Adele E. Howe, "Experiences with Selecting Search Engines Using Metasearch", in ACM Transaction on Information System, Vol.15, No.3, July 1997, Pages 195-222. http://www.microsoft.com/webdev/