开源搜索引擎的比较

开源搜索引擎的比较AComparisonofOpenSourceSearchEnginesChristianMiddleton,RicardoBaeza-Yates作者：ChristianMiddleton的高级工程师。RicardoBaeza-Yates的高级研究人员。翻译：史春奇，搜索工程师，中科院计算所毕业，[e-mail]原文：目录第1章简介第2章背景2.1文档收集2.1.1网页抓取2.1.2文本检索大会TREC2.2索引2.3查询和排序2.4检索评估第3章搜索引擎3.1特征3.2评估第4章比较方法4.1文档收集4.2测试比较4.3引擎安装第5章测试5.1索引5.1.1TREC-4数据集的索引测试5.1.2索引WT10G的分组。5.2查询5.2.1TREC-4数据集的查询实验5.2.2准确率和召回率的比较5.3整体评估第6章结论参考书目第1章简介随着互联网信息量的激增，为用户提供网上相关信息的检索成为迫切需求。而当你准备在网站上提供这种检索服务的时候，你可以选择，要么利用商业搜索引擎，要么选择开源搜索引擎。对于很多站点，采用商业搜索引擎，可能没预期的那么便捷，你得花钱，而且呀，你可能没大站点那样受人家重视。另一方面，开源搜索引擎也能提供商业搜索引擎的同类功能（部分能够处理大数据量），同时拥有开源理念带来的好处：不花钱，可以更主动地来维护软件，也通过二次开发来满足个人的需求。现今，可以选择的开源产品很多，而要决定是采用哪个开源产品，就必须认真考虑每个开源产品的不同的特性。对这些搜索引擎划分的依据可以是开发的编程语言，索引文件的存储（倒排文件，数据库，还是其他文件格式），查询的能力（布尔运算，模糊查询，词根替换等等），排序策略，支持索引的文件类型，在线索引能力和增量索引的能力。其他值得考虑的重要因素是项目的最后更新日期，当前版本和项目的活跃度。这些因素之所以重要是因为，如果一个开源搜索引擎在近期没有更新的话，那么要满足现在的网站的话，可能存在很多的缺陷和问题。利用这些特性就可以给出一个大体上的划分，同时能够减少待选的开源产品的数目。最后，考虑不同负载的时候搜索引擎的性能，当信息量增加时，性能的如何降低的，这些也非常重要。此时，就要分析数据量和索引时间的对比情况，索引阶段所用的资源，和检索阶段的性能。就目前我们了解的情况，本文的工作是首创，比较了17个主流搜索引擎，并且在不同的文档集合和多种查询类型的情况下，比较了索引和查询的性能。本文的目的是告诉人们遇到某种搜索需求的时候，该如何选择是最合适的开源搜索引擎。第二章，介绍信息检索的基础概念，第三章，描述一下本文的搜索引擎，第四章，测试实验的实现思路，第五章前两节，给出实验的结果。第五章最后一节，对结果进行分析。最后，第六章进行总结。第2章背景信息检索（IR）是一个较广的领域，一般符合如下定义：是对信息项进行数据表示，存储，组织和访问的领域。作为一个较广的领域，信息检索必须要能够在对信息进行处理后，用户就能够容易地访问到他们关注的信息。另一个也不失一般性的定义，描述如下：信息检索是从大量数据集合（通常是存放在本地服务器或者互联网上）中，查找满足需求的非结构化（文本）数据（文档）集。核心思想是从可以获取到的数据中，检索出具有相关性的部分来满足用户的信息需求。为了实现这个目的，信息检索（IR）系统由几个相互关联的模块组成（图2.1）。通常这些模块含有三个方面的：索引，查找和排序。图2.1：信息检索过程索引：负责表示和组织所有信息，实现高效的信息访问。查询：从索引中抽出满足用户需求的信息。排序：尽管这是非必须的步骤，但对检索来说非常重要，启示式地对检索结果尽可能按照满足用户需求的方式排序。2.1文档收集要有信息可以检索的话，就要先收集信息，作为索引的入口数据。待收集文档可以是任何类型的数据，只要能从中抽取出信息来。这就有很多场景了，要具体看检索系统的应用背景了。2.1.1网页抓取在网页搜索的场景中，网络爬虫是相当必要的。简单来讲，爬虫是能够在网站间游走，并且将访问过的页面下载保存下来。网络爬虫种类很多，有些是商业的，也有开源的。由于网页是海量的，所以为了平衡新页面的抓取和已抓取页面的更新，会采用各种的抓取算法。同样的，也有必要考虑被抓网站的带宽情况，避免把对方网站抓瘫痪了。2.1.2文本检索大会TREC也有已经生成好的文档集合是被用来做学术研究的。例如，文本检索大会（TREC）就准备了大小和类型不同的好几类文档集合，每个都是为不同任务设计的。根据对文档不同的研究目的，研究被分成各种项目类型。例如2007TREC的项目类型有：博客组：目的是展现博客环境中的信息查找的行为规律。企业组：分析企业搜索。满足用户查找企业数据来完成某些任务。基因组：在特定领域的检索研究（基因数据）。垃圾组：对已有的和推荐的垃圾过滤方法进行研究。利用这些文档集合，TREC也作为一个标准的数据集实例，被各个小组采用各种方法去处理，然后基于这相同的实例进行分析得到的不同结果，来讨论和比较不同检索方法。所以TREC也提供一组检索任务和查询结果相关性的判断。Table2.1，倒排索引举例，对每个出现的词，都保存了在文档中的位置列表这样才使得研究不同信息检索（IR）系统的准确率和召回率成为可能。2.2索引要实现对大文档集合的高效率的检索，就需要重新组织数据，存储到特定的设计好的数据结构中。这就是索引，它使得快速检索文档集合变得容易，简单来说，就是减少两两比较的次数。在文本检索中，最常用的数据结构是倒排索引（见表2.1），它包含一个词典，词典包含了所有在文档中出现的词汇。同时，词典中每个单词映射了一个位置列表，列出这个单词在哪些文档中出现了，以及出现的位置信息。当然不同应用对应的需求的类型也不同，在一些应用中，会将文档自身给出来，而不仅仅是位置信息，这依然是一种倒排索引。索引存储需要的空间和文档集合的大小成正比关系，有些方法可以用来减少和优化存储需要的空间。通常来说，一个词典需要的存储空间不大，但是位置列表的存储需要极大的空间。另外，一个搜索引擎的功能也决定着存储空间的大小，这就需要在提供哪些功能和存储空间之间进行平衡。例如，为了给出用户检索词周围的文本片段,有些索引存储了文档的全文，而另外一些索引则不提供文本片段，这样需要的存储空间就较少。一些索引对位置列表进行压缩，（例如采用段地址，将文本切成段，使得多个实例都被划分到较少的段中，而索引地址就指向这些段），但是这种方式的代价是要精确地获取单词的位置时，需要额外开销（在本文的例子中需要顺序扫描目标段）。在索引之前，有个几预处理需要完成，其中最常见的是停用词消减和词根替换。有些词在文档中出现的极为频繁，但是对检索而言，它们的相关性却很小（例如，在英文中，“a”，“an”，“be”，“for”）[对应到中文，“的”，“是”，“这”，“那”等]。它们被称为停用词，不同的应用和不同的语言，有着不同的停用词表。所以停用词消减成为一种常做的预处理，从文本中除去这些停用词，不索引它们，这就大大减少了倒排索引的大小。另一个叫词根替换，这也很常见，除了用户检索的词外，出现在文本当中的这个词的变体形式，例如复数和过去式，也希望能够被匹配。为了解决这个问题，一些索引采用获取词根的算法，在查询的时候用词根来进行替换。词根一般是不带词缀的部分。例如“connect”是“connected”“connecting”“connection”“connections”的词根。预处理也好，索引结构也好，在影响存储空间的同时，也会影响索引的时间开销。之前提过，根据不用的应用需求，建索引过程中可能要在时间开销作出牺牲，以便获得一个更省空间的索引存储。当然，索引的特性也会影响查询，在本文后面会有说明。2.3查询和排序利用倒排索引，查询会变得相当的快捷，基本上，查询的主要步骤是：1.词典查找，查询词会被切分成一组单词，然后在在词典上找索引。这个过程可以通过对词典排序，而变得很迅速。2.检索是否存在，如果在词典中定位到词了，就在找对应的位置列表，看是否存在文档。3.结果处理，为了得到查询词的结果，需要对找到的结果列表进行再处理。根据查询词的类型（布尔型的，近似匹配，使用通配符）不同，操作会不一样，而且意味着需要对结果做额外处理。例如，布尔型查询是最常见的，是由一组查询词（原子的）通过布尔运算（与，或，非）来进行组合，以便查到的文档满足这些运算条件。利用倒排索引可以解决这类查询，唯一要做的处理只是合并各个查询词的位置列表，然后按照布尔条件要求来选择满足条件的位置。另一方面，单词组合和近似查找这两个查询类型的处理相对困难，需要对结果进行复杂的处理。单词组合是指一组词汇以特定的模式在文档中出现。而近似查找则是一种相对弱的关联关系的处理，单词可能相距一定的距离，但是依然满足出现的顺序。对于这些查询，有必要对结果按照单词的位置进行排列，然后再对结果位置列表进行模式匹配。在查询完索引之后，需要对结果按照用户需求进行排序。这个排序阶段是可选的，不是必须的。但是对于网页搜索的场景来说，这个阶段非常重要。影响排序的因素除了查询的结果文档是否匹配查询词外，还有很多其他附加因素。例如，在某些应用下，文档的大小会暗示文档的重要程度。在网页搜索场景，另一个因素是检索的页面是否“流行”（例如综合考虑网页的入链和出链，页面已经存在的时间等等）。查询词命中的位置（例如是在标题里面命中呢，还是正文里面命中），等。2.4检索评估为了分析一个检索系统的质量，需要研究由系统返回的结果是否和输入的查询词匹配。这可以如此来实现，给定一个查询词和一组文档，文档可以划分为与查询词相关的部分和不相关的部分。然后与由检索系统返回的结果相比较。为了形式化表示质量，有几组定义好的质量评价指标可用。本文只关心准确率和召回率以及两者之间的关系。给定一个查询词q和文档集合I，用R来表示相关的文档。用A来表示搜索引擎检索到的文档集合，当提交了查询词q之后，Ra表示由系统检索到的，并且相关的文档。我们定义如下：召回率：检索系统返回的结果中，与q相关的部分与所有相关的文档的比值。Recall=|Ra|/|R|.（1）1个搜索引擎的数据。（b）3个搜索引擎的数据。图2.2：平均准确率/召回率准确率：检索系统返回的结果中，与q相关的部分与所有返回的文档的比值。Precision=|Ra|/|A|由于单个质量指标自身可能不足以描述检索系统的质量（例如，一个检索系统要得到100%的召回率，只要返回所有的文档集合）。只有通过组合以上指标才能来分析评价。例如，为了从趋势图上分析一个检索系统的质量。可以在平面图上描出平均的准确率召回率（如图2.2），然后再来观察这个系统的准确率和召回率。平面图在比较评价不同的搜索引擎的时候也是有用的。例如，图2.2（b）观察3个搜索引擎的曲线。我们发现搜索引擎2在低召回率的时候，准确率比其它的搜索引擎要低，但是随着召回率的增加，它的准确率比较平缓，不像其它引擎退化的那么厉害。另外一个常用标准是在截取部分结果后来统计准确率。例如，分析返回的结果文档的前五个的准确率。经常叫为前n值准确率，（P@n），之所以采用这个标准，主要用户一般习惯于只查看返回结果的前n个，而不是遍历全部的返回结果。正如上文提到的，要分析准确率和召回率，就要对全部文档，分析每个文档和查询词的相关性。并且需要由领域专家来分析查询词对应的需求含义。但是有时候，这种分析变得难以实现，因为整个文档集合会因为过大而不容易分析，或者用户的查询词所代表的含义并不清楚。为了避免类似的问题，TREC大会也提供了一组查询词（或者相关主体）和对应的相关的文档（相关性判断）。利用每个方向所提供的文档集合，和已