《網(wǎng)絡(luò)信息檢索》課件第8章

第8章并行和分布式信息檢索8.1并行信息檢索8.2分布式信息檢索8.3元搜索引擎8.4P2P網(wǎng)絡(luò)信息檢索8.5小結(jié)思考題

8.1并行信息檢索

8.1.1并行計(jì)算的概念

并行計(jì)算就是研究如何把一個(gè)需要非常巨大的計(jì)算能力才能解決的問(wèn)題分成許多小的部分，分配給多個(gè)計(jì)算機(jī)進(jìn)行處理，并把這些計(jì)算結(jié)果綜合起來(lái)得到最終結(jié)果的問(wèn)題。并行計(jì)算技術(shù)起源于科學(xué)計(jì)算，但如今其應(yīng)用領(lǐng)域已不再僅僅限于科學(xué)計(jì)算。它已經(jīng)被廣泛地應(yīng)用在工程計(jì)算及許多新興的應(yīng)用領(lǐng)域，比如金融走勢(shì)模擬分析、信息檢索和數(shù)據(jù)挖掘等。并行計(jì)算機(jī)是由多個(gè)可同時(shí)工作的處理器構(gòu)成的計(jì)算機(jī)系統(tǒng)。目前，并行計(jì)算系統(tǒng)主要是指并行計(jì)算機(jī)(Multicomputer)系統(tǒng)或多處理機(jī)(Multiprocessors)系統(tǒng)。在一個(gè)并行計(jì)算系統(tǒng)中，不同處理器同時(shí)運(yùn)行同一程序的多個(gè)任務(wù)或進(jìn)程，或者同時(shí)運(yùn)行多個(gè)作業(yè)或大量計(jì)算問(wèn)題的多個(gè)獨(dú)立程序，以提高系統(tǒng)的運(yùn)算速度、吞吐量、系統(tǒng)的可靠性或有效地利用系統(tǒng)的資源。就處理器的組合方式不同，可以對(duì)并行體系結(jié)構(gòu)進(jìn)行分類。常用的Flynn分類法根據(jù)指令和數(shù)據(jù)流數(shù)目，把并行計(jì)算體系結(jié)構(gòu)分為四種類型：

(1)SISD(單指令、單數(shù)據(jù)流)：串行地執(zhí)行指令；

(2)MISD(多指令、單數(shù)據(jù)流)：在多個(gè)處理機(jī)中用不同的指令去處理單個(gè)數(shù)據(jù)；

(3)SIMD(單指令、多數(shù)據(jù)流)：以多個(gè)處理機(jī)同時(shí)對(duì)不同的數(shù)據(jù)執(zhí)行同一種指令操作；

(4)MIMD(多指令、多數(shù)據(jù)流)：以多個(gè)處理機(jī)自治地對(duì)不同的數(shù)據(jù)執(zhí)行不同的操作。

高速并行計(jì)算有三種類型的應(yīng)用：①計(jì)算密集型(Compute-Intensive)應(yīng)用，如大型科學(xué)工程計(jì)算與數(shù)值模擬；②數(shù)據(jù)密集型(Data-Intensive)應(yīng)用，如數(shù)字圖書(shū)館、數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘和計(jì)算可視化等；③網(wǎng)絡(luò)密集型(Network-Intensive)應(yīng)用，如協(xié)同工作、遙控和遠(yuǎn)程醫(yī)療診斷等[1]。搜索引擎的設(shè)計(jì)和實(shí)現(xiàn)需要在短時(shí)間內(nèi)存取和處理海量數(shù)據(jù)，因此是一種數(shù)據(jù)密集型應(yīng)用。這類數(shù)據(jù)密集型應(yīng)用是并行計(jì)算技術(shù)非常適合的領(lǐng)域，同時(shí)也是必須采用并行計(jì)算技術(shù)的應(yīng)用領(lǐng)域。例如，如果有總共達(dá)1TB的文本數(shù)據(jù)，需要在這些特定的文本文件中找到“并行計(jì)算”這個(gè)詞組，并要知道它出現(xiàn)了多少次，都出現(xiàn)在哪些文件的什么位置，并且要求系統(tǒng)給出答案的時(shí)間不超過(guò)1秒。如果用普通的計(jì)算機(jī)來(lái)處理，單單文件I/O，所需的時(shí)間就不止1秒；即使文件I/O的時(shí)間可以忽略不計(jì)，CPU以峰值速率運(yùn)行，它要在1TB數(shù)據(jù)中找到一個(gè)特定的詞組所需的時(shí)間開(kāi)銷也是巨大的。再進(jìn)一步，如果有成百上千用戶同時(shí)利用系統(tǒng)搜索不同的詞組，都要求在1秒鐘內(nèi)得到答案，單機(jī)系統(tǒng)根本處理不過(guò)來(lái)。用戶不能容忍過(guò)長(zhǎng)的等待時(shí)間，如果磁盤的轉(zhuǎn)速和尋道時(shí)間沒(méi)有數(shù)量級(jí)的提高，那么將數(shù)據(jù)讀入內(nèi)存是唯一避免I/O瓶頸的方法。目前普通計(jì)算機(jī)無(wú)法提供1TB的內(nèi)存，那么可以考慮將1TB數(shù)據(jù)讀入100臺(tái)10GB內(nèi)存的計(jì)算機(jī)，100臺(tái)計(jì)算機(jī)同時(shí)在總計(jì)1TB的數(shù)據(jù)中查找，每臺(tái)計(jì)算機(jī)僅僅查找10GB數(shù)據(jù)，這樣才有可能在短時(shí)間內(nèi)完成用戶的請(qǐng)求。

并行計(jì)算，換來(lái)的是I/O帶寬的累加，內(nèi)存容量的累加以及CPU處理能力的累加。在搜索引擎這種海量數(shù)據(jù)處理問(wèn)題上，并行計(jì)算技術(shù)是高效處理海量數(shù)據(jù)的根本辦法。8.1.2并行信息檢索體系架構(gòu)

在介紹并行檢索之前，先看看信息檢索的一般過(guò)程，如圖8-1所示。圖8-1檢索的一般過(guò)程如圖8-1所示，用戶提交一個(gè)查詢，查詢代理對(duì)查詢進(jìn)行分析，比如進(jìn)行編碼格式轉(zhuǎn)換，分詞解析等，得到一個(gè)規(guī)格化的查詢?cè)~，發(fā)送到檢索程序，檢索程序從索引中查找文檔并進(jìn)行處理，如計(jì)算得分和結(jié)果排序等，然后將初步結(jié)果發(fā)回到查詢代理，查詢代理進(jìn)行規(guī)整、合并后，把結(jié)果返回給用戶。

綜上所述，信息檢索可以很方便地進(jìn)行并行化處理。直觀地看來(lái)，多條查詢之間可以進(jìn)行并行檢索，單條查詢內(nèi)部也可以進(jìn)行并行檢索。

1．一般體系架構(gòu)

一種可行的體系架構(gòu)就是，檢索系統(tǒng)利用并行計(jì)算機(jī)中的每一個(gè)處理器運(yùn)行一個(gè)分離的、獨(dú)立的搜索，這些獨(dú)立的搜索可能共享程序代碼庫(kù)、文件系統(tǒng)中的數(shù)據(jù)或共享內(nèi)存中的數(shù)據(jù)等。用戶向搜索引擎提交的查詢是由一個(gè)代理程序來(lái)管理的，代理接受用戶的搜索請(qǐng)求，并把請(qǐng)求分發(fā)到子檢索系統(tǒng)中。圖8-2所示為原理模型，圖8-3為對(duì)應(yīng)的并行信息檢索服務(wù)器模塊圖。圖8-2并行檢索模型圖8-3并行信息檢索服務(wù)器如果有較多的處理器，就可以并行運(yùn)行更多的獨(dú)立搜索，因此可以并行處理更多的搜索請(qǐng)求，提高系統(tǒng)的吞吐量。但是需要注意，并不是簡(jiǎn)單地堆積CPU和磁盤，就可以提高信息檢索的性能。問(wèn)題是如何有效地利用硬件資源，設(shè)計(jì)合理的軟件結(jié)構(gòu)包括系統(tǒng)體系結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)，以提高信息檢索的性能。否則有時(shí)候盲目添加更多的硬件反而會(huì)降低性能，因?yàn)殡S著處理器數(shù)目的增加，磁盤和I/O通道訪問(wèn)次數(shù)也隨之增加，各個(gè)處理器的訪問(wèn)可能會(huì)互相沖突，造成磁盤的存取競(jìng)爭(zhēng)。磁盤瓶頸將會(huì)降低性能，抵消增加處理器帶來(lái)的吞吐量增益。因此需要仔細(xì)地平衡系統(tǒng)中的硬件資源。

2．?dāng)?shù)據(jù)分割和計(jì)算分割

為了支持并行檢索，除了在計(jì)算機(jī)中增加更多的磁盤外，系統(tǒng)管理員還必須合理地在磁盤中分配索引數(shù)據(jù)。如果兩個(gè)搜索進(jìn)程需要存取存放在相同磁盤上的索引數(shù)據(jù)，仍然會(huì)有磁盤競(jìng)爭(zhēng)的問(wèn)題。增加磁盤的數(shù)量，可以減少這樣的競(jìng)爭(zhēng)，但是同時(shí)也增加了存儲(chǔ)設(shè)備的費(fèi)用和更新的復(fù)雜性?？梢钥紤]作一些改進(jìn)，例如，將那些被訪問(wèn)次數(shù)多的數(shù)據(jù)復(fù)制存儲(chǔ)，而把較少被訪問(wèn)的數(shù)據(jù)隨機(jī)分布，這就是索引數(shù)據(jù)的分割和復(fù)制存放策略。為了進(jìn)一步改善查詢的響應(yīng)時(shí)間，必須對(duì)單個(gè)查詢所需要的計(jì)算量進(jìn)行分割，分出多個(gè)子任務(wù)，并分配到多個(gè)處理器上去執(zhí)行。在這種方法中，代理和搜索進(jìn)程也是并行運(yùn)行在分離的處理器上，但是現(xiàn)在是協(xié)同運(yùn)行去處理同一個(gè)查詢。代理程序接受用戶的一個(gè)查詢，并把它分配到多個(gè)搜索進(jìn)程上。然后，每個(gè)搜索進(jìn)程執(zhí)行部分查詢?nèi)蝿?wù)，把中間結(jié)果返回給代理。最后，代理把這些中間結(jié)果組合起來(lái)，形成一個(gè)最終的結(jié)果，交付給用戶。從上面的描述可以知道，并行檢索主要涉及兩大關(guān)鍵技術(shù)，一是并行計(jì)算，二是并行數(shù)據(jù)存取，前者需要通過(guò)并行編程實(shí)現(xiàn)檢索計(jì)算的并行化，后者則是需要對(duì)數(shù)據(jù)結(jié)構(gòu)如倒排文件進(jìn)行分割，并存放在并行文件系統(tǒng)上，以提供高性能高帶寬的并行數(shù)據(jù)存取功能。針對(duì)搜索引擎而言，這兩大技術(shù)的實(shí)現(xiàn)有著很獨(dú)特的要求和特點(diǎn)。下面主要介紹面向信息檢索的并行編程和數(shù)據(jù)并行技術(shù)以及Google在這方面的兩大核心技術(shù)：MapReduce并行編程模型[2]和GFS(GoogleFileSystem)并行文件系統(tǒng)[3]。8.1.3并行編程

1．并行編程概述

并行編程模型一直是并行計(jì)算研究領(lǐng)域的重點(diǎn)內(nèi)容，它和并行計(jì)算機(jī)體系架構(gòu)緊密相關(guān)。共享存儲(chǔ)和消息傳遞是目前兩種主流的并行編程模型。共享存儲(chǔ)體系架構(gòu)下的并行編程模型主要是共享變量編程模型，它具有單地址空間、編程容易、可移植性差等特點(diǎn)，其實(shí)現(xiàn)有OpenMP[4]和Pthreads(POSIXThread)[5]等。分布式存儲(chǔ)體系架構(gòu)下的并行編程模型主要有消息傳遞編程模型，消息傳遞編程模型的特點(diǎn)是多地址空間，編程困難，可移植性好，其實(shí)現(xiàn)有MPI(MessagePassingInterface)[6]和PVM(ParallelVirtualMachine)[7]等。目前用來(lái)構(gòu)建搜索引擎的都是普通PC組成的集群(Cluster)系統(tǒng)，而不是具有共享存儲(chǔ)的SMP(SymmetricalMultiprocessing)機(jī)器，因?yàn)楹笳弑容^昂貴。而集群系統(tǒng)是很典型的分布存儲(chǔ)體系架構(gòu)，因此需要采用分布存儲(chǔ)編程模型，例如消息傳遞編程。消息傳遞(MessagePassing)是指在各個(gè)處理機(jī)節(jié)點(diǎn)之間通過(guò)用戶調(diào)用并行系統(tǒng)的子程序庫(kù)來(lái)實(shí)現(xiàn)它們之間的實(shí)時(shí)消息傳遞(MessageCommunication)。消息傳遞可以定義為：在一組進(jìn)程當(dāng)中，各個(gè)進(jìn)程之間通過(guò)發(fā)送和接收數(shù)據(jù)來(lái)實(shí)現(xiàn)進(jìn)程之間的相互通信。數(shù)據(jù)的傳遞需要各個(gè)處理器節(jié)點(diǎn)之間相互協(xié)調(diào)操作，即一個(gè)發(fā)送(send)的操作就必須有一個(gè)接收(receive)的操作與之相匹配。并行編程對(duì)開(kāi)發(fā)者的要求較高。相比于串行編程，并行編程中需要額外考慮以下問(wèn)題：

(1)負(fù)載平衡問(wèn)題。并行程序中可能出現(xiàn)負(fù)載不平衡的問(wèn)題，沒(méi)有充分利用每個(gè)處理器的處理能力，導(dǎo)致一些處理器比較空閑，影響了程序的總體執(zhí)行性能。

(2)進(jìn)程數(shù)或線程數(shù)的選擇問(wèn)題。一些應(yīng)用問(wèn)題存在所需進(jìn)程或線程數(shù)目與處理機(jī)數(shù)目不匹配的問(wèn)題。若前者太小，則不能充分發(fā)揮機(jī)器的效率；若太大，又無(wú)法執(zhí)行。

(3)通信帶寬和延遲問(wèn)題。并行程序進(jìn)程間的通信帶寬和延遲問(wèn)題可能會(huì)嚴(yán)重影響程序的執(zhí)行性能。特別是在分布式存儲(chǔ)系統(tǒng)如集群系統(tǒng)中，通信延遲對(duì)總體性能的影響更大。

(4)細(xì)粒度并行問(wèn)題。編寫并行程序時(shí)，一般并行粒度越小，越可以更好地利用多處理器，但并行粒度太小也會(huì)增加系統(tǒng)的管理開(kāi)銷。

2．并行編程模型MapReduce

搜索引擎系統(tǒng)需要對(duì)原始數(shù)據(jù)(爬蟲(chóng)抓取下來(lái)的文檔、用戶查詢?nèi)罩镜?進(jìn)行處理，生成倒排索引文件，網(wǎng)頁(yè)鏈接關(guān)系庫(kù)等。這些處理算法原本是簡(jiǎn)單直觀的，但在處理海量的原始數(shù)據(jù)集時(shí)，要在較短的時(shí)間內(nèi)得到運(yùn)算結(jié)果，就只有把運(yùn)算分布到多臺(tái)機(jī)器上并行進(jìn)行。如何分割數(shù)據(jù)，如何并行運(yùn)算，如何處理異常和錯(cuò)誤，都需要進(jìn)行詳細(xì)的分析設(shè)計(jì)，這些都是很復(fù)雜的問(wèn)題。針對(duì)這種情況，Google搜索引擎開(kāi)發(fā)人員提出了一種模型，稱為MapReduce編程模型，把分布運(yùn)算帶來(lái)的細(xì)節(jié)問(wèn)題，如數(shù)據(jù)分割、容錯(cuò)機(jī)制、負(fù)載均衡等封裝在一個(gè)底層包里面隱藏起來(lái)，開(kāi)發(fā)人員只需考慮接口，實(shí)現(xiàn)直觀的算法。也就是說(shuō)，基于MapReduce模型實(shí)現(xiàn)的程序可以自動(dòng)分發(fā)到多個(gè)機(jī)器并行運(yùn)算，由底層軟件包進(jìn)行數(shù)據(jù)分割、任務(wù)調(diào)度、錯(cuò)誤處理以及相關(guān)的主機(jī)通信，使得沒(méi)有任何分布式系統(tǒng)開(kāi)發(fā)經(jīng)驗(yàn)的人也可以利用分布式系統(tǒng)的巨大運(yùn)算能力。

MapReduce模型的核心是Map函數(shù)和Reduce函數(shù)，Map函數(shù)把輸入的一個(gè)[關(guān)鍵字/值]生成多個(gè)[臨時(shí)關(guān)鍵字/臨時(shí)值]，作為中間結(jié)果；Reduce函數(shù)把Map函數(shù)產(chǎn)生的中間結(jié)果作為輸入，把具有相同臨時(shí)關(guān)鍵字的多個(gè)臨時(shí)值合并起來(lái)，得到最終結(jié)果，如圖8-4所示。圖8-4MapReduce的任務(wù)處理流程在搜索引擎系統(tǒng)中，很多運(yùn)算都可以用這個(gè)模型來(lái)表示。比如，統(tǒng)計(jì)一個(gè)頁(yè)面的鏈入U(xiǎn)RL，可以用下面的Map函數(shù)和Reduce函數(shù)表示。Map函數(shù)為在source頁(yè)面碰到的每一個(gè)鏈接到target的鏈接，輸出〈target，source〉；Reduce函數(shù)把target相同的輸出合并起來(lái)，得到〈target，list(source)〉，它就是所有鏈接到target的網(wǎng)頁(yè)集合。倒排索引的建立也可以用這個(gè)模型，Map函數(shù)分析每一個(gè)文檔，輸出一系列的〈word，documentID〉；Reduce函數(shù)接受所有的中間結(jié)果，并根據(jù)documentID進(jìn)行排序，得到〈word，list(documentID)〉。最后再把Reduce函數(shù)輸出的結(jié)果集合起來(lái)，就是一個(gè)簡(jiǎn)單的倒排文件了。

【例8-1】

統(tǒng)計(jì)一個(gè)文檔集合中各個(gè)詞出現(xiàn)的次數(shù)。

解：可以用MapReduce方式編寫，編程例子如下：Map(Stringkey，Stringvalue):

//key：documentname

//value：documentcontents

Foreachwordinvalue:

EmitIntermedicte(w，″1″)；

Reduce(Stringkey，Iteratorvalues):

//key：aword

//values：alistofcounts

intresult=0;

foreachvinvalues：

result+=ParseInt(v);

Emit(AsString(result));在本例中，Map函數(shù)把遇到的單詞和出現(xiàn)次數(shù)(這里為1)作為中間結(jié)果輸出；Reduce函數(shù)把同一個(gè)單詞的中間結(jié)果加在一起。

MapReduce是一個(gè)并行編程模型，這個(gè)模型可以方便地處理實(shí)際問(wèn)題，它隱藏了分布運(yùn)算量進(jìn)行并發(fā)運(yùn)算后帶來(lái)的數(shù)據(jù)分割、容錯(cuò)機(jī)制、負(fù)載均衡等問(wèn)題，極大簡(jiǎn)化了并行編程的復(fù)雜度。開(kāi)發(fā)人員只要把算法描述為Map和Reduce函數(shù)，就可以自動(dòng)利用分布資源，高效進(jìn)行并行運(yùn)算。8.1.4數(shù)據(jù)并行

在進(jìn)行查詢之間的并行時(shí)，檢索系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)通常不需要改變。而對(duì)于單條查詢內(nèi)部的并行處理，則需要對(duì)原有串行信息檢索的數(shù)據(jù)結(jié)構(gòu)進(jìn)行相應(yīng)的改變。檢索系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)就是倒排索引。因此要考慮進(jìn)行倒排索引分割。

1．倒排索引分割

倒排索引分割可以分為兩種，一種是基于文檔的倒排索引分割(DocumentPartitioning)，另一種是基于查詢項(xiàng)的倒排索引分割(TermPartitioning)。

基于文檔的倒排索引分割有兩種實(shí)現(xiàn)方法：物理文檔分割(PhysicalDocumentPartitioning)和邏輯文檔分割(LogicalDocumentPartitioning)。邏輯文檔分割需要對(duì)倒排文件進(jìn)行擴(kuò)展，讓每個(gè)并行進(jìn)程能夠直接訪問(wèn)一部分索引，這些索引對(duì)應(yīng)于處理器所要處理的那部分文檔子集。物理文檔分割則不僅將數(shù)據(jù)集分割，而且將倒排索引表也同時(shí)進(jìn)行分割，每個(gè)數(shù)據(jù)子集擁有自己獨(dú)立的索引倒排結(jié)構(gòu)。對(duì)于邏輯文檔分割，倒排索引表并不物理上進(jìn)行分割，而是增加一個(gè)處理機(jī)分配表，整張倒排索引表則被多個(gè)處理器共享使用，如圖8-5所示。圖8-5邏輯文檔分割[8]邏輯文檔分割后的檢索過(guò)程：用戶輸入查詢，代理將所需詞典詞條和所有postinglist放入共享內(nèi)存，每個(gè)處理器負(fù)責(zé)訪問(wèn)各自的文檔信息，進(jìn)行相似度計(jì)算，最后將結(jié)果匯總。因?yàn)椋鄠€(gè)處理器對(duì)索引的訪問(wèn)都是“讀”操作，所以沒(méi)有訪問(wèn)沖突問(wèn)題。每個(gè)處理器返回結(jié)果都在自己的文檔子集中，所以也沒(méi)有“寫”沖突。物理文檔分割則是把文檔分割為離散的、自包含的文檔子集，每個(gè)子集對(duì)應(yīng)一個(gè)并行處理器，每個(gè)子集有自己的倒排文件。物理倒排表分割后，每個(gè)子集合具有自己獨(dú)立的倒排表結(jié)構(gòu)，因此可以供不同的處理器單獨(dú)調(diào)用，相對(duì)比較靈活。但是，由于獨(dú)立的倒排表沒(méi)有全局的統(tǒng)計(jì)信息(在進(jìn)行檢索時(shí)通常需要全局的統(tǒng)計(jì)信息來(lái)計(jì)算文檔和查詢的匹配相似度)，所以對(duì)每個(gè)子集進(jìn)行檢索時(shí)必須要有另外的處理來(lái)獲得全局信息。方法通常有兩種：一種是采用復(fù)制的方法，即將全局信息復(fù)制多份分配到每個(gè)獨(dú)立的索引倒排表中；另一種是在每個(gè)子集合檢索時(shí)分兩步走，第一步獲取全局信息表，第二步才進(jìn)行檢索。前一種方法比較耗費(fèi)空間，對(duì)索引表的更新也比較復(fù)雜；后一種方法需要較大的通信開(kāi)銷。總的來(lái)說(shuō)，邏輯文檔分割方法的通信開(kāi)銷很小，因此總體性能會(huì)高于物理文檔分割，但是必須要對(duì)普通倒排表增加額外的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行轉(zhuǎn)換。而物理分割方法的靈活性比較強(qiáng)，每個(gè)文檔子集可以單獨(dú)檢索。通過(guò)物理分割的方法，很容易將非并行的信息檢索系統(tǒng)轉(zhuǎn)換為并行的檢索系統(tǒng)。

使用查詢項(xiàng)分割方法時(shí)，要將每個(gè)關(guān)鍵詞項(xiàng)分配到不同處理器上。對(duì)于倒排表來(lái)說(shuō)，就是將關(guān)鍵詞項(xiàng)表(postinglist)進(jìn)行分割(邏輯的或者物理的)，分別對(duì)應(yīng)到不同的處理器上。在進(jìn)行查詢時(shí)，查詢項(xiàng)將被分解成多個(gè)關(guān)鍵詞查詢，每個(gè)關(guān)鍵詞對(duì)應(yīng)不同的處理器分別進(jìn)行處理。處理結(jié)果按照查詢的語(yǔ)義進(jìn)行合并。例如，如果是多個(gè)關(guān)鍵詞布爾表達(dá)式查詢，如查詢“并行AND檢索”，則合并的主要工作是進(jìn)行布爾操作。如果是需要對(duì)多個(gè)子結(jié)果進(jìn)行排序，則合并的主要工作是評(píng)分歸一化并排序。相對(duì)而言，數(shù)據(jù)集分割方法能夠提供更簡(jiǎn)單的倒排表構(gòu)建和維護(hù)。Jeong和Omiecinski通過(guò)實(shí)驗(yàn)對(duì)文檔分割方法和查詢項(xiàng)分割方法進(jìn)行了比較[9]：假設(shè)每個(gè)處理器有自己的I/O通道和磁盤，當(dāng)關(guān)鍵詞在文檔和查詢中呈偏態(tài)分布(skewed)時(shí)，采用數(shù)據(jù)集分割的方法性能較好；而當(dāng)關(guān)鍵詞在查詢中呈均勻(uniform)分布時(shí)，查詢項(xiàng)分割方法更優(yōu)越。

數(shù)據(jù)分割后，需要存放到文件系統(tǒng)上供多處理器并發(fā)讀寫。普通的文件系統(tǒng)通常很難滿足搜索引擎大規(guī)模數(shù)據(jù)讀取的需求。下面介紹Google的并行文件系統(tǒng)GFS。

2．并行文件系統(tǒng)GFS

GFS是Google為搜索引擎系統(tǒng)量身定做的文件系統(tǒng)。在Google看來(lái)，用于搜索引擎的文件系統(tǒng)必須符合下面的應(yīng)用需求：

●文件系統(tǒng)是建立在廉價(jià)通用主機(jī)平臺(tái)上的，這些硬件可能經(jīng)常出問(wèn)題。為此，文件系統(tǒng)必須能夠一直監(jiān)視自己的狀態(tài)并從災(zāi)難中恢復(fù)過(guò)來(lái)。

●文件系統(tǒng)存儲(chǔ)著許多大文件。數(shù)目大概是幾百萬(wàn)個(gè)，大小為100MB或者更大，幾GB的文件在系統(tǒng)中也是常見(jiàn)的。小的文件也要支持，不過(guò)可以不用專門為其作優(yōu)化處理。

●需要支持兩種類型的讀取方式：大規(guī)模流讀取方式和小規(guī)模隨機(jī)讀取方式。在大規(guī)模流讀取中，一個(gè)操作通常會(huì)從一個(gè)連續(xù)的文件區(qū)域中讀取幾百K或者更多的數(shù)據(jù)。隨機(jī)讀取則可能在任意位置讀取幾KB的數(shù)據(jù)。●寫的方式和讀的方式也類似。大量的數(shù)據(jù)通常以追加的方式添加到文件最后，因?yàn)檫@些數(shù)據(jù)一次寫入后通常就不再更改了。隨機(jī)寫入也支持，但不作優(yōu)化。

●系統(tǒng)必須能夠高效地實(shí)現(xiàn)特定的原語(yǔ)，保證多個(gè)客戶端能并發(fā)地對(duì)同一個(gè)文件進(jìn)行追加記錄。

●對(duì)于搜索引擎的文件系統(tǒng)而言，穩(wěn)定的高帶寬比低延時(shí)更重要。大多數(shù)應(yīng)用程序，需要在高傳輸速率下，大塊地操作數(shù)據(jù)。

為此，GFS提供了文件系統(tǒng)常用的接口，比如create、delete、open、close、read、write。同時(shí)，還特別地增加了兩個(gè)原語(yǔ)：snapshot和recordappend。snapshot操作以最低開(kāi)銷拷貝一個(gè)文件和目錄。recordappend操作讓多個(gè)客戶端并發(fā)地給同一個(gè)文件追加記錄。

GFS可建立在通用主機(jī)組成的集群系統(tǒng)上，包括一個(gè)主節(jié)點(diǎn)(GFSmaster)，多個(gè)塊服務(wù)器(chunkserver)節(jié)點(diǎn)和客戶端(GFSclient)，如圖8-6所示。節(jié)點(diǎn)運(yùn)行Linux操作系統(tǒng)，在一臺(tái)機(jī)器上可同時(shí)部署塊服務(wù)器和客戶端。圖8-6GFS架構(gòu)[3]在GFS中，文件被分成固定大小的塊(chunk)，塊的大小是固定的64MB。塊創(chuàng)建的時(shí)候主節(jié)點(diǎn)會(huì)為其指定一個(gè)全局唯一的64位的句柄(chunkhandle)，并以Linux文件的形式保存在塊服務(wù)器的本地磁盤上。利用句柄和字節(jié)范圍對(duì)塊進(jìn)行讀寫訪問(wèn)。為了提高可靠性，塊在其他塊服務(wù)器上會(huì)有副本，通常有3個(gè)副本，用戶也可以根據(jù)需要指定副本數(shù)目。

主節(jié)點(diǎn)管理文件系統(tǒng)的所有元數(shù)據(jù)信息，包括命名空間、訪問(wèn)控制、文件到塊的映射表、塊的位置等。它同時(shí)控制文件系統(tǒng)的全局性操作，管理整個(gè)系統(tǒng)的所有塊副本，決定塊的位置，創(chuàng)建新塊和相應(yīng)的副本，協(xié)調(diào)多變的系統(tǒng)活動(dòng)以保持塊被完全復(fù)制，均衡所有塊服務(wù)器之間的負(fù)載，回收沒(méi)有使用的存儲(chǔ)空間。主節(jié)點(diǎn)會(huì)定時(shí)通過(guò)心跳信息與塊服務(wù)器進(jìn)行交互，發(fā)送指令同時(shí)收集塊服務(wù)器的狀態(tài)信息。

GFS客戶端實(shí)現(xiàn)文件系統(tǒng)API，與主節(jié)點(diǎn)和塊服務(wù)器進(jìn)行交互，進(jìn)行讀寫操作。應(yīng)用程序利用GFSClient就可以訪問(wèn)文件系統(tǒng)?？蛻舳藦闹鞴?jié)點(diǎn)獲取元數(shù)據(jù)信息后，就直接與塊服務(wù)器交互，從塊服務(wù)器獲取數(shù)據(jù)。

下面對(duì)照?qǐng)D8-6，說(shuō)明GFS的各個(gè)模塊之間是如何交互完成一個(gè)讀操作的。

GFS中執(zhí)行一個(gè)簡(jiǎn)單的讀數(shù)據(jù)操作的工作流程如下：客戶端可以把數(shù)據(jù)的偏移位置(offset)轉(zhuǎn)換為塊內(nèi)索引號(hào)(chunkindex)，并和文件名(filename)一起發(fā)送到主節(jié)點(diǎn)，主節(jié)點(diǎn)把請(qǐng)求塊的句柄和塊的位置(chunklocation)發(fā)回到客戶端；客戶端接著從多個(gè)副本中選擇一個(gè)，通常選擇離自己最近的塊服務(wù)器，把句柄、偏移位置和讀取字節(jié)長(zhǎng)度發(fā)送過(guò)去；之后，數(shù)據(jù)的傳送在客戶端與塊服務(wù)器之間進(jìn)行，不再需要主節(jié)點(diǎn)的參與，如圖8-6黑色的數(shù)據(jù)線所示。一般數(shù)據(jù)訪問(wèn)存在空間局部性，以后如果該客戶端需要訪問(wèn)同一塊服務(wù)器中的數(shù)據(jù)，不再向主節(jié)點(diǎn)發(fā)送請(qǐng)求，而是直接向塊服務(wù)器發(fā)送數(shù)據(jù)讀取請(qǐng)求。

GFS采用一個(gè)松散的一致性模型，不僅能很好地支持分布式應(yīng)用，而且實(shí)現(xiàn)起來(lái)也方便、高效。

8.2分布式信息檢索

與并行檢索系統(tǒng)不同，一個(gè)分布式信息檢索系統(tǒng)(DistributedInformationRetrieval，DIR)由多個(gè)信息資源服務(wù)器(CollectionServers)和一個(gè)或多個(gè)代理服務(wù)器(Broker)兩部分組成。用戶向代理服務(wù)器提交查詢，代理服務(wù)器將會(huì)用這個(gè)查詢檢索信息資源服務(wù)器的子集完成所需信息的查找。子集中的每個(gè)信息庫(kù)服務(wù)器反饋給代理服務(wù)器一個(gè)按相關(guān)度由大到小排列的信息列表。最后，代理服務(wù)器對(duì)所有的結(jié)果

列表進(jìn)行整合，形成新的信息列表反饋給用戶。

分布式檢索系統(tǒng)的體系結(jié)構(gòu)由下面幾個(gè)部分構(gòu)成，如圖8-7所示。相對(duì)于集中式信息檢索系統(tǒng)，分布式信息檢索系統(tǒng)的構(gòu)建和工作流程模式有很大的不同：圖8-7分布式檢索系統(tǒng)的體系架構(gòu)

(1)資源選擇(CollectionResource)：獲取一個(gè)資源的內(nèi)容描述(CollectionDescription)，根據(jù)資源內(nèi)容描述符和查詢的比較，決定最可能包含所需信息的資源，對(duì)每一個(gè)查詢可能都要執(zhí)行這個(gè)操作；

(2)文檔選擇：對(duì)選擇的目標(biāo)資源進(jìn)行檢索，并選擇相關(guān)文檔；

(3)信息融合：把來(lái)自不同資源的相關(guān)文檔合并為結(jié)果列表，并輸出給用戶。

歸納而言，分布式信息檢索系統(tǒng)需要解決資源選擇、文檔選擇和信息融合三大問(wèn)題，下節(jié)以元搜索引擎為例進(jìn)行說(shuō)明。

8.3元搜索引擎

元搜索引擎是分布式信息檢索的典型應(yīng)用。元搜索引擎被稱為搜索引擎之上的搜索引擎，它自己并不收集網(wǎng)站或網(wǎng)頁(yè)信息，通常也沒(méi)有自己的資源庫(kù)和網(wǎng)絡(luò)爬蟲(chóng)。元搜索引擎通過(guò)調(diào)用其他獨(dú)立搜索引擎來(lái)完成搜索功能。用戶在元搜索引擎的用戶界面提交查詢，然后元搜索引擎把這一查詢請(qǐng)求發(fā)送給許多獨(dú)立的搜索引擎。由于不同的搜索引擎可能會(huì)有不同的接受命令的格式，所以，用戶查詢請(qǐng)求應(yīng)該先轉(zhuǎn)換成其他搜索引擎能夠接受的命令格式。然后元搜索引擎把從每個(gè)獨(dú)立搜索引擎返回的結(jié)果合并成一個(gè)單一的排序列表，并返回給用戶。元搜索引擎原理如圖8-8所示。圖8-8元搜索引擎原理圖從元搜索引擎的結(jié)構(gòu)中，元搜索引擎的技術(shù)重點(diǎn)在于查詢前的處理(檢索請(qǐng)求提交機(jī)制和檢索接口代理)和結(jié)果的集成。元搜索引擎可以靈活地選擇所要采用的獨(dú)立搜索引擎。它一般都是選擇那些比較典型的、性能優(yōu)異的獨(dú)立搜索引擎。這種強(qiáng)強(qiáng)聯(lián)合的結(jié)果保證了搜索結(jié)果的權(quán)威性和可靠性。它還可以充分發(fā)揮各個(gè)獨(dú)立搜索引擎在某個(gè)搜索領(lǐng)域的功能，彌補(bǔ)獨(dú)立搜索引擎信息覆蓋面的局限性?？偟膩?lái)說(shuō)，元搜索引擎與獨(dú)立搜索引擎相比，具有如下主要優(yōu)點(diǎn)：

(1)信息的覆蓋面。元搜索引擎一般都要默認(rèn)調(diào)用它自己認(rèn)為比較好的若干個(gè)普通搜索引擎，而且大多數(shù)元搜索引擎都提供給用戶在一定范圍內(nèi)選擇搜索引擎的功能。有些元搜索引擎還以頻道的方式為用戶提供專業(yè)搜索引擎的分類。這樣，用戶可以根據(jù)自己的喜好和要查詢的內(nèi)容選擇相應(yīng)的搜索引擎。

(2)搜索結(jié)果的權(quán)威性和可靠性。在獨(dú)立搜索引擎中，索引數(shù)據(jù)庫(kù)的更新需要一定的周期，而且搜集的信息也各有一定的側(cè)重，元搜索引擎調(diào)用多個(gè)獨(dú)立搜索引擎獲取搜索結(jié)果，這種方式首先保證了信息的互補(bǔ)性，其次與獨(dú)立搜索引擎相比，提高了信息的新鮮度。如果同樣的搜索結(jié)果在多個(gè)獨(dú)立搜索引擎中同時(shí)出現(xiàn)，那么說(shuō)明這個(gè)搜索結(jié)果比較重要。這樣就避免了一些獨(dú)立搜索引擎人工干預(yù)搜索排名的缺點(diǎn)，使得搜索結(jié)果的排序更加公正。有些元搜索引擎還檢查搜索結(jié)果鏈接的存在性，這樣可以保證用戶得到的元搜索結(jié)果的可靠性。

(3)易維護(hù)性。所謂易維護(hù)性，是針對(duì)元搜索引擎的管理者而言的。元搜索引擎省卻了獨(dú)立搜索引擎中收集和存儲(chǔ)網(wǎng)頁(yè)、建立和存儲(chǔ)索引的工作。它將自己所調(diào)用的搜索引擎看成一個(gè)可以獨(dú)立完成一定功能的實(shí)體，不需要去維護(hù)它們，只需知道它們的調(diào)用接口即可。元搜索引擎的查詢精度在很大程度上依賴于它所調(diào)用的搜索引擎的查詢精度，所以在設(shè)計(jì)元搜索引擎時(shí)可以把主要精力放在搜索引擎的選擇、查詢請(qǐng)求的優(yōu)化和搜索結(jié)果的優(yōu)化等方面。一般的元搜索引擎都提供了對(duì)應(yīng)的優(yōu)化機(jī)制。

元搜索引擎的核心問(wèn)題是解決如何調(diào)用其他搜索引擎的索引數(shù)據(jù)庫(kù)，如何獲取查詢?cè)~在其他搜索引擎中的查詢結(jié)果以及如何評(píng)價(jià)、排序、呈現(xiàn)結(jié)果等，解決這些問(wèn)題的主要技術(shù)有用戶查詢轉(zhuǎn)換、檢索機(jī)制設(shè)計(jì)與優(yōu)化、檢索結(jié)果輸出、分布式數(shù)據(jù)庫(kù)調(diào)用等技術(shù)。

1.用戶查詢轉(zhuǎn)換

元搜索引擎定制查詢界面供用戶輸入查詢?cè)~，需要根據(jù)不同的搜索引擎轉(zhuǎn)換成可以進(jìn)行檢索的查詢表達(dá)式，不同的搜索引擎有不同的檢索語(yǔ)法和操作符使用技巧，需要對(duì)提問(wèn)進(jìn)行處理。同時(shí)要對(duì)搜索引擎不能處理的檢索方式進(jìn)行排除，并選擇一種合適的方式來(lái)匹配。

2.檢索機(jī)制設(shè)計(jì)與優(yōu)化

對(duì)于搜索引擎初始化方式、各個(gè)搜索引擎結(jié)果平衡處理等問(wèn)題，都需要在檢索機(jī)制的設(shè)計(jì)初期進(jìn)行規(guī)劃，這主要受到檢索反饋速度、檢索結(jié)果滿意度等因素的影響，目前，搜索引擎初始化主要有用戶參與、系統(tǒng)默認(rèn)或自動(dòng)隨機(jī)處理等方式。檢索結(jié)果的處理需要考慮如何衡量不同搜索引擎結(jié)果之間的相關(guān)程度。簡(jiǎn)單的處理方式是以搜索引擎為單位，在選定的獨(dú)立搜索引擎下面顯示比較靠前的結(jié)果；復(fù)雜的處理方式是以記錄為單位，通過(guò)判定某一記錄在多個(gè)獨(dú)立搜索引擎中被評(píng)價(jià)的指數(shù)，如果多個(gè)獨(dú)立搜索引擎都檢出該結(jié)果，那么該記錄將被排列在整個(gè)顯示的前面，同時(shí)后面標(biāo)注出是在哪些搜索引擎中檢出的。

3.檢索結(jié)果輸出

結(jié)果輸出處理一般有兩種形式：直接引用原始結(jié)果頁(yè)面技術(shù)與結(jié)果頁(yè)面定制技術(shù)。直接引用原始結(jié)果頁(yè)面是元搜索技術(shù)中較為簡(jiǎn)單易行的方式，在自制的頁(yè)面中將表單提交的對(duì)象修改為獨(dú)立搜索引擎調(diào)用的腳本文件。在這種情況中，一般無(wú)需進(jìn)行結(jié)果去重，只需完成表單提交的轉(zhuǎn)換即可。結(jié)果頁(yè)面定制技術(shù)則要對(duì)結(jié)果進(jìn)行更多的加工處理，主要包括：①去重和遴選處理，選擇相關(guān)程度高的記錄并加以顯示，同時(shí)刪除可能被多個(gè)獨(dú)立搜索引擎同時(shí)檢出的記錄；②結(jié)果的再度排序，元搜索引擎并不是完全選取在獨(dú)立搜索引擎中得到的結(jié)果的前幾條記錄，而是需要再度排序，根據(jù)檢索機(jī)制對(duì)相關(guān)度判斷的標(biāo)準(zhǔn)來(lái)比較各個(gè)搜索引擎得到的結(jié)果。

4.分布式數(shù)據(jù)庫(kù)調(diào)用技術(shù)

直接調(diào)用獨(dú)立搜索引擎結(jié)果頁(yè)面的元搜索引擎不需與獨(dú)立搜索引擎的索引數(shù)據(jù)庫(kù)直接交換數(shù)據(jù)，只需直接引用獨(dú)立搜索引擎的結(jié)果頁(yè)面；而查詢多個(gè)搜索引擎的元搜索引擎則需在滿足獨(dú)立搜索引擎的數(shù)據(jù)庫(kù)訪問(wèn)權(quán)限的情況下，實(shí)現(xiàn)對(duì)其索引數(shù)據(jù)庫(kù)的訪問(wèn)和二次開(kāi)發(fā)。各獨(dú)立搜索引擎的數(shù)據(jù)庫(kù)分布在不同的地域，要實(shí)現(xiàn)對(duì)異地、異構(gòu)數(shù)據(jù)庫(kù)的訪問(wèn)，需要使用一系列諸如分布計(jì)算等相關(guān)的核心技術(shù)。同時(shí)，不同數(shù)據(jù)庫(kù)調(diào)用結(jié)果響應(yīng)時(shí)間長(zhǎng)短不一，這也會(huì)直接影響到結(jié)果頁(yè)面的呈現(xiàn)。8.3.1系統(tǒng)架構(gòu)

元搜索引擎的參考軟件組成結(jié)構(gòu)如圖8-9所示。下面討論每個(gè)軟件組成的功能和它們之間的相互作用。圖8-9元搜索引擎系統(tǒng)架構(gòu)圖

1．資源選擇

如果元搜索引擎中的成員搜索引擎(ComponentSearchEngines)的數(shù)目較少，就把用戶的查詢請(qǐng)求發(fā)送給每個(gè)成員搜索引擎。但是，當(dāng)成員搜索引擎的數(shù)量很大時(shí)，把查詢請(qǐng)求發(fā)送給每個(gè)成員搜索引擎是不可能的，這是因?yàn)樵谶@種情況下，對(duì)于這個(gè)查詢請(qǐng)求，本地?cái)?shù)據(jù)的很大部分都是沒(méi)有用的。例如，假設(shè)用戶只對(duì)查詢的10個(gè)最匹配的文檔感興趣，很明顯，那10個(gè)想要的文檔最多在10個(gè)成員搜索引擎的索引庫(kù)中。因此，對(duì)于這個(gè)查詢請(qǐng)求來(lái)講，如果搜索引擎的數(shù)量遠(yuǎn)遠(yuǎn)超過(guò)10個(gè)，那么將會(huì)有很大部分的成員搜索引擎沒(méi)有用。發(fā)送查詢請(qǐng)求到?jīng)]有用的成員搜索引擎會(huì)出現(xiàn)一些問(wèn)題。首先，分派查詢請(qǐng)求到?jīng)]有用的成員搜索引擎消耗元搜索引擎站點(diǎn)的資源。第二，從元搜索引擎?zhèn)鬏敳樵冋?qǐng)求到?jīng)]有用的成員搜索引擎，和從這些搜索引擎向元搜索引擎?zhèn)魉蜎](méi)有用的文檔都將帶來(lái)不必要的網(wǎng)絡(luò)流量。第三，評(píng)估一個(gè)無(wú)用索引庫(kù)的查詢請(qǐng)求將會(huì)浪費(fèi)本地系統(tǒng)的資源。第四，如果從無(wú)用的成員搜索引擎返回大量的文檔，元搜索引擎就要花費(fèi)大量的精力來(lái)識(shí)別哪些是有用的文檔。因此，發(fā)送每個(gè)用戶的查詢請(qǐng)求到潛在有用的搜索引擎是很重要的。對(duì)于一個(gè)已知的查詢請(qǐng)求，搜索潛在有用的搜索引擎的問(wèn)題就是資源選擇問(wèn)題。資源選擇器就是負(fù)責(zé)對(duì)于每個(gè)用戶的查詢請(qǐng)求，識(shí)別出潛在有用的成員搜索引擎。一個(gè)好的資源選擇器應(yīng)該能夠識(shí)別出盡可能多的潛在有用成員搜索引擎，同時(shí)能夠使無(wú)用成員搜索引擎當(dāng)作潛在有用成員搜索引擎的可能性最小化。當(dāng)一個(gè)元搜索引擎從用戶接收到一個(gè)查詢時(shí)，它就會(huì)調(diào)用資源選擇器來(lái)選擇元搜索引擎的成員搜索引擎，并將查詢發(fā)向這些成員搜索引擎。一個(gè)好的資源選擇算法應(yīng)該能準(zhǔn)確地找到潛在有用的成員搜索引擎，目前已經(jīng)有很多方法來(lái)實(shí)現(xiàn)資源選擇問(wèn)題(相關(guān)算法詳見(jiàn)8.3.2節(jié))，這些方法的區(qū)別都體現(xiàn)在如下一些方面：資源的表示、根據(jù)有關(guān)查詢選擇資源有用信息的方法、資源選擇有用性的評(píng)價(jià)等。

2．文檔選擇

對(duì)于每個(gè)資源選擇器選擇的搜索引擎，文檔選擇器決定從搜索引擎的索引庫(kù)中返回什么文檔。目的是從搜索引擎中返回盡可能多的潛在有用的文檔，同時(shí)最小化返回?zé)o用的文檔數(shù)。如果從一個(gè)搜索引擎中返回很多無(wú)用的文檔，元搜索引擎就得花很大的精力來(lái)區(qū)分哪些是潛在的有用文檔。一個(gè)最簡(jiǎn)單的方法是讓每個(gè)資源服務(wù)器都將相似的文檔返回給用戶，但是這樣會(huì)導(dǎo)致太多的文檔返回，增加了通信的開(kāi)銷和存儲(chǔ)空間，同時(shí)也增加了結(jié)果融合的難度。如前面所討論的，資源服務(wù)器通常的做法都是將檢索到的文檔按相似度降序排列。因而，文檔選擇可以分解為下面兩個(gè)問(wèn)題：

(1)設(shè)置從資源庫(kù)返回的檢索文檔數(shù)，如果從資源庫(kù)中返回k個(gè)文檔，那么將選擇相似度最大的k個(gè)文檔；

(2)為資源庫(kù)設(shè)定一個(gè)門限，使得只有相似度大于這個(gè)門限的資源庫(kù)中的文檔才會(huì)被返回給用戶。

3．查詢分發(fā)

查詢分發(fā)負(fù)責(zé)和被選定的搜索引擎服務(wù)器間建立連接，并負(fù)責(zé)發(fā)送查詢請(qǐng)求。這個(gè)過(guò)程通常使用HTTP協(xié)議，每個(gè)搜索引擎對(duì)于HTTP請(qǐng)求方法(例如，GET方法和POST方法)和查詢格式都有它自己的要求。查詢分發(fā)必須正確滿足每個(gè)成員搜索引擎的要求。一般情況下，發(fā)送給每個(gè)特定搜索引擎的查詢請(qǐng)求很可能與元搜索引擎收到的查詢請(qǐng)求不相同。也就是說(shuō)，最初的查詢請(qǐng)求在發(fā)送給成員搜索引擎之前，被翻譯成一個(gè)新的查詢請(qǐng)求。Chang等人提出了查詢翻譯的一些規(guī)則[30]。對(duì)于一個(gè)向量空間查詢，查詢翻譯通常直接保留用戶查詢中的所有詞語(yǔ)。也有兩個(gè)例外，第一，在將查詢發(fā)給成員搜索引擎之前，原始的用戶查詢的相對(duì)詞頻權(quán)重可能會(huì)有所調(diào)整。通過(guò)重復(fù)某個(gè)查詢?cè)~到特定的次數(shù)，就能改變不同查詢?cè)~的相對(duì)重要性。第二，從一個(gè)成員搜索引擎檢索到的文檔數(shù)量可能也和用戶想要的有差距。例如，假定一個(gè)查詢，用戶想要m篇文檔，文檔選擇器可能決定要從某個(gè)成員搜索引擎中檢索到k篇文檔。在這個(gè)例子中，k就是由翻譯查詢發(fā)給成員搜索引擎的，很明顯，k不同于m。

4．結(jié)果融合

從被選定的成員搜索引擎的得到結(jié)果返回給元搜索引擎，結(jié)果融合把這些結(jié)果組合成一個(gè)單一的排序列表。根據(jù)用戶的需要，返回列表的前m個(gè)文檔給用戶。一個(gè)好的結(jié)果融合應(yīng)該把所有返回的文檔按照降序排列。

通常，由于不同的數(shù)據(jù)庫(kù)可能有不同類型的搜索引擎和不同的文本統(tǒng)計(jì)，所以，結(jié)果融合的工作是非常困難的。最準(zhǔn)確的解決方案是規(guī)范化從不同成員搜索引擎檢索得到的文檔得分，或者使用需要合作的全局文檔統(tǒng)計(jì)，或者是在搜索客戶端重新計(jì)算文檔得分。8.3.2資源選擇

資源選擇就是指選擇最合適的信息資源的子集，以使這些子集包含與查詢相關(guān)的信息量最多。資源選擇最簡(jiǎn)單的方法是用戶自己選擇信息資源庫(kù)去進(jìn)行檢索，這是目前分布式搜索引擎(如元搜索引擎)常用的方法。但有時(shí)用戶對(duì)信息資源的利用知識(shí)有限，所以有的分布式信息檢索中要求檢索系統(tǒng)對(duì)用戶的查詢能夠自動(dòng)地選擇信息資源，并且保證這些信息資源中包含與用戶查詢相關(guān)的檢索內(nèi)容最多。同時(shí)，如果將查詢?cè)诿總€(gè)信息資源庫(kù)中進(jìn)行檢索，檢索的完整性效果自然是最好的，但是這樣做的成本很高，而且還會(huì)造成檢索響應(yīng)時(shí)間過(guò)長(zhǎng)，增加用戶的負(fù)擔(dān)，因而對(duì)信息資源庫(kù)進(jìn)行選擇的目標(biāo)是盡可能降低信息庫(kù)子集的數(shù)量，盡量保證檢索的效率。給定一個(gè)需求信息和一組資源描述集，系統(tǒng)是怎樣選擇檢索的資源呢？資源選擇的等價(jià)問(wèn)題是根據(jù)滿足信息需求的條件來(lái)對(duì)資源進(jìn)行有效的排序，以便用戶能根據(jù)排序的結(jié)果進(jìn)行有針對(duì)性的選擇，這涉及到資源排序的算法問(wèn)題。

Meng和Yu等人將這些方法歸類為以下三種[10]：概略表示方法(RoughRepresentationApproaches)，統(tǒng)計(jì)表示方法(StatisticalRepresentationApproaches)和基于學(xué)習(xí)的表示方法(Learning-basedApproaches)。這些方法的性能評(píng)估可參見(jiàn)文獻(xiàn)[27]。

1．概略表示方法

概略表示方法用一些關(guān)鍵詞和短語(yǔ)來(lái)表示本地資源，但該方法對(duì)于資源的組成只提供了一般的解決措施，因而概略表示方法對(duì)于資源的選擇是不精確的，該方法一般通過(guò)手動(dòng)產(chǎn)生。

每個(gè)資源都要人為手動(dòng)地設(shè)置一兩個(gè)單詞作為主題詞或分類關(guān)鍵詞。用戶查詢只有和關(guān)鍵詞匹配，才能決定哪個(gè)資源是最適合用戶需要的。匹配可能是針對(duì)一個(gè)或多個(gè)領(lǐng)域，如主題、描述等，這些可由用戶選擇。資源的排列也是依照查詢的匹配程度來(lái)進(jìn)行的，這樣用戶就可以從結(jié)果列表中及時(shí)選出所要的信息資源庫(kù)。資源的文本描述轉(zhuǎn)化為一種結(jié)構(gòu)性的表示。這種轉(zhuǎn)換可以手動(dòng)執(zhí)行，WordNet[11]就可以應(yīng)用在消除主題詞(topicalwords)歧義的轉(zhuǎn)化過(guò)程中。

【例8-2】

在文檔WorldFactbook中，語(yǔ)句“Worldfactslistedbycountry”可以轉(zhuǎn)化為如下的結(jié)構(gòu)表示：

Topic：country

Synset：[nation，nationality，land，country，a_people]

Synset：[state，nation，country，land，commonwealth，res_politic]

Synset：[country，state，land，nation]

Info-type：facts在WordNet中，每個(gè)詞有1個(gè)或多個(gè)同義詞集，主題詞“country”有4個(gè)同義詞集，其中3個(gè)是相關(guān)的，所以這3個(gè)被采用。另外一個(gè)集(如[rural_area，country])與語(yǔ)句(Worldfactslistedbycountry)中“country”的含義不一樣，不能匹配，因而被忽略。

除了人工產(chǎn)生的概略表示方法，也有一些自動(dòng)產(chǎn)生的概略表示方法。在Q-Pilot系統(tǒng)中[12]，每個(gè)資源都用一組帶有權(quán)重的詞語(yǔ)的向量來(lái)表示，這些詞語(yǔ)可以通過(guò)搜索引擎的接口頁(yè)面或搜索引擎的鏈接頁(yè)面來(lái)獲得，權(quán)重就是詞頻。當(dāng)連接到搜索引擎時(shí)，只有那些出現(xiàn)在同一行的詞語(yǔ)才會(huì)被采用，并且每個(gè)詞語(yǔ)的權(quán)重就是指文檔中該詞的權(quán)重。概略表示方法的優(yōu)點(diǎn)在于表示簡(jiǎn)單，而且要求存儲(chǔ)空間少。如果所有獨(dú)立檢索系統(tǒng)都專注于各種主題而且其內(nèi)容都能被很容易地歸納，則概略表示方法可以應(yīng)用得很好。但是，一個(gè)資源的簡(jiǎn)短描述往往不能完整充分地表示資源的內(nèi)容，尤其當(dāng)資源包含的內(nèi)容非常廣泛時(shí)?？偟膩?lái)說(shuō)，應(yīng)用這些方法都不大可能檢索到那些潛在有用的數(shù)據(jù)庫(kù)。因而，對(duì)于大型的檢索系統(tǒng)來(lái)說(shuō)，應(yīng)用概略表示方法可能是不夠的。

2．統(tǒng)計(jì)表示方法

統(tǒng)計(jì)表示方法的原理是：考慮資源中每個(gè)文檔中的每個(gè)詞語(yǔ)，并為每個(gè)詞語(yǔ)保留一份或多份統(tǒng)計(jì)信息。如果設(shè)計(jì)得好，則應(yīng)用這種方法可為每個(gè)查詢發(fā)現(xiàn)單個(gè)潛在有用的文檔。這里重點(diǎn)介紹D-WISE方法[13]和CORI方法[14，15]。

1)D-WISE方法

D-WISE(DistributedWebIndexandSearchEngine)是一個(gè)分布式的搜索引擎。在D-WISE中，每個(gè)資源服務(wù)器也稱成員搜索引擎(MetaSearchEngineComponent)，可用其包含的資源庫(kù)中每個(gè)詞語(yǔ)的詞頻和資源中文檔的數(shù)量來(lái)表示。用ni表示第i個(gè)構(gòu)件資源庫(kù)中的文檔數(shù)量，用dfij來(lái)表示第i個(gè)資源庫(kù)中詞語(yǔ)tj的文檔頻率。

假定有用戶查詢q，所有資源庫(kù)都根據(jù)q來(lái)計(jì)算排列得分，這個(gè)分?jǐn)?shù)可以衡量資源庫(kù)的相對(duì)有用性。如果資源庫(kù)A的得分比B高，則認(rèn)為A比B更相關(guān)。計(jì)算得分步驟如下：首先計(jì)算每個(gè)查詢?cè)~語(yǔ)的有效性CV(CueValidity)。假定有詞語(yǔ)tj，對(duì)于第i個(gè)資源庫(kù)，用下列公式計(jì)算CVij：

這里，N是構(gòu)件資源庫(kù)的總的數(shù)量，可以看出，CVij計(jì)算出的是第i個(gè)含有tj資源庫(kù)文檔相對(duì)于其他資源庫(kù)中含有tj的文檔的百分比。如果第i個(gè)資源庫(kù)的比例高于其他的資源庫(kù)，那么CVij的值也就較大。下一步，對(duì)于所有資源庫(kù)，每個(gè)查詢?cè)~語(yǔ)tj的CVij的方差(CueValidityVariance，CVV)用CVVj表示，可用下列式子計(jì)算：(8-1)(8-2)這里，ACVj是所有CVij的平均值。CVVj衡量了所有資源庫(kù)中tj的分布。對(duì)于兩個(gè)詞語(yǔ)tu和tv，如果CVVu>CVVv，則tu對(duì)于區(qū)分不同的構(gòu)件資源庫(kù)比tv更有用。最后，對(duì)于查詢q，構(gòu)件資源庫(kù)的得分可用下面的式子來(lái)計(jì)算得出：(8-3)

這里，M是查詢?cè)~語(yǔ)的數(shù)量。可以看到，資源庫(kù)i的得分是所有查詢?cè)~語(yǔ)的文檔頻率的總和，資源庫(kù)是每個(gè)查詢?cè)~語(yǔ)CVV的加權(quán)。這個(gè)排名得分說(shuō)明可用的查詢?cè)~語(yǔ)集中在哪些地方。如果某個(gè)資源庫(kù)有很多可用的查詢?cè)~語(yǔ)，比其他資源庫(kù)的可用詞語(yǔ)都多，則資源庫(kù)的得分自然也高?？梢钥闯?，這種方法是很簡(jiǎn)單的，但是有兩個(gè)問(wèn)題：首先，排名得分是相對(duì)得分，根據(jù)給定查詢得出資源庫(kù)的真實(shí)得分往往是非常困難的。如果對(duì)于一個(gè)查詢沒(méi)有適用的資源庫(kù)，排在首位的資源庫(kù)的得分往往也是很小的一個(gè)值。而對(duì)另外一個(gè)查詢可能有好多個(gè)適用的資源庫(kù)，那么前10個(gè)資源庫(kù)通常都是很有用的。也就是說(shuō)，相對(duì)資源庫(kù)得分在區(qū)分這些情況時(shí)往往作用不大。其次，該方法的準(zhǔn)確性仍然值得懷疑，例如不能準(zhǔn)確區(qū)分一個(gè)文檔中某個(gè)詞語(yǔ)出現(xiàn)1次和另一個(gè)文檔相同詞語(yǔ)出現(xiàn)100次的區(qū)別。

2)CORI方法

資源庫(kù)檢索推理(CollectionRetrievalInference，CORI)方法把每個(gè)信息庫(kù)都看成是一篇巨大的文獻(xiàn)，資源庫(kù)的排序方法與傳統(tǒng)信息檢索系統(tǒng)中的文檔排序方法相似。在CORI中，用文檔頻率DF(DocumentFrequency)和資源庫(kù)頻率CF(CollectionFrequency)來(lái)表示資源庫(kù)，后者是含有檢索詞的數(shù)據(jù)庫(kù)數(shù)量。

CORI方法是基于推理網(wǎng)絡(luò)[28]的概率方法。就如第2章介紹的檢索模型中應(yīng)用推理網(wǎng)絡(luò)排序文檔的原理一樣，同樣可以用推理網(wǎng)絡(luò)來(lái)排序資源庫(kù)。從概念上，資源庫(kù)可以被認(rèn)為是包含所有檢索詞的超文檔。如果一個(gè)檢索詞出現(xiàn)在資源庫(kù)的k個(gè)文檔中，可以將這個(gè)詞在超文檔中重復(fù)k次，這樣資源庫(kù)中檢索詞的文檔頻率變成了超文檔的詞頻。在分布式檢索系統(tǒng)中，構(gòu)成資源庫(kù)的所有超文檔組成了一個(gè)超文檔資源庫(kù)。用D來(lái)表示這個(gè)超文檔資源庫(kù)。同樣地，在D中，檢索詞的資源庫(kù)頻率變成了文檔頻率。因此，從構(gòu)件資源庫(kù)中，可以獲得超文檔資源庫(kù)中每個(gè)檢索詞的詞頻和文檔頻率。同理，TFw-IDFw(詞頻權(quán)重和反向詞頻權(quán)重)公式也可以用來(lái)計(jì)算每個(gè)超文檔中每個(gè)詞語(yǔ)的權(quán)重，從而可以用權(quán)重向量來(lái)表示每個(gè)超文檔。此外，也可以用余弦函數(shù)來(lái)計(jì)算兩個(gè)超文檔的相似性，然后根據(jù)相似性排序所有資源庫(kù)。對(duì)于查詢q，資源庫(kù)的排名得分是一個(gè)包含了可用文檔資源庫(kù)的估計(jì)概率值(estimatedbelief)，這個(gè)值實(shí)質(zhì)上是一個(gè)聯(lián)合概率。該值可通過(guò)下述方法計(jì)算得到：假定用戶查詢有k個(gè)詞語(yǔ)，t1，…，tk，N是資源庫(kù)的數(shù)量，設(shè)定dfij為第i個(gè)資源庫(kù)Dj中j個(gè)詞語(yǔ)的文檔頻率，dbfj為第j個(gè)詞語(yǔ)的資源庫(kù)頻率。

首先，Di含有檢索詞j的可用文檔的概率值可以用公式計(jì)算：(8-4)其中，(8-5)是一個(gè)根據(jù)Di和Ij來(lái)計(jì)算超文檔中第j個(gè)詞語(yǔ)的詞頻權(quán)重；Ij是基于所有超文檔計(jì)算出的第j個(gè)詞語(yǔ)的反向文檔頻率，(8-6)式(8-4)和式(8-5)中，c1和c2都是取值于0~1之間的常數(shù)，并且有這樣的關(guān)系：(8-7)這是一個(gè)資源庫(kù)Di的函數(shù)。c3和c4都是常數(shù)，dwi是Di中詞語(yǔ)的數(shù)量，adw是資源庫(kù)中詞語(yǔ)數(shù)量的平均值。這4個(gè)常數(shù)可以通過(guò)在測(cè)試集實(shí)驗(yàn)而獲得一些經(jīng)驗(yàn)值[14]。這樣，查詢q中tj的重要性也可以通過(guò)概率p(q|tj)計(jì)算出來(lái)。最后就可以用下面的式子來(lái)計(jì)算排名了：(8-8)

3．基于學(xué)習(xí)的表示方法

基于學(xué)習(xí)的方法是根據(jù)以前的檢索經(jīng)驗(yàn)來(lái)預(yù)測(cè)新查詢的可用資源庫(kù)。獲得檢索經(jīng)驗(yàn)有很多種途徑。首先，訓(xùn)練查詢(TrainingQuery)就是一種，這要求預(yù)先根據(jù)訓(xùn)練查詢來(lái)獲得每個(gè)構(gòu)件資源庫(kù)的檢索知識(shí)，這種方法叫靜態(tài)訓(xùn)練。這種方法的特點(diǎn)是，一旦學(xué)習(xí)到了檢索知識(shí)，就不再改變，因此缺點(diǎn)在于不能適應(yīng)查詢的變化。其次，通過(guò)學(xué)習(xí)用戶的查詢并逐漸積累，不時(shí)更新，這種方法就叫做動(dòng)態(tài)學(xué)習(xí)，該方法的缺點(diǎn)是需要比較長(zhǎng)的時(shí)間才能學(xué)習(xí)到足夠的知識(shí)，以滿足資源選擇需要。綜合前兩點(diǎn)，就有了第三種綜合學(xué)習(xí)方法，先從訓(xùn)練查詢中獲得初始的知識(shí)，再在用戶的查詢基礎(chǔ)之上保持知識(shí)的不斷更新。綜合學(xué)習(xí)方法克服了前兩種方法的缺點(diǎn)。本小節(jié)將介紹幾種基于學(xué)習(xí)的資源庫(kù)選擇方法。

1)MRDD方法

MRDD(ModelingRelevantDocumentDistribution)方法[16]是一個(gè)靜態(tài)學(xué)習(xí)方法。在學(xué)習(xí)過(guò)程中，利用到了一組訓(xùn)練查詢集。該方法中，訓(xùn)練查詢都會(huì)提交給每個(gè)資源庫(kù)使用，從資源庫(kù)返回的文檔中，會(huì)標(biāo)注出相關(guān)文檔，再用一個(gè)向量來(lái)反映相關(guān)文檔的分布，系統(tǒng)在獲得該向量后會(huì)存儲(chǔ)起來(lái)。向量有一個(gè)特定的格式，〈r1，r2，…，rs〉，這里ri是一個(gè)正整數(shù)，表示對(duì)于某個(gè)查詢檢索到的i個(gè)文檔。例如，假定有訓(xùn)練查詢q和一個(gè)資源庫(kù)D，檢索到了100個(gè)文檔，組成序列(d1，d2，…，d100)。在這些文檔中，文檔d1，d4，d10，d17，d30是相關(guān)的，那么相應(yīng)的分布向量則為〈r1，r2，r3，r4，r5〉＝〈1，4，10，17，30〉。在所有的資源庫(kù)都根據(jù)訓(xùn)練查詢獲得分布向量之后，接下來(lái)的工作就是資源庫(kù)選擇了。接收到一個(gè)用戶查詢之后，系統(tǒng)會(huì)將查詢和所有的訓(xùn)練查詢進(jìn)行比較，標(biāo)注出k個(gè)最相似的文檔。然后，對(duì)于每個(gè)數(shù)據(jù)庫(kù)D，計(jì)算對(duì)于k個(gè)向量的平均相關(guān)文檔分布向量，該平均向量將用于選擇資源庫(kù)。

【例8-3】對(duì)于查詢q，有如下3個(gè)資源的平均分布向量：

D1：〈1，4，6，7，10，12，17〉

D2：〈3，5，7，9，15，20〉

D3：〈2，3，6，9，11，16〉若要檢索3篇相關(guān)文檔，為了最大化檢索的準(zhǔn)確率，即盡量少檢索到不相關(guān)文檔，則需要從D1中檢索1篇文檔，從D3中檢索3篇文檔(假定3篇中有兩篇是相關(guān)的)。也就是說(shuō)，D1和D3應(yīng)該被選擇出來(lái)，這個(gè)選擇的準(zhǔn)確率是75%，即4篇文檔中有3篇是相關(guān)的。

在MRDD方法中，表示資源庫(kù)的是訓(xùn)練查詢的一組分布向量集。該方法的主要弱點(diǎn)在于人工手動(dòng)學(xué)習(xí)，難于識(shí)別合適的訓(xùn)練查詢，當(dāng)資源庫(kù)內(nèi)容改變時(shí)，學(xué)習(xí)到的知識(shí)會(huì)使查詢準(zhǔn)確率降低。

2)SavvySearch方法

SavvySearch()是一個(gè)應(yīng)用了動(dòng)態(tài)學(xué)習(xí)方法的元搜索引擎[17]，該方法是在過(guò)去查詢的經(jīng)驗(yàn)上計(jì)算出資源庫(kù)的排名得分。對(duì)于每個(gè)搜索，資源選擇器都要維護(hù)一個(gè)權(quán)重向量(w1，w2，…，wm)，這里wi對(duì)應(yīng)于資源庫(kù)中第i個(gè)詞語(yǔ)。初始狀態(tài)時(shí)，所有的權(quán)重都置為0，當(dāng)用一個(gè)含有詞語(yǔ)ti的查詢從資源庫(kù)D中查找文檔時(shí)，權(quán)重wi會(huì)根據(jù)檢索結(jié)果做出相應(yīng)的調(diào)整。如果搜索引擎沒(méi)有返回該查詢的任何文檔，那么權(quán)重將減少1/k，這里k是查詢中查詢?cè)~的數(shù)量。如果返回結(jié)果中至少有一篇文章被用戶點(diǎn)擊進(jìn)入閱讀，那么權(quán)重也將增加1/k?？梢缘贸鲞@樣的結(jié)論，正數(shù)wi越大，表明數(shù)據(jù)庫(kù)D對(duì)過(guò)去詞語(yǔ)ti響應(yīng)得越好；負(fù)數(shù)的wi則表明響應(yīng)得很差。同樣，SavvySearch也追蹤每個(gè)資源服務(wù)器的最近性能，h表示最近5個(gè)查詢的平均返回文檔數(shù)，r則是最近5個(gè)查詢發(fā)給資源服務(wù)器的響應(yīng)時(shí)間。如果h小于門限值Th(默認(rèn)是1)，對(duì)于每個(gè)成員搜索引擎則計(jì)算出一個(gè)補(bǔ)償值ph，同樣，如果r小于門限值Tr(默認(rèn)是15秒)，則也計(jì)算一個(gè)補(bǔ)償值pr，這里r0＝45是超時(shí)前允許的最大響應(yīng)時(shí)間。(8-9)(8-10)對(duì)于一個(gè)含有詞語(yǔ)t1，…，tk的查詢q，資源庫(kù)D的得分可用下列公式計(jì)算：(8-11)式中：log(N/fi)是詞語(yǔ)ti的反向資源庫(kù)頻率權(quán)重;N是資源庫(kù)數(shù);fi是對(duì)詞語(yǔ)ti有正數(shù)權(quán)重值的資源庫(kù)的數(shù)量。在SavvySearch中，為每個(gè)資源服務(wù)器存儲(chǔ)信息而占用的開(kāi)銷是適中的，而維護(hù)這些信息也無(wú)需花費(fèi)很多精力。但SavvySearch的一個(gè)缺點(diǎn)是：對(duì)于檢索次數(shù)很少的詞語(yǔ)，則檢索的結(jié)果不理想。另外一個(gè)就是SavvySearch對(duì)于用戶反饋也解決得不好，有時(shí)候可能錯(cuò)過(guò)很多可用信息。用戶會(huì)傾向于直接查看排在前面的文檔，而不管這些文檔是否真的有用。這也意味著詞語(yǔ)權(quán)重很容易被調(diào)整，而這些調(diào)整都不是產(chǎn)生權(quán)重機(jī)制的本意。

3)ProFusion方法

ProFusion是一個(gè)應(yīng)用綜合學(xué)習(xí)方法的元搜索引擎的例子[18]。在ProFusion中，采用13組預(yù)定義的分類，“scienceandengineering”，“computerscuence”，“travel”，“medicalandbiotechnology”，“businessandfinance”等，每個(gè)分類都關(guān)聯(lián)一組詞語(yǔ)，用來(lái)反映該分類的主題。使用分類和特定訓(xùn)練集的目的是可以了解到每個(gè)資源庫(kù)對(duì)于不同的分類有不同的結(jié)果。對(duì)于一個(gè)給定的分類C和構(gòu)件資源庫(kù)D，每個(gè)關(guān)聯(lián)的訓(xùn)練查詢都會(huì)提交給D，然后再選擇前10個(gè)標(biāo)注是相關(guān)的文檔。這樣，根據(jù)分類C和查詢，可以計(jì)算出數(shù)據(jù)庫(kù)D的性能得分：(8-12)這里，c是一個(gè)常數(shù)。如果排的第i個(gè)位置的文檔是相關(guān)的，則設(shè)定Ni為1/i；如果文檔不相關(guān)，則設(shè)定Ni為0。R是10個(gè)返回文檔的相關(guān)文檔數(shù)。

可以看到，該方法計(jì)算出的得分涵蓋了每個(gè)相關(guān)文檔的

排列順序和前10個(gè)檢索文檔的準(zhǔn)確率。最后，與分類C相關(guān)的所有訓(xùn)練查詢的得分是資源庫(kù)D的一個(gè)平均值，這個(gè)平均值就是資源庫(kù)對(duì)于分類的可信因子。在訓(xùn)練的最后，對(duì)于13個(gè)分類，每個(gè)資源庫(kù)都有一個(gè)可信因子。

當(dāng)元搜索引擎接到一個(gè)查詢q，如果q中有詞語(yǔ)在分類C中，q首先映射到分類中。然后，資源庫(kù)將根據(jù)已映射進(jìn)分類的每個(gè)資源庫(kù)的可信因子的總和來(lái)排名。這個(gè)綜合就稱為q的資源庫(kù)的排名得分。在ProFusion系統(tǒng)中，為每個(gè)查詢選擇3個(gè)得分最高的資源庫(kù)。在ProFusion中，對(duì)已經(jīng)檢索到的文檔的排名是根據(jù)文檔的相似性和資源庫(kù)的得分的乘積得出來(lái)的。假定d是數(shù)據(jù)庫(kù)D中的第一篇用戶點(diǎn)擊進(jìn)入查看的文檔，如果d不是排名前列的文檔，那么D的排名得分將會(huì)增加，而那些含有排名高于d文檔的數(shù)據(jù)庫(kù)的得分相應(yīng)地減少，這些操作都適當(dāng)?shù)卣{(diào)整映射為分類的數(shù)據(jù)庫(kù)可信因子。假設(shè)有查詢q和資源庫(kù)D，已經(jīng)選定的兩個(gè)分類是C1和C2，可信因子分別是0.6和0.4，為了把D的得分增加x，C1和C2中D的可信因子也應(yīng)分別增加0.6x和0.4x，這樣的處理可以使文檔d在將來(lái)的查詢中位置能更靠前一些。

ProFusion綜合了靜態(tài)學(xué)習(xí)和動(dòng)態(tài)學(xué)習(xí)，克服了其各自的一些缺點(diǎn)，但是ProFusion仍然有一些問(wèn)題。首先，靜態(tài)學(xué)習(xí)部分仍然需要人工來(lái)完成，比如選擇訓(xùn)練查詢和標(biāo)識(shí)相關(guān)文檔還是要手動(dòng)進(jìn)行。其次，在調(diào)整可信因子之后，雖然有些排在前列的文檔是用戶不感興趣的，但作為第一次點(diǎn)擊進(jìn)入的，從相同資源庫(kù)中檢索到的文檔仍然會(huì)排列在前。第三，應(yīng)用動(dòng)態(tài)學(xué)習(xí)的方法過(guò)于簡(jiǎn)單，比如，幾乎沒(méi)有考慮到反饋信息，也沒(méi)有考慮到用戶通常不管文檔是否相關(guān)，都會(huì)選擇排列在前的文檔。8.3.3文檔選擇

除了進(jìn)行資源選擇以確定所需的資源庫(kù)外，還需要進(jìn)行文檔選擇。文檔選擇決定從資源庫(kù)中返回什么文檔，目的是從資源服務(wù)器中返回盡可能多的潛在的有用文檔，同時(shí)最小化返回?zé)o用的文檔數(shù)。

1．用戶設(shè)定

用戶設(shè)定就是讓用戶自己能自由地設(shè)定從元搜索引擎所要返回的文檔數(shù)。在MetaCrawler系統(tǒng)[19]和SavvySearch中，都是使用這種方法，不同的查詢可能會(huì)選擇返回不同的文檔數(shù)。如果用戶沒(méi)有選擇所要返回的文檔數(shù)，則系統(tǒng)將根據(jù)默認(rèn)值來(lái)返回文檔。如果資源庫(kù)的數(shù)目不是很大，而且用戶對(duì)這些資源庫(kù)都非常熟悉，那么應(yīng)用該方法會(huì)取得很好的效果。但是如果資源庫(kù)非常之多，則可能會(huì)引發(fā)比較嚴(yán)重的問(wèn)題。用戶可能不會(huì)根據(jù)資源庫(kù)來(lái)選擇合適的文檔數(shù)，而是隨意選擇一個(gè)數(shù)提交給系統(tǒng)。由于可用的文檔數(shù)對(duì)于不同的資源庫(kù)數(shù)目是不同的，故這個(gè)方法也無(wú)法適應(yīng)這種變化，有時(shí)可能選的文檔數(shù)過(guò)多，而有時(shí)選的文檔數(shù)又太少。如果要從N個(gè)數(shù)據(jù)庫(kù)中選擇m篇文檔，設(shè)定的數(shù)目一般是[m/N]，或稍大些。

2．權(quán)重分布

如前面提到的，在資源選擇中，對(duì)于資源庫(kù)都有一個(gè)排名，并為每個(gè)資源庫(kù)都計(jì)算出一個(gè)得分。權(quán)重分布的基本思路就是，可以從那些排列在前的資源庫(kù)中盡量多選擇一些文檔。

在D-WISE系統(tǒng)中，對(duì)于一個(gè)查詢q，設(shè)ri是構(gòu)成資源庫(kù)Di(i＝1，…，N)的計(jì)算得分，這里N是選擇的資源庫(kù)數(shù)目。假定從所有選擇的資源庫(kù)中要m篇文檔，那么從Di中返回的文檔數(shù)mi是(8-13)對(duì)于CORI系統(tǒng)，如果總共m篇文檔從N個(gè)數(shù)據(jù)庫(kù)中檢索到，則從第i個(gè)資源庫(kù)返回的文檔數(shù)mi是(8-14)注意到，有。這里，為了盡量少漏掉可用文檔，m值通常要設(shè)定得比用戶想要的文檔數(shù)大一些。

3．基于學(xué)習(xí)

前面介紹過(guò)MRDD方法，實(shí)際上，這個(gè)方法不僅可用于用戶資源庫(kù)的選擇，也可用于對(duì)資源庫(kù)的文檔選擇。引用例8-3，當(dāng)需要從3個(gè)已知資源庫(kù)中得到3篇相關(guān)的文檔時(shí)，該方法就會(huì)從D1中選擇最靠前的1篇文檔，而從D3中選擇最靠前的3篇文檔。第二個(gè)方法是查詢聚類(QueryClustering，QC)，也是基于過(guò)去的檢索經(jīng)驗(yàn)來(lái)進(jìn)行文檔選擇。同樣，這里也利用了一組訓(xùn)練查詢，在訓(xùn)練階段，對(duì)于每個(gè)資源庫(kù)，訓(xùn)練查詢都分組為一些聚類。如果兩個(gè)查詢檢索到的相同的文檔數(shù)很大，那么這兩個(gè)查詢就歸入同一個(gè)聚類中。下一步，根據(jù)聚類中的查詢的平均向量計(jì)算出每個(gè)查詢聚類的質(zhì)心(centroid)。對(duì)于每個(gè)資源庫(kù)，基于前T個(gè)相關(guān)文檔的平均數(shù)(由Voorhees[16]得出的實(shí)驗(yàn)數(shù)據(jù)，T＝8效果最好)，每個(gè)聚類都要計(jì)算一個(gè)權(quán)重。對(duì)于一個(gè)資源庫(kù)，聚類的權(quán)重表明資源庫(kù)對(duì)查詢是否響應(yīng)得很好。在計(jì)算出質(zhì)心之后，就選擇那些與查詢相似的查詢聚類。然后根據(jù)所選擇的查詢聚類的權(quán)重來(lái)決定每個(gè)數(shù)據(jù)庫(kù)的文檔選擇。假定wi是為構(gòu)成數(shù)據(jù)庫(kù)Di選擇的查詢聚類的權(quán)重，m是想要的文檔數(shù)，則從Di中選擇的文檔數(shù)mi是(8-15)這里，N是資源庫(kù)的數(shù)量?？梢钥吹皆摲椒▽?shí)質(zhì)上也是一個(gè)權(quán)重分布方法，資源庫(kù)的權(quán)重是一個(gè)學(xué)習(xí)到的查詢聚類的權(quán)重。8.3.4信息融合

由于分布式信息檢索的查詢結(jié)果是從多個(gè)獨(dú)立的信息資源檢索出的，因此極有可能在結(jié)果中出現(xiàn)相同或者相似文檔，這些來(lái)自于不同信息資源的相似和相同結(jié)果應(yīng)合并為一個(gè)最終結(jié)果。雖然從每個(gè)信息資源返回的結(jié)果是按照其與查詢的相關(guān)度排序的，但是由于每個(gè)信息資源對(duì)于計(jì)算相關(guān)度有自己的標(biāo)準(zhǔn)和算法，因此，資源與資源之間的排序沒(méi)有可比性。例如元搜索引擎在搜索結(jié)果的顯示過(guò)程中，需要將用戶查詢相關(guān)度高的結(jié)果放在前面，但是由于不同搜索引擎所采用的技術(shù)不盡相同，采用的排序方法不一樣，所以很難按照一個(gè)統(tǒng)一的標(biāo)準(zhǔn)去排列這些結(jié)果，信息融合很好地解決了這一問(wèn)題。

信息融合是指在一個(gè)統(tǒng)一的標(biāo)準(zhǔn)上重新考慮所有結(jié)果的排序問(wèn)題。信息融合實(shí)際上可以看成一種社會(huì)選擇(SocialChoice)問(wèn)題，也即幫助人們做出集合決定，例如選舉。信息融合的數(shù)學(xué)模型包括：

(1)一系列投票者(voters)：V={V1，V2，V3，…，Vn}；

(2)一系列候選者(alternatives)：S={S1，S2，S3，…，Sm}，S的維度|S|=m；

(3)一系列偏好關(guān)系P={R1，R2，R3，…，Rn}，稱為偏好設(shè)置(preferenceprofile)；

(4)投票者i的偏好關(guān)系為Ri，是S

的一個(gè)置換列表。

下面介紹幾種信息融合的方法。

1．平均融合

對(duì)于信息融合而言，簡(jiǎn)單的平均每個(gè)信息源的相關(guān)判斷是最簡(jiǎn)單的，也是較為有效的方法。如果每個(gè)信息源給出文檔di的相關(guān)度為Pi，則N個(gè)信息源的平均相關(guān)度為

1/。

進(jìn)一步推廣平均融合的思想，可以有最小、最大、均值和中位數(shù)等融合方法[20]。如表8-1所示。而Hull等證明用對(duì)數(shù)比log[P/(1－P)]規(guī)范化之后可得到更好的融合結(jié)果[21]。

2．線性融合

線性融合(LinearCombination，LC)模型[22-23]假設(shè)系統(tǒng)中存在大量重復(fù)的相關(guān)文檔和少量重復(fù)的不相關(guān)文檔，設(shè)已知給定s個(gè)獨(dú)立IR系統(tǒng)，權(quán)重是w=(ω1，ω2，…，ωs)，對(duì)查詢q每個(gè)檢索引擎對(duì)文檔x給出一個(gè)相關(guān)度pi=pi(x，q)。對(duì)所有s個(gè)搜索引擎對(duì)文檔x的相關(guān)度加權(quán)求和，即為文檔x的相關(guān)度：(8-16)這個(gè)值就可以用來(lái)對(duì)文檔排序。對(duì)于兩個(gè)IR系統(tǒng)，可以簡(jiǎn)化為(8-17)然而，實(shí)際問(wèn)題是由融合系統(tǒng)給出的排序問(wèn)題。因此，對(duì)于兩個(gè)系統(tǒng)的情況，只有兩個(gè)權(quán)重的比值和權(quán)重記號(hào)的關(guān)系是重要的，式(8-17)可以用單權(quán)重的公式代替：(8-18)這里sinω=ω1，cosω=ω2。

LC模型比其他的模型更靈活。大多數(shù)都是由單一參數(shù)組成的，例如，得分和或是最大得分，或是基于獨(dú)立系統(tǒng)性能的固定權(quán)重，LC模型也可以看做最簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)。

3．Bayes融合

Bayes融合[24]基于Bayes概率原理。已知n個(gè)檢索系統(tǒng)返回的文檔排序列表，設(shè)ri(d)是文檔d在檢索系統(tǒng)i中的排序(如果文檔d在檢索系統(tǒng)i中未被檢索，該值為無(wú)窮大)。對(duì)于一個(gè)已知文檔，設(shè)：(8-19)分別是排序r1，r2，…，rn的該文檔的相關(guān)概率和不相關(guān)概率。貝葉斯最佳策略規(guī)定了決定文檔相關(guān)度的規(guī)定，如果Prel>Pirr，則該文檔認(rèn)為是相關(guān)的；反之則認(rèn)為不相關(guān)。由于關(guān)注的是文檔的排序，需要計(jì)算相關(guān)度的比：(8-20)按照這一標(biāo)準(zhǔn)來(lái)對(duì)文檔排序。應(yīng)用貝葉斯法則，可以得到(8-21)然而P[r1，r2，…，rn]在實(shí)際中很難得到，在相關(guān)度比公式中可以約去：(8-22)使用原始貝葉斯獨(dú)立假設(shè)，可以用一種很簡(jiǎn)單的方式重寫這個(gè)公式：(8-23)由于只關(guān)心文檔的排序，所以可以去掉常數(shù)項(xiàng)P[rel]/P[irr]，然后取對(duì)數(shù)值，得到如下的相關(guān)度公式：(8-24)注意，P[ri|rel]是已知相關(guān)文檔ri的排序概率。同樣，P[ri|irr]是已知不相關(guān)文檔ri的排序概率。因此，為了獲得文檔的相關(guān)度排序，可以簡(jiǎn)單地計(jì)算所有系統(tǒng)的這兩個(gè)概率比的對(duì)數(shù)和。

4．Borda選舉

與實(shí)際的選舉問(wèn)題相反，在分布式搜索中，我們假設(shè)有許多的候選人，而有相對(duì)較少的選舉者。Borda選舉算法[25]即使在選舉者的數(shù)量非常少的情況下也適用。

Borda選舉算法的操作步驟如下：每一個(gè)選舉者對(duì)固定c個(gè)候選者進(jìn)行選舉。對(duì)于每一個(gè)選舉者，排名最高的候選人給c分，排名第二的候選人給c－1分，依次類推。若有候選人未被排序，則將所有余下的分值平均分配給每個(gè)未被排序的候選人。候選人按照得分排序，得分最高的候選人勝出。由多候選人選舉策略可以直接類推分布式檢索問(wèn)題：把檢索的文檔看做候選人，檢索系統(tǒng)是選舉者。使用這種方式，Borda選舉可以使用多檢索系統(tǒng)返回的排序列表。不要求相關(guān)度得分，不要求訓(xùn)練數(shù)據(jù)，這種融合算法既簡(jiǎn)單又有效。

【例8-4】

有3個(gè)選舉人A、B和C，有4個(gè)候選者(X、Y、Z、W)，選舉結(jié)果如表8-2所示，請(qǐng)給出最終排序。

解：根據(jù)Borda選舉算法，排在第一的分?jǐn)?shù)為1，排在第二的分?jǐn)?shù)為2，依次類推。因此有：

X：1+2+1=4，Y：2+1+4=7，Z：3+4+3=10，W：4+3+2=9

最后得到：X>Y>W>Z。在民主選舉中，當(dāng)然每一個(gè)選舉者都有相同的權(quán)重。然而，在分布式搜索系統(tǒng)中，最佳的性能通常是通過(guò)對(duì)不同信息源賦予不同的權(quán)重得到的。一個(gè)簡(jiǎn)單的賦予權(quán)重方法是乘以系統(tǒng)Si的系統(tǒng)權(quán)重ωi，這個(gè)策略又稱為權(quán)重Borda(WeightedBorda)融合。

融合排序方法的原理通常是很淺顯易懂的。例如，Borda方法就是基于“獲勝越多越好”的想法。很自然地可以擴(kuò)展這種想法，如“戰(zhàn)勝越多優(yōu)秀競(jìng)爭(zhēng)者就越好”，并且可以通過(guò)啟發(fā)式方法反復(fù)優(yōu)化排序。在Web搜索中，HITS算法和PageRank算法也是類似的原理。因此可以看到，大部分融合算法都是Borda算法的擴(kuò)展，由“少數(shù)服從多數(shù)”以及幾何均值來(lái)排序。

5．CORI融合

CORI融合算法是一個(gè)將數(shù)據(jù)庫(kù)的得分和文檔的得分線性融合的算法[26]。這個(gè)算法沒(méi)有對(duì)每個(gè)資源庫(kù)中的文檔重疊數(shù)量和相關(guān)文檔的數(shù)量提出假設(shè)，只是簡(jiǎn)單支持來(lái)自數(shù)據(jù)庫(kù)的高得分文檔，并且使來(lái)自低分資源庫(kù)的高分文檔有高的排序。這個(gè)方法已經(jīng)應(yīng)用到INQUERY系統(tǒng)。

計(jì)算適宜融合的“規(guī)范化”得分：(8-25)(8-26)(8-27)(8-28)式中：df是在資源Ri中包含查詢?cè)~rk的文檔數(shù)目；cf是包含查詢?cè)~rk的資源數(shù)目；cw是資源Ri中的索引詞語(yǔ)數(shù)目；avg_cw是每個(gè)資源中索引詞語(yǔ)的平均數(shù)目；n是查詢?cè)~個(gè)數(shù)；C是資源庫(kù)的數(shù)目。根據(jù)公式(8-28)可以計(jì)算每一個(gè)資源相對(duì)于每一個(gè)查詢請(qǐng)求的得分Ri。如果對(duì)查詢請(qǐng)求，公式(8-28)中的T都設(shè)為1.0，則可計(jì)算出得分Rmax。如果對(duì)查詢請(qǐng)求T設(shè)為0.0，則可計(jì)算出得分Rmin。這就是資源排序算法可以為資源潛在分配的最高和最低得分。所以說(shuō)，公式(8-25)是規(guī)范化的資源權(quán)重得分，它只可以用來(lái)計(jì)算資源選擇索引中的信息。在INQUERY中，對(duì)于每一個(gè)查詢請(qǐng)求，資源Ri的Dmaxi是通過(guò)把TF-IDF算法的tf設(shè)置為最大值(1.0)來(lái)計(jì)算的；資源Ri的Dmini是通過(guò)把TF-IDF算法的tf組成設(shè)置為最小值(0.0)來(lái)計(jì)算的。因此，Dmaxi和Dmini是資源Ri中的所有文檔的最大最小得分的估值。因此公式(8-26)是文檔得分的規(guī)范化，但它需要每個(gè)資源服務(wù)器合作來(lái)提供Dmax和Dmin。如果資源服務(wù)器沒(méi)有合作，則Dmax可設(shè)置為資源服務(wù)器返回的最大文檔得分，Dmin設(shè)置為最