《大規模元搜尋引擎技》——2.3 挑戰環境

本節書摘來自華章出版社《大規模元搜尋引擎技》一書中的第2章，第2.3節，作者 ［美］孟衛一(weiyi meng)， 紐約州立大學， 賓漢姆頓分校於德（clement t.yu），伊利諾伊大學芝加哥分校，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

大多數情況下，元搜尋引擎使用的成員搜尋引擎是自治的，即它們是獨立建立和維護。每個搜尋引擎的開發者決定其搜尋引擎将為哪些文檔提供查詢服務、如何表示文檔以及何時更新索引。文檔和使用者查詢之間的相似度通過相似度函數計算。同樣，也是由每個搜尋引擎的開發者決定使用哪種相似度函數。商業搜尋引擎的開發者通常把他們使用的相似度函數和其他實作細節視為私有資訊，不向公衆提供。一般來說，元搜尋引擎需要與沒有直接合作關系的搜尋引擎互動。

成員搜尋引擎自治的直接後果是存在大量的異構。2.3.1節介紹元搜尋引擎環境中一些獨特的主要的異構，并讨論它們對建構元搜尋引擎的影響。常見于其他自治系統（如多資料庫系統）中的異構，例如不同的作業系統平台，我們将不做描述。2.3.2節簡要概述旨在簡化元搜尋引擎與其成員搜尋引擎之間互動的一些研究工作。

在自治成員搜尋引擎之間有下列異構［meng et al.,1999b，2002］。

1)文檔集。不同搜尋引擎的文檔集可能有兩個層次的不同。第一層是集合的主題或話題領域。例如，一個集合可能包含醫療文檔，另一個集合可能包含法律文檔。在這種情況下，這兩個集合的主題不同。在實際中，因為一個集合所包含的文檔可能來自多個領域，是以這一文檔集的主題領域可能不容易被确定。第二層是實際文檔。即使兩個集合有相同的主題，但它們仍然可以有完全不同的文檔集。一般情況下，多個文檔集合之間的關系是複雜的，因為在主題層次和文檔層次上，它們可以有不同的重疊度。

2)查詢語言。每個搜尋引擎都支援一個預定義的查詢模型集合，其範圍從向量空間模型、布爾模型、鄰近比對模型到精确的字元串比對和數值區域比對。而且，不同的搜尋引擎通常支援不同的查詢模型集合，使用不同的符号來表示相同的算符，針對使用者送出的關鍵詞查詢，若無明确指定算符時，會有不同的預設解釋。

3)伺服器連接配接。與人類使用者通過web浏覽器界面送出查詢給搜尋引擎不同，元搜尋引擎直接發送查詢到搜尋引擎伺服器。每個搜尋引擎都有連接配接配置，任何應用程式都需要使用該配置連接配接搜尋引擎。典型的配置包含名稱、伺服器的網際網路位址、支援的http請求方法、查詢字元串名稱、許多預設的查詢字元串名稱和值對（詳情請參見第4章）。不同的搜尋引擎通常有不同的連接配接配置。

4)響應頁面格式。所有搜尋引擎都用html編碼格式在動态生成的響應頁面中展示其檢索結果。這樣的格式通常是預先設計的，稱為模闆。一個模闆可能包含多個部分，例如，一部分用于顯示搜尋結果記錄，另一部分用于顯示贊助連結。在每一部分中，模闆控制如何組織和顯示該部分的資訊。響應頁面及包含查詢結果記錄的相應部分通常在不同的搜尋引擎中有不同的模闆。

5)索引方法。不同搜尋引擎可能采用不同的技術來确定表示一個文檔的詞。例如，有些搜尋引擎僅使用一個web頁面中出現的詞來索引該web頁面，但許多搜尋引擎也使用出現在其他web頁面中的錨詞（anchor term）來索引其連結的web頁面。其他一些不同索引技術的例子包括：是否删除停用詞（stop word）、是否執行詞幹提取（stemming）、是否識别短語。此外，不同的搜尋引擎可能使用不同的停用詞清單和不同的詞幹提取算法，以及識别出不同的短語。

6)詞權重方法。web頁面中詞的權重可以使用不同的方法來确定。例如，一種方法使用詞頻權重（term frequency weight），另一種使用詞頻權重（term frequency weight）和逆文檔頻率權重（inverse document frequency weight）的乘積（見1.2.2節）。這些方法存在多種變體［salton，g.，1989］。一些搜尋引擎也把詞的位置和字型加入權重計算。例如，若一個詞出現在web頁面标題中或為黑體，則其權重可被增加（更多讨論見1.3.3節）。

7)相似度函數。不同搜尋引擎可能采用不同相似度函數來度量查詢和web頁面之間的比對程度。針對文本文檔，1.2.3節描述了一些常用的相似度函數，包括餘弦函數和okapi函數。在1.3.4節中，我們讨論的連結導出的重要性（例如，pagerank）也可以運用于相似度函數。在實際中，相似度函數可能考慮大量的因素，排序規則可能變得非常複雜。例如，據2008年的報道，google所用的排序規則考慮了超過250個因素［hiemstra，d.，2008］。

8)文檔版本。作者可以随時修改web上他們自己的文檔，甚至可以由某些軟體自動修改。通常，當一個web頁面被修改後，索引該web頁面的那些搜尋引擎不會收到修改通知。在搜尋引擎重新擷取和重新索引修改後的web頁面之前，搜尋引擎中該web頁面的表示是基于陳舊的或過時的頁面版本。由于web規模龐大，是以大型搜尋引擎的爬蟲隻能按某一周期（從幾天到幾周）重訪以前索引過的頁面。是以，在一個搜尋引擎爬蟲兩次通路某一頁面之間，該頁面可能會經曆多次變化。由于搜尋引擎是自治的，是以它們的爬蟲可能在不同時間擷取或重新擷取相同的頁　每個頁面由它的url辨別。。是以，在任意給定時間，很可能不同搜尋引擎索引了同一頁面的不同版本。

上面讨論的自治性和異構性将對元搜尋引擎的每一個主要部件的建構産生重大影響。下面進行讨論。

1)搜尋引擎的選擇。第一，不同的成員搜尋引擎有不同文檔集，這一事實是需要對搜尋引擎進行選擇的基礎。第二，為了估計一個搜尋引擎關于一個給定查詢的有用性，搜尋引擎選擇器（search engine selector）需要具有搜尋引擎文檔集内容的一些知識。把概括搜尋引擎文檔集内容的知識稱為搜尋引擎内容表記（content representative），或簡稱表記（representative）。開發有效的搜尋引擎選擇算法的關鍵挑戰為：1)如何概括搜尋引擎文檔集的内容？換句話說，應該使用什麼樣的表記？2)如何使用不同成員搜尋引擎的表記來執行選擇？3)如何生成所需的表記？如果成員搜尋引擎不協作提供表記所需的資訊，最後一個問題會變得更加困難。由于搜尋引擎的自治性，它們的協作往往是不可能的。第3章将詳細研究上述3個問題。

2)搜尋引擎的加入。如2.1節所讨論的，搜尋引擎加入器部件包括兩部分：查詢分派器（query dispatcher）和結果抽取器（result extractor）。每個成員搜尋引擎的查詢分派器依次包括兩個程式：一個是連接配接程式（connection program），一個是查詢翻譯程式（query translator）。顯然，不同成員搜尋引擎的伺服器連接配接、查詢語言和響應頁面格式的異構性直接影響連接配接程式、查詢翻譯程式和結果抽取器。特别地，每個成員搜尋引擎需要各自的連接配接程式、查詢翻譯程式和結果抽取器。這使得開發大規模元搜尋引擎更具挑戰性，因為人工實作大量的連接配接程式、查詢翻譯程式和結果抽取器是不實際的。第4章将介紹這些子部件的高度自動化解決方案。

3)結果合并。許多因素影響文檔和查詢之間的相似性，這些因素包括文檔集（即它影響每個詞的文檔頻率進而每個詞的idf權重）、索引方法、詞權重方法、相似度函數和文檔版本。不同成員搜尋引擎之間這些因素的異構性使得不同搜尋引擎計算的相似度（關于同一查詢）沒有直接可比性。這意味着結果合并器不能直接使用這些相似度對不同搜尋引擎傳回的結果進行排序，即使這些相似度可以得到。現代搜尋引擎通常不傳回檢索結果的相似度，而是在内部使用這些相似度來确定檢索結果的排序。這導緻不同搜尋引擎傳回查詢結果的本地排序也沒有直接可比性。這些不可比性使得有效的結果合并算法的設計變得更複雜。第5章将介紹不同的結果合并技術。

如2.3.1節所讨論的，不同搜尋引擎之間的自治性和異構性使建構元搜尋引擎變得很困難。元搜尋領域已經付出了很大努力來規範元搜尋引擎和搜尋引擎之間的通信，以便簡化建構元搜尋引擎的任務。本節簡述其中一些主要工作。

starts（stanford proposal for internet meta-searching）［gravano et al.，1997］。這是最早提出在搜尋引擎和元搜尋引擎之間建立協定的嘗試之一。它考慮了如何支援搜尋引擎選擇、查詢映射和結果合并。對于搜尋引擎選擇，它要求搜尋引擎提供詞彙資訊（包括停用詞、詞幹提取、大小寫敏感性、字段相關性）和一些具體的統計資料（搜尋引擎的總計詞頻、文檔頻率和搜尋引擎中的文檔數目）。它還要求搜尋引擎提供内容摘要（文本描述）。starts對查詢語言問題進行了很好的讨論，包括基于關鍵詞的查詢、布爾運算符和鄰近條件。這些對于從元搜尋引擎查詢到搜尋引擎查詢的映射很重要。然而，starts沒有涉及應該如何格式化搜尋結果以便于元搜尋引擎抽取。

opensearch（http：//www.opensearch.org/home　通路日期為2010年11月3日。）。opensearch由amazon.com研發，它支援一些基本規格說明：連接配接資訊（例如，搜尋引擎伺服器的位址、字元編碼協定和輸入語言）、隐私資訊（例如，結果是否可以顯示給使用者或發送到其他應用程式）、進階别内容資訊（例如，是否有成人内容）。然而，它一般不支援詳細搜尋結果格式化的規格說明。它的“響應元素”支援一些xml協定，例如rss 2.0。

sru（search/retrieval via url；http：//www.loc.gov/standards/sru/　通路日期為2010年11月3日。）［sru］。sru可以視作z39.50為使其與web環境更相關而專門定制的特定版本。它使用擴充的url（一些細節包含在多個附加文檔中）來指定搜尋引擎的位址、查詢參數和結果格式。支援sru協定的每個搜尋引擎應該具有一條“解釋記錄”，此記錄給出關于其功能的資訊，如搜尋引擎連接配接資訊。

sru具有稱為通用查詢語言（common query language，cql）的查詢語言。cql支援關鍵詞檢索、布爾運算和鄰近條件。sru協定簡化了任意應用程式與搜尋引擎之間的互動，是以可以用來建構元搜尋引擎。然而，這個協定幾乎沒有要求便于簡化搜尋引擎選擇和結果合并所需的資訊。

mxg（metasearch xml gateway）［standards committee bc/task group 3，2006］。這是國家資訊标準組織（national information standards organization，niso）制定的一個标準。對于元搜尋應用，mxg是基于sru而制定的。它提供了一種由内容提供者向元搜尋引擎展示其内容和服務的機制。mxg有3個級别的要求，較進階别的要求支援更多的互操作性和功能性。級别1需要搜尋引擎滿足基本的url請求要求和響應要求（傳回結果使用xml格式）。但是，元搜尋引擎的開發者需要自己發現每個搜尋引擎具備的能力和如何将元搜尋引擎的使用者查詢轉化為搜尋引擎的本地查詢格式。級别2還要求搜尋引擎提供額外的資訊，如主機伺服器名稱、端口号和資料集名稱。級别3增加了這樣一個要求：每個符合級别3的搜尋引擎要支援一個标準查詢語言，即通用查詢語言。第3級mxg與sru沒有多大差別。

niso元搜尋議案（http：//www.niso.org/workrooms/mi/　通路日期為2010年11月3日。）。niso大約在2003年年底啟動這個議案。mi（metasearch initiative，元搜尋議案）委員會包括3個任務組。第一組關注通路管理（認證和授權）。第二組關注資料集描述和服務描述。第三組關注搜尋和檢索。到2005年年底，各任務組釋出了其推薦/草案标準。前面簡要提及的mxg和sru都是第三組的成果。

2005年第二組制定了兩個草案規則，一個用于資料集描述（collection description，cd ）［national information standards organization，2006a］，另一個用于服務描述（service description，sd）［national information standards organization，2006b］。針對cd，每一個資料集有28個屬性（辨別符、标題、可選标題、描述、大小、語言、類型、權限、通路權限、權責發生方法、權責發生周期性、權責發生政策、監管曆史、觀衆、主題、空間範圍、時間範圍、累積日期範圍、内容日期範圍、主體完整性、采集者、所有者、通路方式、子集、擴集、目錄或說明、相關集合、相關出版物）。草案規則［national information standards organization，2006a］沒有論及有關詞的統計資料。針對sd，描述服務的資訊包括服務位置、網絡協定（例如，http）、身份驗證或授權協定、通路資料的方法（搜尋、浏覽、排序、查詢語言、字段/屬性、比較器），以及能夠被檢索的記錄數（或類似的功能設定）等。

niso是美國國家标準局（american national standards institute，ansi）的一部分，這個mi工作有來自世界上許多組織的參與者。是以，提出的标準有一定的公信力。然而，mi目前的狀況并不清楚，因為從niso mi網站（http：//www.niso.org/workrooms/mi/）上看，似乎2006年之後niso mi委員會就一直不活躍了。

盡管有上述工作，但是它們并沒有被廣泛用于建構真正的元搜尋引擎。能被搜尋引擎開發者廣泛接受的單一标準是否會出現，仍拭目以待。