利用倒排索引， 查询会变得相当的快捷， 基本上，查询的主要步骤是：
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大会也提供了一组查询词（或者相关主体）和对应的相关的文档（相关性判断）。 利用每个方向所提供的文档集合，和已经定义好的一组主题，以及使用该数据 的意义， 这些就可以在被研究的检索引擎上进行查询， 然后对返回的相关的结果集合进行分析。
第3章 搜索引擎
开源搜索引擎还挺多的。 在本文中，列出了目前主流的搜索引擎， 并且对它们进行了初步的评价， 以便给出一个总体上的 印象。 初步评价用到的标准包括： 开发现状， 项目活跃度， 最后更新时间。 我们比较了29个搜索引擎项目： ASPSeek, BBDBot, Datapark, ebhath, Eureka, ht://Dig, Indri, ISearch, IXE, Lucene, Managing Gigabytes (MG), MG4J, mnoGoSearch, MPS Information Server, Namazu, Nutch, Omega, OmniFind IBM Yahoo! Ed., OpenFTS, PLWeb, SWISH-E, SWISH++, Terrier, WAIS/ freeWAIS, WebGlimpse, XML Query Engine, XMLSearch, Zebra, 和 Zettair。
基于本文收集到的信息， 可以除去部分项目， 因为它们已经太过时了（最后更新时间要早于2000年）。这些项目不死不活的， 又无法得到更多信息。 因此我们除去了ASPSeek,
BBDBot, ebhath, Eureka, ISearch, MPS Information Server, PLWeb, 和 WAIS/freeWAIS.
另外， 也有项目由于其它原因 被丢弃了。 例如尽管MG项目是该领域一个相当重要的工作， 但是由于从1999后就再没有更新过。另外Nutch项目也被忽略了，因为它只是Lucene项目的一次调用。 因此我们只分析Lucene项目。 最后， XML Query引擎和Zebra引擎也被忽略了， 因为这两个项目是专注 于结构化数据（XML），而不是半结构数据（HTML）的。
因此， 剩下来， 本文要覆盖的当前的项目是： Datapark, ht://Dig, Indri, IXE, Lucene, MG4J, mno-GoSearch, Namazu, OmniFind, OpenFTS, Omega, SWISH-E, SWISH++, Terrier, WebGlimpse (Glimpse), XMLSearch, and Zettair。 但是，经过很初步的测试， 就最小的数据集合而言， 本文发现， Datapark, mnoGoSearch, Namazu, OpenFTS, 和 Glimpse的建索引的时间开销是其余项目的建索引时间开销的3到6倍。 因此我们也将它们 排除在外了。
3.1 特征
前面提到， 每个搜索引擎都可以依据它们实现的特性，以及在不同场景下的表现来进行划分。 本文通过分析这些搜索引擎的功能以及内在特性， 给定了13个常用特征来描述划分这些搜索引擎。
存储方式： 索引的存储方式， 要么是用数据库存储或者仅采用文件结构存储。
增量索引： 是否支持向已有的索引 追加新的文件集合， 而不用重新生成整个索引。
结果摘要： 是否支持对结果提取摘 要信息。
结果模板： 部分引擎支持模板来提 前结果信息。
停用词表： 建索引的时候，开放停 用词表接口，可以通过增减高频词，来去掉这些高频词。
文件类型： 索引可以解析的文件的 类型。最常用的类型是HTML。
词根替换： 索引和检索是否支持词 根替换。
模糊查找： 是否支持模糊查找， 而不要精确匹配。
结果排序： 根据不同的标准对结果 进行排序。
排序策略： 在提供查询结果的时 候，采用的排序策略。
搜索类型： 是否支持查询词的组合 操作。
编程语言： 建索引实现的编程语 言。 这个信息在对项目进行扩展或者继承的时候会相当有用。
版权信息： 指明允许使用和二次开 发的条件。
在表3.2中列出了每个搜索引擎的特征信息。 为了决定采用哪个搜索引擎， 有必要将所有特征来整体分析， 并且要补充上性能评估 的信息。
简单描述一下将要分析的每个搜索引擎， 主要有谁在哪里开发的， 和项目赖以著称的特征。
ht://Dig， 提供一组工具可以索引和搜索一个站点。 提供有一个命令行工具和CGI界面来执行搜索。尽管已经有了更新的版本了， 但是根据项目的网站， 3.1.6版是最快的版本了。
IXE Toolkit， 是模块化C++类集合， 有一组工具完成索引和查询。Tiscali（来自意大 利）提供有商业版本， 同时提供了一个非商业版本仅用于科学研究。
Indri， 是基于Lemur的搜索引擎。Lemur是用来研究语言模型和信息检索的工具。这个项目是马萨诸塞大学和CMU的合作项目的产物。
Lucene， 是Apache 软件基金会的一个文本搜索引擎库。 由于它是一个库， 所以很多项目基于这个库， 例如Nutch项目。在目前， 它 捆绑自带的最简单的应用是索引文档集合。
MG4J（管理前兆数据Java语言）是针对大文本集合的一个全文 索引工具。由米兰大学开发。他们提供了通用的字符串和位级别的I/O的优化的类库作为副产物。
Omega， 基于Xapian的应用。Xapian是开源的统计信息检索库， 由C++开 发， 但是被移植到了（Perl Python php， Java， Tcl， C#）等多种语言。
IBM Omnifind Yahoo! Edition， 非常适合内网 搜索的搜索软件。 他结合了基于Lucene索引的内网搜索，和利用Yahoo 实现的外网搜索。
SWISH-E（简单网页索引系统—增强版）， 是开源的索引和检索引擎。是Kevin Hughes 开发的SWISH的增强版。
SWISH++是基于SWISH-E的索引和检索工具。尽管经过C++全部重写， 但是 没有实现SWISH-E的全部功能。
Terrier（太字节检索）， 由苏格兰的格拉斯哥大学开发的，模块化的平台，能够快速的构架互联网， 内网， 和 桌面的搜索引擎。 它附带了索引，查询和评估标准TREC集合的功能。
XMLSearch， C++开发的索引和检索的一组类。利用文本操作（相等，前缀，后缀，分段）来扩展了查询能力。 Barcino（来自智利）提供了一个商 业版， 同时也有个供学术研究的非商业版。
Zettair，（先前称为Lucy）， 由皇家墨尔本理工大学的搜索引擎小组开发的文本检索引擎。主要特征是能够处理超大量的文本。
史春奇，
搜索工程师，
中科院计算所毕业，