《网络信息检索》课件第8章

第8章并行和分布式信息检索8.1并行信息检索8.2分布式信息检索8.3元搜索引擎8.4P2P网络信息检索8.5小结思考题

8.1并行信息检索

8.1.1并行计算的概念

并行计算就是研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，分配给多个计算机进行处理，并把这些计算结果综合起来得到最终结果的问题。并行计算技术起源于科学计算，但如今其应用领域已不再仅仅限于科学计算。它已经被广泛地应用在工程计算及许多新兴的应用领域，比如金融走势模拟分析、信息检索和数据挖掘等。并行计算机是由多个可同时工作的处理器构成的计算机系统。目前，并行计算系统主要是指并行计算机(Multicomputer)系统或多处理机(Multiprocessors)系统。在一个并行计算系统中，不同处理器同时运行同一程序的多个任务或进程，或者同时运行多个作业或大量计算问题的多个独立程序，以提高系统的运算速度、吞吐量、系统的可靠性或有效地利用系统的资源。就处理器的组合方式不同，可以对并行体系结构进行分类。常用的Flynn分类法根据指令和数据流数目，把并行计算体系结构分为四种类型：

(1)SISD(单指令、单数据流)：串行地执行指令；

(2)MISD(多指令、单数据流)：在多个处理机中用不同的指令去处理单个数据；

(3)SIMD(单指令、多数据流)：以多个处理机同时对不同的数据执行同一种指令操作；

(4)MIMD(多指令、多数据流)：以多个处理机自治地对不同的数据执行不同的操作。

高速并行计算有三种类型的应用：①计算密集型(Compute-Intensive)应用，如大型科学工程计算与数值模拟；②数据密集型(Data-Intensive)应用，如数字图书馆、数据仓库、数据挖掘和计算可视化等；③网络密集型(Network-Intensive)应用，如协同工作、遥控和远程医疗诊断等[1]。搜索引擎的设计和实现需要在短时间内存取和处理海量数据，因此是一种数据密集型应用。这类数据密集型应用是并行计算技术非常适合的领域，同时也是必须采用并行计算技术的应用领域。例如，如果有总共达1TB的文本数据，需要在这些特定的文本文件中找到“并行计算”这个词组，并要知道它出现了多少次，都出现在哪些文件的什么位置，并且要求系统给出答案的时间不超过1秒。如果用普通的计算机来处理，单单文件I/O，所需的时间就不止1秒；即使文件I/O的时间可以忽略不计，CPU以峰值速率运行，它要在1TB数据中找到一个特定的词组所需的时间开销也是巨大的。再进一步，如果有成百上千用户同时利用系统搜索不同的词组，都要求在1秒钟内得到答案，单机系统根本处理不过来。用户不能容忍过长的等待时间，如果磁盘的转速和寻道时间没有数量级的提高，那么将数据读入内存是唯一避免I/O瓶颈的方法。目前普通计算机无法提供1TB的内存，那么可以考虑将1TB数据读入100台10GB内存的计算机，100台计算机同时在总计1TB的数据中查找，每台计算机仅仅查找10GB数据，这样才有可能在短时间内完成用户的请求。

并行计算，换来的是I/O带宽的累加，内存容量的累加以及CPU处理能力的累加。在搜索引擎这种海量数据处理问题上，并行计算技术是高效处理海量数据的根本办法。8.1.2并行信息检索体系架构

在介绍并行检索之前，先看看信息检索的一般过程，如图8-1所示。图8-1检索的一般过程如图8-1所示，用户提交一个查询，查询代理对查询进行分析，比如进行编码格式转换，分词解析等，得到一个规格化的查询词，发送到检索程序，检索程序从索引中查找文档并进行处理，如计算得分和结果排序等，然后将初步结果发回到查询代理，查询代理进行规整、合并后，把结果返回给用户。

综上所述，信息检索可以很方便地进行并行化处理。直观地看来，多条查询之间可以进行并行检索，单条查询内部也可以进行并行检索。

1．一般体系架构

一种可行的体系架构就是，检索系统利用并行计算机中的每一个处理器运行一个分离的、独立的搜索，这些独立的搜索可能共享程序代码库、文件系统中的数据或共享内存中的数据等。用户向搜索引擎提交的查询是由一个代理程序来管理的，代理接受用户的搜索请求，并把请求分发到子检索系统中。图8-2所示为原理模型，图8-3为对应的并行信息检索服务器模块图。图8-2并行检索模型图8-3并行信息检索服务器如果有较多的处理器，就可以并行运行更多的独立搜索，因此可以并行处理更多的搜索请求，提高系统的吞吐量。但是需要注意，并不是简单地堆积CPU和磁盘，就可以提高信息检索的性能。问题是如何有效地利用硬件资源，设计合理的软件结构包括系统体系结构和数据结构，以提高信息检索的性能。否则有时候盲目添加更多的硬件反而会降低性能，因为随着处理器数目的增加，磁盘和I/O通道访问次数也随之增加，各个处理器的访问可能会互相冲突，造成磁盘的存取竞争。磁盘瓶颈将会降低性能，抵消增加处理器带来的吞吐量增益。因此需要仔细地平衡系统中的硬件资源。

2．数据分割和计算分割

为了支持并行检索，除了在计算机中增加更多的磁盘外，系统管理员还必须合理地在磁盘中分配索引数据。如果两个搜索进程需要存取存放在相同磁盘上的索引数据，仍然会有磁盘竞争的问题。增加磁盘的数量，可以减少这样的竞争，但是同时也增加了存储设备的费用和更新的复杂性。可以考虑作一些改进，例如，将那些被访问次数多的数据复制存储，而把较少被访问的数据随机分布，这就是索引数据的分割和复制存放策略。为了进一步改善查询的响应时间，必须对单个查询所需要的计算量进行分割，分出多个子任务，并分配到多个处理器上去执行。在这种方法中，代理和搜索进程也是并行运行在分离的处理器上，但是现在是协同运行去处理同一个查询。代理程序接受用户的一个查询，并把它分配到多个搜索进程上。然后，每个搜索进程执行部分查询任务，把中间结果返回给代理。最后，代理把这些中间结果组合起来，形成一个最终的结果，交付给用户。从上面的描述可以知道，并行检索主要涉及两大关键技术，一是并行计算，二是并行数据存取，前者需要通过并行编程实现检索计算的并行化，后者则是需要对数据结构如倒排文件进行分割，并存放在并行文件系统上，以提供高性能高带宽的并行数据存取功能。针对搜索引擎而言，这两大技术的实现有着很独特的要求和特点。下面主要介绍面向信息检索的并行编程和数据并行技术以及Google在这方面的两大核心技术：MapReduce并行编程模型[2]和GFS(GoogleFileSystem)并行文件系统[3]。8.1.3并行编程

1．并行编程概述

并行编程模型一直是并行计算研究领域的重点内容，它和并行计算机体系架构紧密相关。共享存储和消息传递是目前两种主流的并行编程模型。共享存储体系架构下的并行编程模型主要是共享变量编程模型，它具有单地址空间、编程容易、可移植性差等特点，其实现有OpenMP[4]和Pthreads(POSIXThread)[5]等。分布式存储体系架构下的并行编程模型主要有消息传递编程模型，消息传递编程模型的特点是多地址空间，编程困难，可移植性好，其实现有MPI(MessagePassingInterface)[6]和PVM(ParallelVirtualMachine)[7]等。目前用来构建搜索引擎的都是普通PC组成的集群(Cluster)系统，而不是具有共享存储的SMP(SymmetricalMultiprocessing)机器，因为后者比较昂贵。而集群系统是很典型的分布存储体系架构，因此需要采用分布存储编程模型，例如消息传递编程。消息传递(MessagePassing)是指在各个处理机节点之间通过用户调用并行系统的子程序库来实现它们之间的实时消息传递(MessageCommunication)。消息传递可以定义为：在一组进程当中，各个进程之间通过发送和接收数据来实现进程之间的相互通信。数据的传递需要各个处理器节点之间相互协调操作，即一个发送(send)的操作就必须有一个接收(receive)的操作与之相匹配。并行编程对开发者的要求较高。相比于串行编程，并行编程中需要额外考虑以下问题：

(1)负载平衡问题。并行程序中可能出现负载不平衡的问题，没有充分利用每个处理器的处理能力，导致一些处理器比较空闲，影响了程序的总体执行性能。

(2)进程数或线程数的选择问题。一些应用问题存在所需进程或线程数目与处理机数目不匹配的问题。若前者太小，则不能充分发挥机器的效率；若太大，又无法执行。

(3)通信带宽和延迟问题。并行程序进程间的通信带宽和延迟问题可能会严重影响程序的执行性能。特别是在分布式存储系统如集群系统中，通信延迟对总体性能的影响更大。

(4)细粒度并行问题。编写并行程序时，一般并行粒度越小，越可以更好地利用多处理器，但并行粒度太小也会增加系统的管理开销。

2．并行编程模型MapReduce

搜索引擎系统需要对原始数据(爬虫抓取下来的文档、用户查询日志等)进行处理，生成倒排索引文件，网页链接关系库等。这些处理算法原本是简单直观的，但在处理海量的原始数据集时，要在较短的时间内得到运算结果，就只有把运算分布到多台机器上并行进行。如何分割数据，如何并行运算，如何处理异常和错误，都需要进行详细的分析设计，这些都是很复杂的问题。针对这种情况，Google搜索引擎开发人员提出了一种模型，称为MapReduce编程模型，把分布运算带来的细节问题，如数据分割、容错机制、负载均衡等封装在一个底层包里面隐藏起来，开发人员只需考虑接口，实现直观的算法。也就是说，基于MapReduce模型实现的程序可以自动分发到多个机器并行运算，由底层软件包进行数据分割、任务调度、错误处理以及相关的主机通信，使得没有任何分布式系统开发经验的人也可以利用分布式系统的巨大运算能力。

MapReduce模型的核心是Map函数和Reduce函数，Map函数把输入的一个[关键字/值]生成多个[临时关键字/临时值]，作为中间结果；Reduce函数把Map函数产生的中间结果作为输入，把具有相同临时关键字的多个临时值合并起来，得到最终结果，如图8-4所示。图8-4MapReduce的任务处理流程在搜索引擎系统中，很多运算都可以用这个模型来表示。比如，统计一个页面的链入URL，可以用下面的Map函数和Reduce函数表示。Map函数为在source页面碰到的每一个链接到target的链接，输出〈target，source〉；Reduce函数把target相同的输出合并起来，得到〈target，list(source)〉，它就是所有链接到target的网页集合。倒排索引的建立也可以用这个模型，Map函数分析每一个文档，输出一系列的〈word，documentID〉；Reduce函数接受所有的中间结果，并根据documentID进行排序，得到〈word，list(documentID)〉。最后再把Reduce函数输出的结果集合起来，就是一个简单的倒排文件了。

【例8-1】

统计一个文档集合中各个词出现的次数。

解：可以用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函数把遇到的单词和出现次数(这里为1)作为中间结果输出；Reduce函数把同一个单词的中间结果加在一起。

MapReduce是一个并行编程模型，这个模型可以方便地处理实际问题，它隐藏了分布运算量进行并发运算后带来的数据分割、容错机制、负载均衡等问题，极大简化了并行编程的复杂度。开发人员只要把算法描述为Map和Reduce函数，就可以自动利用分布资源，高效进行并行运算。8.1.4数据并行

在进行查询之间的并行时，检索系统中的数据结构通常不需要改变。而对于单条查询内部的并行处理，则需要对原有串行信息检索的数据结构进行相应的改变。检索系统中最重要的数据结构就是倒排索引。因此要考虑进行倒排索引分割。

1．倒排索引分割

倒排索引分割可以分为两种，一种是基于文档的倒排索引分割(DocumentPartitioning)，另一种是基于查询项的倒排索引分割(TermPartitioning)。

基于文档的倒排索引分割有两种实现方法：物理文档分割(PhysicalDocumentPartitioning)和逻辑文档分割(LogicalDocumentPartitioning)。逻辑文档分割需要对倒排文件进行扩展，让每个并行进程能够直接访问一部分索引，这些索引对应于处理器所要处理的那部分文档子集。物理文档分割则不仅将数据集分割，而且将倒排索引表也同时进行分割，每个数据子集拥有自己独立的索引倒排结构。对于逻辑文档分割，倒排索引表并不物理上进行分割，而是增加一个处理机分配表，整张倒排索引表则被多个处理器共享使用，如图8-5所示。图8-5逻辑文档分割[8]逻辑文档分割后的检索过程：用户输入查询，代理将所需词典词条和所有postinglist放入共享内存，每个处理器负责访问各自的文档信息，进行相似度计算，最后将结果汇总。因为，多个处理器对索引的访问都是“读”操作，所以没有访问冲突问题。每个处理器返回结果都在自己的文档子集中，所以也没有“写”冲突。物理文档分割则是把文档分割为离散的、自包含的文档子集，每个子集对应一个并行处理器，每个子集有自己的倒排文件。物理倒排表分割后，每个子集合具有自己独立的倒排表结构，因此可以供不同的处理器单独调用，相对比较灵活。但是，由于独立的倒排表没有全局的统计信息(在进行检索时通常需要全局的统计信息来计算文档和查询的匹配相似度)，所以对每个子集进行检索时必须要有另外的处理来获得全局信息。方法通常有两种：一种是采用复制的方法，即将全局信息复制多份分配到每个独立的索引倒排表中；另一种是在每个子集合检索时分两步走，第一步获取全局信息表，第二步才进行检索。前一种方法比较耗费空间，对索引表的更新也比较复杂；后一种方法需要较大的通信开销。总的来说，逻辑文档分割方法的通信开销很小，因此总体性能会高于物理文档分割，但是必须要对普通倒排表增加额外的数据结构来进行转换。而物理分割方法的灵活性比较强，每个文档子集可以单独检索。通过物理分割的方法，很容易将非并行的信息检索系统转换为并行的检索系统。

使用查询项分割方法时，要将每个关键词项分配到不同处理器上。对于倒排表来说，就是将关键词项表(postinglist)进行分割(逻辑的或者物理的)，分别对应到不同的处理器上。在进行查询时，查询项将被分解成多个关键词查询，每个关键词对应不同的处理器分别进行处理。处理结果按照查询的语义进行合并。例如，如果是多个关键词布尔表达式查询，如查询“并行AND检索”，则合并的主要工作是进行布尔操作。如果是需要对多个子结果进行排序，则合并的主要工作是评分归一化并排序。相对而言，数据集分割方法能够提供更简单的倒排表构建和维护。Jeong和Omiecinski通过实验对文档分割方法和查询项分割方法进行了比较[9]：假设每个处理器有自己的I/O通道和磁盘，当关键词在文档和查询中呈偏态分布(skewed)时，采用数据集分割的方法性能较好；而当关键词在查询中呈均匀(uniform)分布时，查询项分割方法更优越。

数据分割后，需要存放到文件系统上供多处理器并发读写。普通的文件系统通常很难满足搜索引擎大规模数据读取的需求。下面介绍Google的并行文件系统GFS。

2．并行文件系统GFS

GFS是Google为搜索引擎系统量身定做的文件系统。在Google看来，用于搜索引擎的文件系统必须符合下面的应用需求：

●文件系统是建立在廉价通用主机平台上的，这些硬件可能经常出问题。为此，文件系统必须能够一直监视自己的状态并从灾难中恢复过来。

●文件系统存储着许多大文件。数目大概是几百万个，大小为100MB或者更大，几GB的文件在系统中也是常见的。小的文件也要支持，不过可以不用专门为其作优化处理。

●需要支持两种类型的读取方式：大规模流读取方式和小规模随机读取方式。在大规模流读取中，一个操作通常会从一个连续的文件区域中读取几百K或者更多的数据。随机读取则可能在任意位置读取几KB的数据。●写的方式和读的方式也类似。大量的数据通常以追加的方式添加到文件最后，因为这些数据一次写入后通常就不再更改了。随机写入也支持，但不作优化。

●系统必须能够高效地实现特定的原语，保证多个客户端能并发地对同一个文件进行追加记录。

●对于搜索引擎的文件系统而言，稳定的高带宽比低延时更重要。大多数应用程序，需要在高传输速率下，大块地操作数据。

为此，GFS提供了文件系统常用的接口，比如create、delete、open、close、read、write。同时，还特别地增加了两个原语：snapshot和recordappend。snapshot操作以最低开销拷贝一个文件和目录。recordappend操作让多个客户端并发地给同一个文件追加记录。

GFS可建立在通用主机组成的集群系统上，包括一个主节点(GFSmaster)，多个块服务器(chunkserver)节点和客户端(GFSclient)，如图8-6所示。节点运行Linux操作系统，在一台机器上可同时部署块服务器和客户端。图8-6GFS架构[3]在GFS中，文件被分成固定大小的块(chunk)，块的大小是固定的64MB。块创建的时候主节点会为其指定一个全局唯一的64位的句柄(chunkhandle)，并以Linux文件的形式保存在块服务器的本地磁盘上。利用句柄和字节范围对块进行读写访问。为了提高可靠性，块在其他块服务器上会有副本，通常有3个副本，用户也可以根据需要指定副本数目。

主节点管理文件系统的所有元数据信息，包括命名空间、访问控制、文件到块的映射表、块的位置等。它同时控制文件系统的全局性操作，管理整个系统的所有块副本，决定块的位置，创建新块和相应的副本，协调多变的系统活动以保持块被完全复制，均衡所有块服务器之间的负载，回收没有使用的存储空间。主节点会定时通过心跳信息与块服务器进行交互，发送指令同时收集块服务器的状态信息。

GFS客户端实现文件系统API，与主节点和块服务器进行交互，进行读写操作。应用程序利用GFSClient就可以访问文件系统。客户端从主节点获取元数据信息后，就直接与块服务器交互，从块服务器获取数据。

下面对照图8-6，说明GFS的各个模块之间是如何交互完成一个读操作的。

GFS中执行一个简单的读数据操作的工作流程如下：客户端可以把数据的偏移位置(offset)转换为块内索引号(chunkindex)，并和文件名(filename)一起发送到主节点，主节点把请求块的句柄和块的位置(chunklocation)发回到客户端；客户端接着从多个副本中选择一个，通常选择离自己最近的块服务器，把句柄、偏移位置和读取字节长度发送过去；之后，数据的传送在客户端与块服务器之间进行，不再需要主节点的参与，如图8-6黑色的数据线所示。一般数据访问存在空间局部性，以后如果该客户端需要访问同一块服务器中的数据，不再向主节点发送请求，而是直接向块服务器发送数据读取请求。

GFS采用一个松散的一致性模型，不仅能很好地支持分布式应用，而且实现起来也方便、高效。

8.2分布式信息检索

与并行检索系统不同，一个分布式信息检索系统(DistributedInformationRetrieval，DIR)由多个信息资源服务器(CollectionServers)和一个或多个代理服务器(Broker)两部分组成。用户向代理服务器提交查询，代理服务器将会用这个查询检索信息资源服务器的子集完成所需信息的查找。子集中的每个信息库服务器反馈给代理服务器一个按相关度由大到小排列的信息列表。最后，代理服务器对所有的结果

列表进行整合，形成新的信息列表反馈给用户。

分布式检索系统的体系结构由下面几个部分构成，如图8-7所示。相对于集中式信息检索系统，分布式信息检索系统的构建和工作流程模式有很大的不同：图8-7分布式检索系统的体系架构

(1)资源选择(CollectionResource)：获取一个资源的内容描述(CollectionDescription)，根据资源内容描述符和查询的比较，决定最可能包含所需信息的资源，对每一个查询可能都要执行这个操作；

(2)文档选择：对选择的目标资源进行检索，并选择相关文档；

(3)信息融合：把来自不同资源的相关文档合并为结果列表，并输出给用户。

归纳而言，分布式信息检索系统需要解决资源选择、文档选择和信息融合三大问题，下节以元搜索引擎为例进行说明。

8.3元搜索引擎

元搜索引擎是分布式信息检索的典型应用。元搜索引擎被称为搜索引擎之上的搜索引擎，它自己并不收集网站或网页信息，通常也没有自己的资源库和网络爬虫。元搜索引擎通过调用其他独立搜索引擎来完成搜索功能。用户在元搜索引擎的用户界面提交查询，然后元搜索引擎把这一查询请求发送给许多独立的搜索引擎。由于不同的搜索引擎可能会有不同的接受命令的格式，所以，用户查询请求应该先转换成其他搜索引擎能够接受的命令格式。然后元搜索引擎把从每个独立搜索引擎返回的结果合并成一个单一的排序列表，并返回给用户。元搜索引擎原理如图8-8所示。图8-8元搜索引擎原理图从元搜索引擎的结构中，元搜索引擎的技术重点在于查询前的处理(检索请求提交机制和检索接口代理)和结果的集成。元搜索引擎可以灵活地选择所要采用的独立搜索引擎。它一般都是选择那些比较典型的、性能优异的独立搜索引擎。这种强强联合的结果保证了搜索结果的权威性和可靠性。它还可以充分发挥各个独立搜索引擎在某个搜索领域的功能，弥补独立搜索引擎信息覆盖面的局限性。总的来说，元搜索引擎与独立搜索引擎相比，具有如下主要优点：

(1)信息的覆盖面。元搜索引擎一般都要默认调用它自己认为比较好的若干个普通搜索引擎，而且大多数元搜索引擎都提供给用户在一定范围内选择搜索引擎的功能。有些元搜索引擎还以频道的方式为用户提供专业搜索引擎的分类。这样，用户可以根据自己的喜好和要查询的内容选择相应的搜索引擎。

(2)搜索结果的权威性和可靠性。在独立搜索引擎中，索引数据库的更新需要一定的周期，而且搜集的信息也各有一定的侧重，元搜索引擎调用多个独立搜索引擎获取搜索结果，这种方式首先保证了信息的互补性，其次与独立搜索引擎相比，提高了信息的新鲜度。如果同样的搜索结果在多个独立搜索引擎中同时出现，那么说明这个搜索结果比较重要。这样就避免了一些独立搜索引擎人工干预搜索排名的缺点，使得搜索结果的排序更加公正。有些元搜索引擎还检查搜索结果链接的存在性，这样可以保证用户得到的元搜索结果的可靠性。

(3)易维护性。所谓易维护性，是针对元搜索引擎的管理者而言的。元搜索引擎省却了独立搜索引擎中收集和存储网页、建立和存储索引的工作。它将自己所调用的搜索引擎看成一个可以独立完成一定功能的实体，不需要去维护它们，只需知道它们的调用接口即可。元搜索引擎的查询精度在很大程度上依赖于它所调用的搜索引擎的查询精度，所以在设计元搜索引擎时可以把主要精力放在搜索引擎的选择、查询请求的优化和搜索结果的优化等方面。一般的元搜索引擎都提供了对应的优化机制。

元搜索引擎的核心问题是解决如何调用其他搜索引擎的索引数据库，如何获取查询词在其他搜索引擎中的查询结果以及如何评价、排序、呈现结果等，解决这些问题的主要技术有用户查询转换、检索机制设计与优化、检索结果输出、分布式数据库调用等技术。

1.用户查询转换

元搜索引擎定制查询界面供用户输入查询词，需要根据不同的搜索引擎转换成可以进行检索的查询表达式，不同的搜索引擎有不同的检索语法和操作符使用技巧，需要对提问进行处理。同时要对搜索引擎不能处理的检索方式进行排除，并选择一种合适的方式来匹配。

2.检索机制设计与优化

对于搜索引擎初始化方式、各个搜索引擎结果平衡处理等问题，都需要在检索机制的设计初期进行规划，这主要受到检索反馈速度、检索结果满意度等因素的影响，目前，搜索引擎初始化主要有用户参与、系统默认或自动随机处理等方式。检索结果的处理需要考虑如何衡量不同搜索引擎结果之间的相关程度。简单的处理方式是以搜索引擎为单位，在选定的独立搜索引擎下面显示比较靠前的结果；复杂的处理方式是以记录为单位，通过判定某一记录在多个独立搜索引擎中被评价的指数，如果多个独立搜索引擎都检出该结果，那么该记录将被排列在整个显示的前面，同时后面标注出是在哪些搜索引擎中检出的。

3.检索结果输出

结果输出处理一般有两种形式：直接引用原始结果页面技术与结果页面定制技术。直接引用原始结果页面是元搜索技术中较为简单易行的方式，在自制的页面中将表单提交的对象修改为独立搜索引擎调用的脚本文件。在这种情况中，一般无需进行结果去重，只需完成表单提交的转换即可。结果页面定制技术则要对结果进行更多的加工处理，主要包括：①去重和遴选处理，选择相关程度高的记录并加以显示，同时删除可能被多个独立搜索引擎同时检出的记录；②结果的再度排序，元搜索引擎并不是完全选取在独立搜索引擎中得到的结果的前几条记录，而是需要再度排序，根据检索机制对相关度判断的标准来比较各个搜索引擎得到的结果。

4.分布式数据库调用技术

直接调用独立搜索引擎结果页面的元搜索引擎不需与独立搜索引擎的索引数据库直接交换数据，只需直接引用独立搜索引擎的结果页面；而查询多个搜索引擎的元搜索引擎则需在满足独立搜索引擎的数据库访问权限的情况下，实现对其索引数据库的访问和二次开发。各独立搜索引擎的数据库分布在不同的地域，要实现对异地、异构数据库的访问，需要使用一系列诸如分布计算等相关的核心技术。同时，不同数据库调用结果响应时间长短不一，这也会直接影响到结果页面的呈现。8.3.1系统架构

元搜索引擎的参考软件组成结构如图8-9所示。下面讨论每个软件组成的功能和它们之间的相互作用。图8-9元搜索引擎系统架构图

1．资源选择

如果元搜索引擎中的成员搜索引擎(ComponentSearchEngines)的数目较少，就把用户的查询请求发送给每个成员搜索引擎。但是，当成员搜索引擎的数量很大时，把查询请求发送给每个成员搜索引擎是不可能的，这是因为在这种情况下，对于这个查询请求，本地数据的很大部分都是没有用的。例如，假设用户只对查询的10个最匹配的文档感兴趣，很明显，那10个想要的文档最多在10个成员搜索引擎的索引库中。因此，对于这个查询请求来讲，如果搜索引擎的数量远远超过10个，那么将会有很大部分的成员搜索引擎没有用。发送查询请求到没有用的成员搜索引擎会出现一些问题。首先，分派查询请求到没有用的成员搜索引擎消耗元搜索引擎站点的资源。第二，从元搜索引擎传输查询请求到没有用的成员搜索引擎，和从这些搜索引擎向元搜索引擎传送没有用的文档都将带来不必要的网络流量。第三，评估一个无用索引库的查询请求将会浪费本地系统的资源。第四，如果从无用的成员搜索引擎返回大量的文档，元搜索引擎就要花费大量的精力来识别哪些是有用的文档。因此，发送每个用户的查询请求到潜在有用的搜索引擎是很重要的。对于一个已知的查询请求，搜索潜在有用的搜索引擎的问题就是资源选择问题。资源选择器就是负责对于每个用户的查询请求，识别出潜在有用的成员搜索引擎。一个好的资源选择器应该能够识别出尽可能多的潜在有用成员搜索引擎，同时能够使无用成员搜索引擎当作潜在有用成员搜索引擎的可能性最小化。当一个元搜索引擎从用户接收到一个查询时，它就会调用资源选择器来选择元搜索引擎的成员搜索引擎，并将查询发向这些成员搜索引擎。一个好的资源选择算法应该能准确地找到潜在有用的成员搜索引擎，目前已经有很多方法来实现资源选择问题(相关算法详见8.3.2节)，这些方法的区别都体现在如下一些方面：资源的表示、根据有关查询选择资源有用信息的方法、资源选择有用性的评价等。

2．文档选择

对于每个资源选择器选择的搜索引擎，文档选择器决定从搜索引擎的索引库中返回什么文档。目的是从搜索引擎中返回尽可能多的潜在有用的文档，同时最小化返回无用的文档数。如果从一个搜索引擎中返回很多无用的文档，元搜索引擎就得花很大的精力来区分哪些是潜在的有用文档。一个最简单的方法是让每个资源服务器都将相似的文档返回给用户，但是这样会导致太多的文档返回，增加了通信的开销和存储空间，同时也增加了结果融合的难度。如前面所讨论的，资源服务器通常的做法都是将检索到的文档按相似度降序排列。因而，文档选择可以分解为下面两个问题：

(1)设置从资源库返回的检索文档数，如果从资源库中返回k个文档，那么将选择相似度最大的k个文档；

(2)为资源库设定一个门限，使得只有相似度大于这个门限的资源库中的文档才会被返回给用户。

3．查询分发

查询分发负责和被选定的搜索引擎服务器间建立连接，并负责发送查询请求。这个过程通常使用HTTP协议，每个搜索引擎对于HTTP请求方法(例如，GET方法和POST方法)和查询格式都有它自己的要求。查询分发必须正确满足每个成员搜索引擎的要求。一般情况下，发送给每个特定搜索引擎的查询请求很可能与元搜索引擎收到的查询请求不相同。也就是说，最初的查询请求在发送给成员搜索引擎之前，被翻译成一个新的查询请求。Chang等人提出了查询翻译的一些规则[30]。对于一个向量空间查询，查询翻译通常直接保留用户查询中的所有词语。也有两个例外，第一，在将查询发给成员搜索引擎之前，原始的用户查询的相对词频权重可能会有所调整。通过重复某个查询词到特定的次数，就能改变不同查询词的相对重要性。第二，从一个成员搜索引擎检索到的文档数量可能也和用户想要的有差距。例如，假定一个查询，用户想要m篇文档，文档选择器可能决定要从某个成员搜索引擎中检索到k篇文档。在这个例子中，k就是由翻译查询发给成员搜索引擎的，很明显，k不同于m。

4．结果融合

从被选定的成员搜索引擎的得到结果返回给元搜索引擎，结果融合把这些结果组合成一个单一的排序列表。根据用户的需要，返回列表的前m个文档给用户。一个好的结果融合应该把所有返回的文档按照降序排列。

通常，由于不同的数据库可能有不同类型的搜索引擎和不同的文本统计，所以，结果融合的工作是非常困难的。最准确的解决方案是规范化从不同成员搜索引擎检索得到的文档得分，或者使用需要合作的全局文档统计，或者是在搜索客户端重新计算文档得分。8.3.2资源选择

资源选择就是指选择最合适的信息资源的子集，以使这些子集包含与查询相关的信息量最多。资源选择最简单的方法是用户自己选择信息资源库去进行检索，这是目前分布式搜索引擎(如元搜索引擎)常用的方法。但有时用户对信息资源的利用知识有限，所以有的分布式信息检索中要求检索系统对用户的查询能够自动地选择信息资源，并且保证这些信息资源中包含与用户查询相关的检索内容最多。同时，如果将查询在每个信息资源库中进行检索，检索的完整性效果自然是最好的，但是这样做的成本很高，而且还会造成检索响应时间过长，增加用户的负担，因而对信息资源库进行选择的目标是尽可能降低信息库子集的数量，尽量保证检索的效率。给定一个需求信息和一组资源描述集，系统是怎样选择检索的资源呢？资源选择的等价问题是根据满足信息需求的条件来对资源进行有效的排序，以便用户能根据排序的结果进行有针对性的选择，这涉及到资源排序的算法问题。

Meng和Yu等人将这些方法归类为以下三种[10]：概略表示方法(RoughRepresentationApproaches)，统计表示方法(StatisticalRepresentationApproaches)和基于学习的表示方法(Learning-basedApproaches)。这些方法的性能评估可参见文献[27]。

1．概略表示方法

概略表示方法用一些关键词和短语来表示本地资源，但该方法对于资源的组成只提供了一般的解决措施，因而概略表示方法对于资源的选择是不精确的，该方法一般通过手动产生。

每个资源都要人为手动地设置一两个单词作为主题词或分类关键词。用户查询只有和关键词匹配，才能决定哪个资源是最适合用户需要的。匹配可能是针对一个或多个领域，如主题、描述等，这些可由用户选择。资源的排列也是依照查询的匹配程度来进行的，这样用户就可以从结果列表中及时选出所要的信息资源库。资源的文本描述转化为一种结构性的表示。这种转换可以手动执行，WordNet[11]就可以应用在消除主题词(topicalwords)歧义的转化过程中。

【例8-2】

在文档WorldFactbook中，语句“Worldfactslistedbycountry”可以转化为如下的结构表示：

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中，每个词有1个或多个同义词集，主题词“country”有4个同义词集，其中3个是相关的，所以这3个被采用。另外一个集(如[rural_area，country])与语句(Worldfactslistedbycountry)中“country”的含义不一样，不能匹配，因而被忽略。

除了人工产生的概略表示方法，也有一些自动产生的概略表示方法。在Q-Pilot系统中[12]，每个资源都用一组带有权重的词语的向量来表示，这些词语可以通过搜索引擎的接口页面或搜索引擎的链接页面来获得，权重就是词频。当连接到搜索引擎时，只有那些出现在同一行的词语才会被采用，并且每个词语的权重就是指文档中该词的权重。概略表示方法的优点在于表示简单，而且要求存储空间少。如果所有独立检索系统都专注于各种主题而且其内容都能被很容易地归纳，则概略表示方法可以应用得很好。但是，一个资源的简短描述往往不能完整充分地表示资源的内容，尤其当资源包含的内容非常广泛时。总的来说，应用这些方法都不大可能检索到那些潜在有用的数据库。因而，对于大型的检索系统来说，应用概略表示方法可能是不够的。

2．统计表示方法

统计表示方法的原理是：考虑资源中每个文档中的每个词语，并为每个词语保留一份或多份统计信息。如果设计得好，则应用这种方法可为每个查询发现单个潜在有用的文档。这里重点介绍D-WISE方法[13]和CORI方法[14，15]。

1)D-WISE方法

D-WISE(DistributedWebIndexandSearchEngine)是一个分布式的搜索引擎。在D-WISE中，每个资源服务器也称成员搜索引擎(MetaSearchEngineComponent)，可用其包含的资源库中每个词语的词频和资源中文档的数量来表示。用ni表示第i个构件资源库中的文档数量，用dfij来表示第i个资源库中词语tj的文档频率。

假定有用户查询q，所有资源库都根据q来计算排列得分，这个分数可以衡量资源库的相对有用性。如果资源库A的得分比B高，则认为A比B更相关。计算得分步骤如下：首先计算每个查询词语的有效性CV(CueValidity)。假定有词语tj，对于第i个资源库，用下列公式计算CVij：

这里，N是构件资源库的总的数量，可以看出，CVij计算出的是第i个含有tj资源库文档相对于其他资源库中含有tj的文档的百分比。如果第i个资源库的比例高于其他的资源库，那么CVij的值也就较大。下一步，对于所有资源库，每个查询词语tj的CVij的方差(CueValidityVariance，CVV)用CVVj表示，可用下列式子计算：(8-1)(8-2)这里，ACVj是所有CVij的平均值。CVVj衡量了所有资源库中tj的分布。对于两个词语tu和tv，如果CVVu>CVVv，则tu对于区分不同的构件资源库比tv更有用。最后，对于查询q，构件资源库的得分可用下面的式子来计算得出：(8-3)

这里，M是查询词语的数量。可以看到，资源库i的得分是所有查询词语的文档频率的总和，资源库是每个查询词语CVV的加权。这个排名得分说明可用的查询词语集中在哪些地方。如果某个资源库有很多可用的查询词语，比其他资源库的可用词语都多，则资源库的得分自然也高。可以看出，这种方法是很简单的，但是有两个问题：首先，排名得分是相对得分，根据给定查询得出资源库的真实得分往往是非常困难的。如果对于一个查询没有适用的资源库，排在首位的资源库的得分往往也是很小的一个值。而对另外一个查询可能有好多个适用的资源库，那么前10个资源库通常都是很有用的。也就是说，相对资源库得分在区分这些情况时往往作用不大。其次，该方法的准确性仍然值得怀疑，例如不能准确区分一个文档中某个词语出现1次和另一个文档相同词语出现100次的区别。

2)CORI方法

资源库检索推理(CollectionRetrievalInference，CORI)方法把每个信息库都看成是一篇巨大的文献，资源库的排序方法与传统信息检索系统中的文档排序方法相似。在CORI中，用文档频率DF(DocumentFrequency)和资源库频率CF(CollectionFrequency)来表示资源库，后者是含有检索词的数据库数量。

CORI方法是基于推理网络[28]的概率方法。就如第2章介绍的检索模型中应用推理网络排序文档的原理一样，同样可以用推理网络来排序资源库。从概念上，资源库可以被认为是包含所有检索词的超文档。如果一个检索词出现在资源库的k个文档中，可以将这个词在超文档中重复k次，这样资源库中检索词的文档频率变成了超文档的词频。在分布式检索系统中，构成资源库的所有超文档组成了一个超文档资源库。用D来表示这个超文档资源库。同样地，在D中，检索词的资源库频率变成了文档频率。因此，从构件资源库中，可以获得超文档资源库中每个检索词的词频和文档频率。同理，TFw-IDFw(词频权重和反向词频权重)公式也可以用来计算每个超文档中每个词语的权重，从而可以用权重向量来表示每个超文档。此外，也可以用余弦函数来计算两个超文档的相似性，然后根据相似性排序所有资源库。对于查询q，资源库的排名得分是一个包含了可用文档资源库的估计概率值(estimatedbelief)，这个值实质上是一个联合概率。该值可通过下述方法计算得到：假定用户查询有k个词语，t1，…，tk，N是资源库的数量，设定dfij为第i个资源库Dj中j个词语的文档频率，dbfj为第j个词语的资源库频率。

首先，Di含有检索词j的可用文档的概率值可以用公式计算：(8-4)其中，(8-5)是一个根据Di和Ij来计算超文档中第j个词语的词频权重；Ij是基于所有超文档计算出的第j个词语的反向文档频率，(8-6)式(8-4)和式(8-5)中，c1和c2都是取值于0~1之间的常数，并且有这样的关系：(8-7)这是一个资源库Di的函数。c3和c4都是常数，dwi是Di中词语的数量，adw是资源库中词语数量的平均值。这4个常数可以通过在测试集实验而获得一些经验值[14]。这样，查询q中tj的重要性也可以通过概率p(q|tj)计算出来。最后就可以用下面的式子来计算排名了：(8-8)

3．基于学习的表示方法

基于学习的方法是根据以前的检索经验来预测新查询的可用资源库。获得检索经验有很多种途径。首先，训练查询(TrainingQuery)就是一种，这要求预先根据训练查询来获得每个构件资源库的检索知识，这种方法叫静态训练。这种方法的特点是，一旦学习到了检索知识，就不再改变，因此缺点在于不能适应查询的变化。其次，通过学习用户的查询并逐渐积累，不时更新，这种方法就叫做动态学习，该方法的缺点是需要比较长的时间才能学习到足够的知识，以满足资源选择需要。综合前两点，就有了第三种综合学习方法，先从训练查询中获得初始的知识，再在用户的查询基础之上保持知识的不断更新。综合学习方法克服了前两种方法的缺点。本小节将介绍几种基于学习的资源库选择方法。

1)MRDD方法

MRDD(ModelingRelevantDocumentDistribution)方法[16]是一个静态学习方法。在学习过程中，利用到了一组训练查询集。该方法中，训练查询都会提交给每个资源库使用，从资源库返回的文档中，会标注出相关文档，再用一个向量来反映相关文档的分布，系统在获得该向量后会存储起来。向量有一个特定的格式，〈r1，r2，…，rs〉，这里ri是一个正整数，表示对于某个查询检索到的i个文档。例如，假定有训练查询q和一个资源库D，检索到了100个文档，组成序列(d1，d2，…，d100)。在这些文档中，文档d1，d4，d10，d17，d30是相关的，那么相应的分布向量则为〈r1，r2，r3，r4，r5〉＝〈1，4，10，17，30〉。在所有的资源库都根据训练查询获得分布向量之后，接下来的工作就是资源库选择了。接收到一个用户查询之后，系统会将查询和所有的训练查询进行比较，标注出k个最相似的文档。然后，对于每个数据库D，计算对于k个向量的平均相关文档分布向量，该平均向量将用于选择资源库。

【例8-3】对于查询q，有如下3个资源的平均分布向量：

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

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

D3：〈2，3，6，9，11，16〉若要检索3篇相关文档，为了最大化检索的准确率，即尽量少检索到不相关文档，则需要从D1中检索1篇文档，从D3中检索3篇文档(假定3篇中有两篇是相关的)。也就是说，D1和D3应该被选择出来，这个选择的准确率是75%，即4篇文档中有3篇是相关的。

在MRDD方法中，表示资源库的是训练查询的一组分布向量集。该方法的主要弱点在于人工手动学习，难于识别合适的训练查询，当资源库内容改变时，学习到的知识会使查询准确率降低。

2)SavvySearch方法

SavvySearch()是一个应用了动态学习方法的元搜索引擎[17]，该方法是在过去查询的经验上计算出资源库的排名得分。对于每个搜索，资源选择器都要维护一个权重向量(w1，w2，…，wm)，这里wi对应于资源库中第i个词语。初始状态时，所有的权重都置为0，当用一个含有词语ti的查询从资源库D中查找文档时，权重wi会根据检索结果做出相应的调整。如果搜索引擎没有返回该查询的任何文档，那么权重将减少1/k，这里k是查询中查询词的数量。如果返回结果中至少有一篇文章被用户点击进入阅读，那么权重也将增加1/k。可以得出这样的结论，正数wi越大，表明数据库D对过去词语ti响应得越好；负数的wi则表明响应得很差。同样，SavvySearch也追踪每个资源服务器的最近性能，h表示最近5个查询的平均返回文档数，r则是最近5个查询发给资源服务器的响应时间。如果h小于门限值Th(默认是1)，对于每个成员搜索引擎则计算出一个补偿值ph，同样，如果r小于门限值Tr(默认是15秒)，则也计算一个补偿值pr，这里r0＝45是超时前允许的最大响应时间。(8-9)(8-10)对于一个含有词语t1，…，tk的查询q，资源库D的得分可用下列公式计算：(8-11)式中：log(N/fi)是词语ti的反向资源库频率权重;N是资源库数;fi是对词语ti有正数权重值的资源库的数量。在SavvySearch中，为每个资源服务器存储信息而占用的开销是适中的，而维护这些信息也无需花费很多精力。但SavvySearch的一个缺点是：对于检索次数很少的词语，则检索的结果不理想。另外一个就是SavvySearch对于用户反馈也解决得不好，有时候可能错过很多可用信息。用户会倾向于直接查看排在前面的文档，而不管这些文档是否真的有用。这也意味着词语权重很容易被调整，而这些调整都不是产生权重机制的本意。

3)ProFusion方法

ProFusion是一个应用综合学习方法的元搜索引擎的例子[18]。在ProFusion中，采用13组预定义的分类，“scienceandengineering”，“computerscuence”，“travel”，“medicalandbiotechnology”，“businessandfinance”等，每个分类都关联一组词语，用来反映该分类的主题。使用分类和特定训练集的目的是可以了解到每个资源库对于不同的分类有不同的结果。对于一个给定的分类C和构件资源库D，每个关联的训练查询都会提交给D，然后再选择前10个标注是相关的文档。这样，根据分类C和查询，可以计算出数据库D的性能得分：(8-12)这里，c是一个常数。如果排的第i个位置的文档是相关的，则设定Ni为1/i；如果文档不相关，则设定Ni为0。R是10个返回文档的相关文档数。

可以看到，该方法计算出的得分涵盖了每个相关文档的

排列顺序和前10个检索文档的准确率。最后，与分类C相关的所有训练查询的得分是资源库D的一个平均值，这个平均值就是资源库对于分类的可信因子。在训练的最后，对于13个分类，每个资源库都有一个可信因子。

当元搜索引擎接到一个查询q，如果q中有词语在分类C中，q首先映射到分类中。然后，资源库将根据已映射进分类的每个资源库的可信因子的总和来排名。这个综合就称为q的资源库的排名得分。在ProFusion系统中，为每个查询选择3个得分最高的资源库。在ProFusion中，对已经检索到的文档的排名是根据文档的相似性和资源库的得分的乘积得出来的。假定d是数据库D中的第一篇用户点击进入查看的文档，如果d不是排名前列的文档，那么D的排名得分将会增加，而那些含有排名高于d文档的数据库的得分相应地减少，这些操作都适当地调整映射为分类的数据库可信因子。假设有查询q和资源库D，已经选定的两个分类是C1和C2，可信因子分别是0.6和0.4，为了把D的得分增加x，C1和C2中D的可信因子也应分别增加0.6x和0.4x，这样的处理可以使文档d在将来的查询中位置能更靠前一些。

ProFusion综合了静态学习和动态学习，克服了其各自的一些缺点，但是ProFusion仍然有一些问题。首先，静态学习部分仍然需要人工来完成，比如选择训练查询和标识相关文档还是要手动进行。其次，在调整可信因子之后，虽然有些排在前列的文档是用户不感兴趣的，但作为第一次点击进入的，从相同资源库中检索到的文档仍然会排列在前。第三，应用动态学习的方法过于简单，比如，几乎没有考虑到反馈信息，也没有考虑到用户通常不管文档是否相关，都会选择排列在前的文档。8.3.3文档选择

除了进行资源选择以确定所需的资源库外，还需要进行文档选择。文档选择决定从资源库中返回什么文档，目的是从资源服务器中返回尽可能多的潜在的有用文档，同时最小化返回无用的文档数。

1．用户设定

用户设定就是让用户自己能自由地设定从元搜索引擎所要返回的文档数。在MetaCrawler系统[19]和SavvySearch中，都是使用这种方法，不同的查询可能会选择返回不同的文档数。如果用户没有选择所要返回的文档数，则系统将根据默认值来返回文档。如果资源库的数目不是很大，而且用户对这些资源库都非常熟悉，那么应用该方法会取得很好的效果。但是如果资源库非常之多，则可能会引发比较严重的问题。用户可能不会根据资源库来选择合适的文档数，而是随意选择一个数提交给系统。由于可用的文档数对于不同的资源库数目是不同的，故这个方法也无法适应这种变化，有时可能选的文档数过多，而有时选的文档数又太少。如果要从N个数据库中选择m篇文档，设定的数目一般是[m/N]，或稍大些。

2．权重分布

如前面提到的，在资源选择中，对于资源库都有一个排名，并为每个资源库都计算出一个得分。权重分布的基本思路就是，可以从那些排列在前的资源库中尽量多选择一些文档。

在D-WISE系统中，对于一个查询q，设ri是构成资源库Di(i＝1，…，N)的计算得分，这里N是选择的资源库数目。假定从所有选择的资源库中要m篇文档，那么从Di中返回的文档数mi是(8-13)对于CORI系统，如果总共m篇文档从N个数据库中检索到，则从第i个资源库返回的文档数mi是(8-14)注意到，有。这里，为了尽量少漏掉可用文档，m值通常要设定得比用户想要的文档数大一些。

3．基于学习

前面介绍过MRDD方法，实际上，这个方法不仅可用于用户资源库的选择，也可用于对资源库的文档选择。引用例8-3，当需要从3个已知资源库中得到3篇相关的文档时，该方法就会从D1中选择最靠前的1篇文档，而从D3中选择最靠前的3篇文档。第二个方法是查询聚类(QueryClustering，QC)，也是基于过去的检索经验来进行文档选择。同样，这里也利用了一组训练查询，在训练阶段，对于每个资源库，训练查询都分组为一些聚类。如果两个查询检索到的相同的文档数很大，那么这两个查询就归入同一个聚类中。下一步，根据聚类中的查询的平均向量计算出每个查询聚类的质心(centroid)。对于每个资源库，基于前T个相关文档的平均数(由Voorhees[16]得出的实验数据，T＝8效果最好)，每个聚类都要计算一个权重。对于一个资源库，聚类的权重表明资源库对查询是否响应得很好。在计算出质心之后，就选择那些与查询相似的查询聚类。然后根据所选择的查询聚类的权重来决定每个数据库的文档选择。假定wi是为构成数据库Di选择的查询聚类的权重，m是想要的文档数，则从Di中选择的文档数mi是(8-15)这里，N是资源库的数量。可以看到该方法实质上也是一个权重分布方法，资源库的权重是一个学习到的查询聚类的权重。8.3.4信息融合

由于分布式信息检索的查询结果是从多个独立的信息资源检索出的，因此极有可能在结果中出现相同或者相似文档，这些来自于不同信息资源的相似和相同结果应合并为一个最终结果。虽然从每个信息资源返回的结果是按照其与查询的相关度排序的，但是由于每个信息资源对于计算相关度有自己的标准和算法，因此，资源与资源之间的排序没有可比性。例如元搜索引擎在搜索结果的显示过程中，需要将用户查询相关度高的结果放在前面，但是由于不同搜索引擎所采用的技术不尽相同，采用的排序方法不一样，所以很难按照一个统一的标准去排列这些结果，信息融合很好地解决了这一问题。

信息融合是指在一个统一的标准上重新考虑所有结果的排序问题。信息融合实际上可以看成一种社会选择(SocialChoice)问题，也即帮助人们做出集合决定，例如选举。信息融合的数学模型包括：

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

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

(3)一系列偏好关系P={R1，R2，R3，…，Rn}，称为偏好设置(preferenceprofile)；

(4)投票者i的偏好关系为Ri，是S

的一个置换列表。

下面介绍几种信息融合的方法。

1．平均融合

对于信息融合而言，简单的平均每个信息源的相关判断是最简单的，也是较为有效的方法。如果每个信息源给出文档di的相关度为Pi，则N个信息源的平均相关度为

1/。

进一步推广平均融合的思想，可以有最小、最大、均值和中位数等融合方法[20]。如表8-1所示。而Hull等证明用对数比log[P/(1－P)]规范化之后可得到更好的融合结果[21]。

2．线性融合

线性融合(LinearCombination，LC)模型[22-23]假设系统中存在大量重复的相关文档和少量重复的不相关文档，设已知给定s个独立IR系统，权重是w=(ω1，ω2，…，ωs)，对查询q每个检索引擎对文档x给出一个相关度pi=pi(x，q)。对所有s个搜索引擎对文档x的相关度加权求和，即为文档x的相关度：(8-16)这个值就可以用来对文档排序。对于两个IR系统，可以简化为(8-17)然而，实际问题是由融合系统给出的排序问题。因此，对于两个系统的情况，只有两个权重的比值和权重记号的关系是重要的，式(8-17)可以用单权重的公式代替：(8-18)这里sinω=ω1，cosω=ω2。

LC模型比其他的模型更灵活。大多数都是由单一参数组成的，例如，得分和或是最大得分，或是基于独立系统性能的固定权重，LC模型也可以看做最简单的神经网络。

3．Bayes融合

Bayes融合[24]基于Bayes概率原理。已知n个检索系统返回的文档排序列表，设ri(d)是文档d在检索系统i中的排序(如果文档d在检索系统i中未被检索，该值为无穷大)。对于一个已知文档，设：(8-19)分别是排序r1，r2，…，rn的该文档的相关概率和不相关概率。贝叶斯最佳策略规定了决定文档相关度的规定，如果Prel>Pirr，则该文档认为是相关的；反之则认为不相关。由于关注的是文档的排序，需要计算相关度的比：(8-20)按照这一标准来对文档排序。应用贝叶斯法则，可以得到(8-21)然而P[r1，r2，…，rn]在实际中很难得到，在相关度比公式中可以约去：(8-22)使用原始贝叶斯独立假设，可以用一种很简单的方式重写这个公式：(8-23)由于只关心文档的排序，所以可以去掉常数项P[rel]/P[irr]，然后取对数值，得到如下的相关度公式：(8-24)注意，P[ri|rel]是已知相关文档ri的排序概率。同样，P[ri|irr]是已知不相关文档ri的排序概率。因此，为了获得文档的相关度排序，可以简单地计算所有系统的这两个概率比的对数和。

4．Borda选举

与实际的选举问题相反，在分布式搜索中，我们假设有许多的候选人，而有相对较少的选举者。Borda选举算法[25]即使在选举者的数量非常少的情况下也适用。

Borda选举算法的操作步骤如下：每一个选举者对固定c个候选者进行选举。对于每一个选举者，排名最高的候选人给c分，排名第二的候选人给c－1分，依次类推。若有候选人未被排序，则将所有余下的分值平均分配给每个未被排序的候选人。候选人按照得分排序，得分最高的候选人胜出。由多候选人选举策略可以直接类推分布式检索问题：把检索的文档看做候选人，检索系统是选举者。使用这种方式，Borda选举可以使用多检索系统返回的排序列表。不要求相关度得分，不要求训练数据，这种融合算法既简单又有效。

【例8-4】

有3个选举人A、B和C，有4个候选者(X、Y、Z、W)，选举结果如表8-2所示，请给出最终排序。

解：根据Borda选举算法，排在第一的分数为1，排在第二的分数为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。在民主选举中，当然每一个选举者都有相同的权重。然而，在分布式搜索系统中，最佳的性能通常是通过对不同信息源赋予不同的权重得到的。一个简单的赋予权重方法是乘以系统Si的系统权重ωi，这个策略又称为权重Borda(WeightedBorda)融合。

融合排序方法的原理通常是很浅显易懂的。例如，Borda方法就是基于“获胜越多越好”的想法。很自然地可以扩展这种想法，如“战胜越多优秀竞争者就越好”，并且可以通过启发式方法反复优化排序。在Web搜索中，HITS算法和PageRank算法也是类似的原理。因此可以看到，大部分融合算法都是Borda算法的扩展，由“少数服从多数”以及几何均值来排序。

5．CORI融合

CORI融合算法是一个将数据库的得分和文档的得分线性融合的算法[26]。这个算法没有对每个资源库中的文档重叠数量和相关文档的数量提出假设，只是简单支持来自数据库的高得分文档，并且使来自低分资源库的高分文档有高的排序。这个方法已经应用到INQUERY系统。

计算适宜融合的“规范化”得分：(8-25)(8-26)(8-27)(8-28)式中：df是在资源Ri中包含查询词rk的文档数目；cf是包含查询词rk的资源数目；cw是资源Ri中的索引词语数目；avg_cw是每个资源中索引词语的平均数目；n是查询词个数；C是资源库的数目。根据公式(8-28)可以计算每一个资源相对于每一个查询请求的得分Ri。如果对查询请求，公式(8-28)中的T都设为1.0，则可计算出得分Rmax。如果对查询请求T设为0.0，则可计算出得分Rmin。这就是资源排序算法可以为资源潜在分配的最高和最低得分。所以说，公式(8-25)是规范化的资源权重得分，它只可以用来计算资源选择索引中的信息。在INQUERY中，对于每一个查询请求，资源Ri的Dmaxi是通过把TF-IDF算法的tf设置为最大值(1.0)来计算的；资源Ri的Dmini是通过把TF-IDF算法的tf组成设置为最小值(0.0)来计算的。因此，Dmaxi和Dmini是资源Ri中的所有文档的最大最小得分的估值。因此公式(8-26)是文档得分的规范化，但它需要每个资源服务器合作来提供Dmax和Dmin。如果资源服务器没有合作，则Dmax可设置为资源服务器返回的最大文档得分，Dmin设置为最