Xapian：检索

经过前面几篇的介绍，如果再参考一下Omega的话，估计应该可以顺利创建database和往database里添加document了。有了数据，下一步关心的当然是怎样将它们查出来，在一个IR系统（不单止Xapian）中，检索的方式是多元化的，排序则是多样化的，结果则是人性化的，这就是跟关系数据库相比的最大优势。由于内容较多，因此将检索、排序和取得结果分开讲述，这一篇先讲述如何检索。

IR系统有这么多的好处，因此终端用户对它是有很高期望的，世事万物总不会完美的，于是IR系统有三个评价标准：召回率、准确率与查询效率。三个指标相互矛盾，只有取舍、不能调和，这亦是一个博弈的过程，使用者关心不同的指标，自然会采用不同的观点和做法。拿Web搜索引擎来说，查询效率肯定是摆在第一位的，其次才能考虑准确率和召回率。看字面看上去，大家心里估计对准确率还有个谱，但召回率又如何解释呢？

准确率和召回率

有时候，准确率也称为精度，举个例子，一个数据库有500个文档，其中有50个文档符合定义的问题。系统检索到75个文档，但是只有45个符合定义的问题。

召回率R=45/50=90%

精度P=45/75=60%

本例中，系统检索是比较有效的，召回率为90%。但是结果有很大的噪音，有近一半的检索结果是不相关。通常来说，在不牺牲精度的情况下，获得一个高召回率是很困难的。对于一个检索系统来讲，召回率和精度不可能两全其美：召回率高时，精度低，精度高时，召回率低。对于搜索引擎系统来讲，它可以通过搜索更多更多的结果来查到更多相关结果，从而提高召回率(查全率)，但也会导致查到更多不相关结果，从而降低了搜索结果的精度(查准率)。因为没有一个搜索引擎系统能够搜集到所有的WEB网页，所以召回率很难计算。所以一般来说，不会单独的使用召回率或精度，而是在其中一个值固定的基础上，讨论另一个值。如当召回率为60%时的精度值变化情况。因此在召回率与准确率中，Web搜索引擎会更倾向于后者，因为终端用户最想得到的他们要想得到的数据，而不是一堆似是而非的数据。

但是，对于一个传统的图书信息检索系统，情况会大不相同——书籍与文章有良好的关键字索引，包括标题、作者、摘要、正文、收录时间等定义明确的结构化数据，文档集合相对稳定并且规模相对较小，想更深一层，终端用户可能只知道某图书名的其中一两个字，那么如果在较低的召回率下，此用户可能会铩羽而归。

说到这里我们应该差不多知道IR系统在不同的应用场合下是有不同的准确率和召回率作为评价指标的，而准确率和召回率则是由分词策略直接影响的，拿我们最关心的中文分词来说，分词策略一般有以下几种：

l        第一种，默认的单字切分。这种分词策略实现起来最简单，举个例子，有以下句子：“我们在吃饭呢”，则按字切分为[我]、[们]、[在]、[吃]、[饭]、[呢]。按这种方法分词所得到的term是最少的，因为我们所使用的汉字就那么几千个，但随便所索引的数据量的增大，索引文件的增长比例却比下面的几种模型都要大，虽然其召回率是很高的，但精确率却非常低，而且一般情况下性能也是最差的。

l        第二种，二元切分，即以句子中的每两个字都作为一个词语。继续拿“我们在吃饭呢”这个句子作例子，用二元切分法会得到以下词：[我们]、[们在]、[在吃]、[吃饭]、[饭呢]。这种切分方法比第一种要好，精确率提高了，召回率也没降低多少（实际上两者都不高，太中庸了）。

l        第三种：按照词义切分。这种方法要用到词典，常见的有正向最大切分法和逆向最大切分法等。我们再拿“我们在吃饭呢”作为例子。使用正向切分法最终得到词语可能如下：[我们]、[在吃]、[饭]、[呢]，而使用逆向最大切分法则可能最终得到以下词语：[我们]、[在]、[吃饭]、[呢]。只要处理好在庞大的词典中查找词语的性能，基于词典的分词结果会挺不错。

l        第四种：基于统计概率切分。这种方法根据一个概率模型，可以从一个现有的词得出下一个词成立的概率，也以“我们在吃饭呢”这个句子举个可能不恰当的例子，假设已经存在[我们]这个词语，那么根据概率统计模型可以得出[吃饭]这个词语成立的概率。当然，实际应用中的模型要复杂得多，例如著名的隐马尔科夫模型。

在实际的中文分词应用中，一般会将按词典切分和基于统计概率切分综合起来，以便消除歧义，提高精确率。

性能

前面提到，按单字切分的查询性能可能反而是最差的，咋一眼看上去，这种分词方式低精度高召回率是没错，但为什么说它性能不好呢。为了方便解释，我们假设有两万篇文章需要被存储和索引，假设文章里所有内容都是汉字，我们常用的汉字有4000～5000个，那么最理想的情况下平均每个汉字索引了4～5篇文章，可惜实际上有很多汉字的出现频率是非常高的，就拿上面的[我]、[们]、[在]、[吃]、[饭]、[呢]这几个汉字来说，在每篇文章中出现的概率估计至少得有70%～80%。

常见的存储方式是将索引和数据（即文章内容）分开存放，以各种树（红黑树、AVL树或B*树）来存储索引，每个结点除了保存父结点和儿子结点的指针外，一般还会保存其索引的文章的Id（在Xapian里就是DocId），通过这个Id可以很快地找到文章内容。在Xapian中，DocId是以32位无符号整数来表示的，占4个字节，如果“我”字在两万篇文章中出现的概率是50%，那么“我”字这个结点就至少占了4*1000个字节，差不多足足40K！如果某天我们的永久存储体和内存的速度一样快了，这种存储方式问题其实还不大，但由于我们现在普遍使用硬盘/磁带机来保存永久数据，商用的硬盘/磁带机的结构是使用由机械臂控制的磁头来读写盘片来存取数据的，为了减少磁头定位的次数，硬盘/磁带机会设计成按页读取，每页占2~2字节，虽然经过这样的精心设计，但硬盘/磁带机的存取速度还是比主存慢5个数量级左右，这就是I/O是最耗性能的原因，也是我们天天说的“数据库是瓶颈”的原因所在。

很明显，如果按上述的推论，“我”这个结点要占10个以上磁盘页，这太疯狂了。如果通过分词技术将文章切分为多个词语，那么每个词语所索引文章必定减少。前面提到大部分的IR系统或数据库系统的索引都是以B*树的形式来存储的，B*树是一种硬盘I/O性能非常好的数据结构，其特点是一般每个结点的大小和硬盘上每页的大小是一样的，每个结点能存放n个关键字，而每个结点又有n+1个子女，也就是说，在一棵高度为2的B*树中，最多只需要读取2个结点就可以到达目标结点，也就是说控制磁头的机械臂只移动了两次。在这个时候，良好的数据结构的优越性就显示出来了。

当然，这只是纯粹以硬盘/磁带机为中心来讨论，在实际应用中架构会更加良好，而且如果只有两万篇文章，当我们的主内存足够大的时候，甚至可以一次过将所有文章读到内存中以避免进行硬盘I/O操作，只是这样也带来了写入数据时非常缓慢的尴尬。现在的数据库或IR系统的数据文件动辄几个GB，因此怎样最大限度避免进行频繁的硬盘I/O读写还是放在提高性能的第一位的。

不过千万别以为IR系统一切都比关系数据库要好，IR系统的其中一个弱点是插入、修改和删除都相对缓慢，因为是中间要经过多层的工序处理，所以IR系统的首要任务是检索，其次才是存储。

布尔型检索

虽然IR系统会帮我们分词，但有时候我们却想“帮助”IR系统理解我们要搜索什么。例如，我们可能会在百度或Google的搜索栏里输入：“我们吃饭”来寻找我们感兴趣的关于“我们”和“吃饭”的文章，而不是直接输入“我们吃饭”来搜索文章。这两种的输入得到的结果是完全不同的，因为“我们吃饭”已经成为了Google的IR系统里的其中一个term了。

像“我们吃饭”这样的输入，其实就是布尔型检索。在Xapian里，则是将多个terms用AND、 OR或AND_NOT连接起来，举个例子：

t1 索引了 documents 1 2 3 5 8

   t2  索引了 documents 2 3 6

那么：

    t1 AND t2  检索得 2 3

    t1 OR t2   检索得 1 2 3 5 6 8

    t1 AND_NOT t2  检索得 1 5 8

    t2 AND_NOT t1  检索得 6

     在很多系统中，这些documents并没有根据它们之间的相关度来排序的；但在Xapian里，布尔型风格的查询都可以在检索得出documents集合结果后，然后使用概率性的排序。

概率性IR和相关度

      布尔型检索是最常用的，但在IR系统中，其还没能担大旗，因为使用布尔型检索得到的结果并没有按任何机制使其能变得对用户更友好，在这种情况下，用户必须对这个IR系统有充分的了解才能更有效地使用之。虽然如此，但只有纯粹的布尔型检索的IR系统依然活得好好的。

相关度是概率模型里的核心概念，可以将documents的集合按相关度来排列。本质上，当某个document是用户需要的，那么它则是相关的，否则便是不相关的，在理想状态下，检索到的document都是相关的，而没检索到的则是一个都不相关的，这是一个黑与白的概念。不过检索很少是完美的，因此会出现风马牛不相及的情况，于是便用相关度来表示，指两个事物间存在相互联系的百分比，这是一个非常复杂的理论。

Xapian默认的排序模式称为BM25Weight，这是一种将词频和document等元素出现的频率通过一个固定的公式得出排序权重的模式，权重越高则相关度越高，如果不想使用BM25Weight作为排序模式，可以使用BoolWeight，BoolWeight模式里的各种元素的权重都为0。排序会在后续文章里继续讲述。

组合检索

默认情况下，Xapian可以使用任意组合的复杂的布尔型查询表达式来缩小检索的范围，然后将结果按概率性排序（某些布尔型系统只允许将查询表达式限制为某种格式）。

布尔型检索和概率性检索有两种组合的方式：

• 先用布尔型检索得到所有documents中的某个子集，然后在这个子集中再使用概率性检索。
• 先进行概率性检索，然后使用布尔型检索过滤查询结果。

这两种方式的结果还是有稍稍区别的。举个例子，在某个database里包含了英文和法文两种documents，“grand”这个词语在这两种语言中都存在（意思都差不多），但在法文中更常见，不过如果使用第一种方式，先用布尔型检索先限定出英文子集，这个词语则会得到更多的权重。

      第一种方法更精确，不过执行效率不高，Xapian特地优化了第二种方法，别以为Xapian真的先进行概率性检索再进行布尔型检索的，实际上Xapian是同时执行这两种操作的。在Xapian内部进行了几种优化，例如如果通过概率性检索能得出结果，Xapian就会取消正在执行的布尔型AND操作。这些优化方法经过评测可以提高几倍的性能，并且在执行多个Terms查询时会有更好的表现。

QueryParser

      在IR系统中，终端用户按某种系统约定的格式输入，这些输入便称为“查询”。然后IR系统将此输入转交给查询器，查询器也是IR系统的一部分，其可以解析“查询“，匹配documents和对结果集进行排序，然后返回结果给终端用户。

      在Xapian中，Query类便起着“查询”的作用，Query类的生成方法有两种，第一种是由QueryParser类解析查询字符串生成，别一种则是创建多个表示不同描述表达式的Query类，然后再将这些Query按需组合起来。

      以下是Xapian::QueryParser支持的语法，其实这些语法跟其它IR系统的语法亦很相似。

l        AND

expression And expression提取这两个表达式所匹配的documents的交集。

l        OR

expression OR expression提取这两个表达式匹配的documents的并集。

l        NOT

expression NOT expression提取只符合左边的表达式的documents集合。

如果FLAG_PURE_NOT标志被设置，那么NOTexpression表达式不提取匹配符合此表达式的documents。

l        XOR

expression XORexpression 只提取左表达式和右表达式其中一个表达式匹配的documents，而不提取两者都匹配的documents。

l        组合表达式

可以使用括号将上述布尔操作符括起来从而控制其优先级，例如：(one OR two) AND three。

l        +和–

一组标记了+或-操作符的terms只提取匹配所有的+terms，而不匹配所有的-terms。如果terms不标记+或-操作符会有助于documents的排名。

l        NEAR

one NEAR two NEAR three会提取符合这三个关键字的词距在10之间的documents，词距从那里来？在《利用Xapian构建自己的搜索引擎：Document、Term和Value》这篇文章里就曾介绍过可以使用Document类的add_posting方法来添加带词距的terms。

NEAR默认的词距是10，可以使用NEAR/n来设置，例如one NEAR/6 two。

l        ADJ

ADJ跟NEAR很相似，不过ADJ两边的terms是按顺序来比较的。因此one ADJ two ADJ three是表示one与two与three之间的词距都是10。

l        短语搜索

一个短语是被双引号括着的，可以用在文件名或邮件地址等地方。

l        使用字段名的形式

如果database里的terms已经添加了前缀，那么可以使用QueryParser的add_prefix方法来设置前缀map。例如QueryParser.add_prefix("subject", "S")这样便将subject映射到S，如果某个term的值为“S标题”，那么可以使用“subject:标题”这样的表达式来检索结果。这时大家可能会记起Google也支持这种语法，例如在Google的搜索栏里输入“Site:股票”时，只会检索出里的关于股票的网页，这功能其实亦实现了Lucene的Field功能。

l        范围搜索

范围搜索在Xapian中是由Xapian::ValueRangeProcessor类来支持的，在Xapian 1.0.0以后才出现。从Xapian::ValueRangeProcessor的名字可以知道，其只能搜索Value的范围，而不能搜索terms的范围。

Xapian::ValueRangeProcessor是一个抽象基类，因此在实际应用中要使用其子类，Xapian提供了三个开箱即用的Xapian::ValueRangeProcessor的子类，分别是StringValueRangeProcessor、DateValueRangeProcessor和NumberValueRangeProcessor，如果觉得这三个类不能满足需求，亦可以继承Xapian::ValueRangeProcessor来创建自己的子类。

当使用Xapian::ValueRangeProcessor的子类时，应该将开始范围和结束范围传给它，如果Xapian::ValueRangeProcessor的子类无法明白传进来的范围，它会返回Xapian::BAD_VALUENO。

下面仅以StringValueRangeProcessor举例，当database里将用户名保存在Number为4的Value中（Value是通过数字来标识的，详细请看《利用Xapian构建自己的搜索引擎：Document、Term和Value》），那么可以这样组织查询表达式：mars asimov..bradbury，只是这样当然还不够，还需要创建一个StringValueRangeProcessor

Xapian::QueryParser qp;

Xapian::StringValueRangeProcessor author_proc(4);

qp.add_valuerangeprocessor(&author_proc);

当QueryParser解析查询表达式时会使用OP_VALUE_RANGE标志，因此QueryParser生成的query会返回以下描述：

Xapian::Query(mars:(pos=1) FILTER (VALUE_RANGE 4 asimov bradbury)

(VALUE_RANGE 4 asimov Bradbury)这个子表达式使用仅仅匹配Number为4的Value的值是>= asimov 和<= bradbury（使用字符串比较）。

值范围搜索并不复杂，更多的介绍请看。

l        别名

QueryParser亦支持别名检索，使用这样的语法：~term。如何添加别名，后面会介绍。

l        通配符

QueryParser支持以“*”结尾的通配符，因此“wildc*”可以匹配“wildcard”、“wildcarded”、“wildcards”、“wildcat”、“wildcats”。不过这功能默认是关闭的，可以将Xapian::QueryParser::FLAG_WILDCARD

作为标志传到Xapian::QueryParser::parse_query(query_string, flags)来开启按以下步骤来开启。

Query

      如果不想使用字符串形式的查询表达式，可以用下面这些操作符将多个Query组合起来：

OP_AND	等同于QueryParser所支持的AND
OP_OR	等同于QueryParser所支持的OR
OP_AND_NOT	等同于QueryParser所支持的AND_NOT
OP_XOR	等同于QueryParser所支持的XOR
OP_AND_MAYBE	只返回左边子表达式匹配的documents，不过两边的表达式所匹配的documents都加入权重计算。
OP_FILTER	作用跟AND相似，不过仅仅左边的表达式匹配的documents才加入权重计算。
OP_NEAR	等同于QueryParser所支持的NEAR
OP_PHRASE	等同于QueryParser所支持的ADJ
OP_VALUE_RANGE	等同于QueryParser所支持的范围搜索
OP_SCALE_WEIGHT	给子表达式指定权重，如果权重为0，则此表达式为纯布尔型查询
OP_ELITE_SET	作用跟OP_OR 很相似，不过有时候性能比OP_OR 要好。这里有详细的解释：
OP_VALUE_GE	返回大于或等于给定的document value
OP_VALUE_LE	返回小于或等于给定的document value

 

l        如何创建一个只包含一个term的Query

可以使用默认的构造函数：Xapian::Query query(term);

亦可以使用多参数的构造函数：

Xapian::Query(conststring & tname_,

       Xapian::termcountwqf_ = 1,

       Xapian::termposterm_pos_ = 0)   其中wqf的全称是WithinQuery Frequency，可以指定此term在query中的权重。如果整个查询只包含了一个term，这参数用处不大；但当组合查询时，威力便显出来了，因为可以便取得的结果集跟这个term是更相关的。

      而term_pos是指term在query中的位置，同样如果整个查询中只包含了一个term则用处不大，因此一般用在词组搜索中。

l        将多个Query组合起来查询

通过上面所说的Query操作符将Query组合起来，这时要用到Xapian::Query的另一个构造函数：

Xapian::Query(Xapian::Query::opop_,

       const Xapian::Query &left,

   const Xapian::Query &right)

l        概率性查询

一个普通的概率性查询其实是将terms用Xapian::Query::OP_OR连接起来。例如：

Xapian::Queryquery("regulation"));

   query = Xapian::Query(Xapian::Query::OP_OR,query, Xapian::Query("import"));

   query = Xapian::Query(Xapian::Query::OP_OR,query, Xapian::Query("export"));

   query = Xapian::Query(Xapian::Query::OP_OR,query, Xapian::Query("canned"));

query =Xapian::Query(Xapian::Query::OP_OR,query, Xapian::Query("fish"));

不过这样的风格太臃肿了，可以用下面这种清爽一点的风格：

   vector terms;

   terms.push_back("regulation");

   terms.push_back("import");

   terms.push_back("export");

   terms.push_back("canned");

   terms.push_back("fish");

    Xapian::Query query(Xapian::Query::OP_OR, terms.begin(), terms.end());

l        布尔型查询

假设有这样的布尔型查询表达式：

   ('EEC' - 'France') and ('1989' or '1991' or '1992') and 'Corporate Law'

This could be built up as bquery like this,那么则用Query来表示则如下

   Xapian::Querybquery1(Xapian::Query::OP_AND_NOT,"EEC", "France");

   Xapian::Querybquery2("1989");

   bquery2 = Xapian::Query(Xapian::Query::OP_OR,bquery2, "1991");

   bquery2 = Xapian::Query(Xapian::Query::OP_OR,bquery2, "1992");

   Xapian::Querybquery3("Corporate Law");

 

     Xapian::Query bquery(Xapian::Query::OP_AND, bquery1, Xapian::Query(Xapian::Query::OP_AND(bquery2, bquery3)));

还可以将上面创建的bquery对象附加到另一个概率性查询作为布尔型过滤器用来过滤结果集：

query =Xapian::Query(Xapian::Query::OP_FILTER,query, bquery);

l        +和– 操作符

例如有这样的查询表达式：regulation import export +canned +fish –japan

转化为Query则是如下：

vector plus_terms;

   vector minus_terms;

   vector normal_terms;

 

   plus_terms.push_back("canned");

   plus_terms.push_back("fish");

 

   minus_terms.push_back("japan");

 

   normal_terms.push_back("regulation");

   normal_terms.push_back("import");

   normal_terms.push_back("export");

 

   Xapian::Queryquery(Xapian::Query::OP_AND_MAYBE,

       Xapian::Query(Xapian::Query::OP_AND,plus_terms.begin(),plus_terms.end());

   Xapian::Query(Xapian::Query::OP_OR,normal_terms.begin(),normal_terms.end()));

 

   query = Xapian::Query(Xapian::Query::OP_AND_NOT,

       query,

       Xapian::Query(Xapian::Query::OP_OR,minus_terms.begin(),minus_terms.end()));

实战

当使用QueryParser类或Query类创建了Query对象后，只需要实例化一个查询器就可以使用这些Query对象了。例：

Xapian::Databasedb("Index");

Enquireenquire(db);

enquire.set_query(query);

当然，要想取得结果集、对结果集排序或扩展查询还需要更多的功夫，会在下一篇里继续讲述。