信息检索札记-完整搜索系统的评分计算
前面我们给出了文档评分中词项权重计算的理论，并由此导出向量空间模型和基本余弦相似度评分算法。当然不少策略不会精确返回与查询相匹配的K篇文档，一些策略也可以推广到余弦相似度计算之外的其他场合中去。
快速评分算法以及排序
前面介绍通过计算查询与文档的余弦相似度来给文档评分：
在上面这个公式中，我们对V(q)，进行了一个归一化处理。例如查询q=[jealous gossip]，归一化后为v(q)=[0.707 0.707]。其实我们没必要归一化，直接用[1 1]的查询向量，这样我们做向量乘积的时候就乘1，这个就不需要乘了，最后直接转换为加法。
根据上面的分析计算出每篇文档的得分，然后利用TopK算法选出得分最高的K篇文档。如果我们每次都要计算N篇文档的分数，那么这个工作量很大，下面介绍一下简单的方法：
（1）非精确返回前K篇文档：为了避免文档集中的大多数的评分计算。我们选择一个文档子集A，它包含了参与最后竞争排名的候选文档，A不必包含K篇得分最高的文档，但是它应该包含很多和前K篇文档得分相近的文档。那么我们只需要返回得分A中得分最高的K篇文档。
（2）索引去除技术：只考虑那些idf（逆文档频率）超过一定阀值的文档；只考虑包含多个查询词的文档。
（3）胜者表：称为优胜者表，对于词典中的每个词项t，预先计算出r个最高权重的文档，r值事先给定，词项t所对应的tf值最高的r篇文档构成t的胜者表。（注：按照正常的topk算法，我们应该是选出每个词项t的前k个最高权重文档构成胜者表，然后再从胜者表选出全局的TopK）
（4）静态得分和排序：很多搜索引擎中，每篇文档d往往都有一个静态得分g(d)，我们选择胜者表的时候加上文档的静态得分。
（5）簇剪枝方法：先通过对文档聚类来进行预处理操作。然后在查询处理时，只考虑利用少数几个簇中的文档进行余弦相似度计算。具体的预处理步骤：先从N篇文档中选出sqrt(N)个先导者；对于不属于先导者的文档计算离之最近的先导者（这里的最近，表示余弦相似度最大）；给定查询后我们先与sqrt(N)先导者计算相似度，找出最近的先导者，然后从相似度最大的先导者中去匹配该先导者的追随者，从而选出TopK。主要思路，我们只需要在距离最近的这一类中去匹配，其他类就不需要匹配了。下面画个示意图。
【注】上面这个图中，一个追随者只属于一个先导者，其实一个追随者还可以属于多个先导者，这样的聚类更复杂。
【注】关于聚类方法：K-means方法，EM算法，DBSCAN算法（基于密度的方法），CLARANS算法（划分方法），
BIRCH算法（层次方法），CLIQUE算法（综合了基于密度和基于网格的算法）
信息检索系统组成
一个完整的信息检索系统并不仅仅支持向量空间模型，也支持其他的查询操作符。
（1）层次索引
我们检索简单的建立一个倒排表，而是根据词项频率大小分层多个倒排表。例如，可能第一层索引表示词项i频率大于100的索引，第二层索引表示词项频率大于50的索引，第三层索引表示表示词项频率大于0的索引。这样我们查询的时候从上层往下查，当我们在第一层能获得topK篇文档，就没必要往下走了。
（2）查询词项的邻近特性
例如，对于“stained mercy”这样一个查询，我们要考虑这两个词在文档中的距离，通过距离进行加权。
向量空间模型对各种查询操作的支持
我们介绍了支持*文本查询的向量空间模型，而前面介绍的几种查询操作，而实际上增加了查询的表达能力。下面考察能否在用向量空间模型的同时，支持这些查询操作，从而增加表达能力。在建立一个搜索引擎时，我们往往希望能够支持用户的多种查询操作符。
向量空间模型支持*文本查询，这与前面的布尔查询、通配符查询和短语查询处理有所不同。下面看看向量空间模型怎么支持这些查询。
（1）向量空间模型显然能够处理布尔查询。
（2）对于通配符查询rom*，我们将所有可能的词项输入到查询向量中去，这样通配符查询也能支持。
（3）对于短语查询，如果短语被转换为向量，丢失了短语的位置信息。所以我们用向量空间模型来检索“german sherpherd”类型短语的时候，只能检索出两个词项权重较高的文档，不能保证2个词项连续出现。
后记
至此，本文准备阅读信息检索基础篇结束。