Lucene的搜索打之从理论到源码的分析

1、物品相似

• 如何判断俩个事物相似呢？这时可能会有人说，提取特征，比较特征相似的个数；真的只有这么简单吗？如果我们提取特征眼睛个数，耳朵个数，是否有尾巴仅仅三个特征，计算的结果那岂不是一模一样了，但实际并不是；原因在哪呢，特征不对，哪里不对呢，因为这些特征不是他们各自标志性的特征，就比如我一说 哎呦 不错哦，那肯定是和周杰伦有关； 不知不觉我已经讲到了lucene评分算法的核心，tf 和idf; tf是衡量已有特征相似相似程度，idf是衡量每个特征的重要程度，也就是其标致性程度，下面我们详细讲解

• 文档是段落&标题的集合
• 句子是短语的集合
• 段落标题是句子的集合

• 文档如何判断相似呢？我们给它进行拆解，拆解分词
• 文档如何提取特征呢——分词？分词好比这里面的特征工程，他的好坏直接决定后续的评分；
• 当然分词器单讲也能讲很多，包括短路径，统计概率模型 n元分词器等等

2、向量空间模型

• q : query，表示一个查询
• d : document，表示一篇文档

• 当然要计算相似性，必须要进行抽象，抽象到数学模型（这块基本都是中学知识 ），只有抽象到数学模型才能进行计算，数学理计算相似度常用的就是余弦相似度，如图； 几何模型在n-model 向量夹角越小 越相似
• 向量空间模型是信息检索领域中一种成熟和基础的检索模型。这种方法以3维空间中的向量作为类比，维度就是做好索引的term，比如这里以3个主要的关键词奥巴马，叙利亚和战争为三个维度，通过文档在各个维度上的权重，每个文档以及查询都会在空间中有一个向量，直观的看起来，两个向量越相似，则他们的夹角越小，所以，用起反比的cos，则可以得到，cos值越大，则两个向量越相似。同理便可以将3维空间推广到多维空间去。
• 现在的问题就变成，如何求得每个维度上的term在文档中的权重，在向量空间模型中，特征权重的计算框架是TF*IDF框架，这里TF就是term在文档中的词频，TF值越大，说明该篇文档相对于这个term来说更加重要，因此，权重应该更高；而IDF则是term在整个文档集中占的比重，即n/N，其中n是含该term的文档数，N是总文档数，但是，实际使用中往往习惯用
  
  

• 即所包含的该term的文档数越少说明该term越重要。可以举个例子，有100篇文档，其中80篇都在说红楼梦，其中只有几篇讲到计算机，当你在这个文档集中搜索到计算机时，可以肯定这几篇讲计算机的比较重要，而搜索红楼梦时，则很难区分哪篇更加重要，换句话说，在这个文档集合中，计算机比红楼梦更有区分度，相对来说，计算机比红楼梦更有信息量，所以IDF就是评判所含信息量大小的一个值
• 那么，在lucene中，是如何应用这个模型的呢？根据向量空间模型的的数学推导（见参考文档3），可以看到，在lucene中实际上是将sim(dj,q)变形和调整后应用了如下一个打分公式

• coord(q,d): 协调因子，它的计算是基于文档d中所包含的所有可供查询的词条数量
• tf: 单词t在文档d中出现的词频，对词频开根号是希望对一篇出现太多相同关键词的文章进行相应的惩罚，即
• idf: 单词t在文档集中的比重
• t.getBoost(): 在搜索过程中影响评分的参数
• norm(t,d): 字段的标准化值，表明在字段中存储了多少词条，这个数值是在索引过程中计算出来的，并且也存储在索引中，可以在TFIDFSimScorer中的norms找到，其中一个参数LengthNorm是在DefaultSimilarity中定义的，另一个参数则是每次索引过程中每次处理一个field时累乘上去的

3、公式推导过程

• TFIDFSimilarity的评分公式的推导，接下来先来统一一下术语和记号，q : query，表示一个查询，d : document，表示一篇文档，

• 因此：

• 通常来说每个Query的每个词条的出现次数都是1，因此 tf(t1)=tf(t2)=...=tf(ti)=a,a∈(0,1]tf(t1)=tf(t2)=...=tf(ti)=a,a∈(0,1] tf(t_1) = tf(t_2) = ... = tf(t_i) = a, a\in(0, 1]tf(t1)=tf(t2)=...=tf(ti)=a,a∈(0,1]。

• 由上式易知a对同一个Query而言是一个常量，因此上式可以进一步简化为

• idf计算：

• 我们知道：lucene TFIDFSimilarity给出的理论评分公式,，发现|V(d)|不见了？
• |V(d)|是一个单位向量，因此它并不带文档的长度信息。但是文档由多段不一样文本构成的，那么文档长度信息可能会有影响。为此，使用不同文档长度归一化因子，可实现一个向量大于或等于它的单位向量doc-len-norm(d)。

• 什么是 doc-len-norm(d)
• 名思义，它是文档长度归一化因子，即是弱化文档长度对终评分的影响。 首先lucene文档是可以有多个字段，而且搜索时被指定字段. 由此可以用搜索时指定搜索字段ff ff的归一化因子来表示文档的归一化因子，所以就把问题转化算字段ff ff的归一化因子的问题了。设
• norm(t,d)norm(t,d) norm(t,d)norm(t,d)表示文档d的搜索字段ff ff的归一化因子。todo.....

• |V(q)| : 细心的你可能已经知道了|V(q)|是怎么回事，对的没错它就是queryNorm的别名。看一下QueryNorm的公式

它使得两个不同Queries的搜索结果的每个文档的得分可以比较,可以比较意思是它们的比较是有意义的。

ueryNorm不影响排名，也就是不影响评分，就是对于同一个Query来说queryNorm是的。好吧，这说法并不准确，应该是对于同一个Index的同一个Query它的queryNorm是的。如果不能理解就看公式吧，作为查询归一化，那么它作用就是缩小同一个Query在不同Index上产生的影响。这使得分布式查询（同一个Query用在不同的Index上并计算文档的分数）的评分变得有意义和有可比性。

不影响排名，也就是不影响评分，有两层意思：

1、在单个Index而queryNorm是没意义，不会影响评分和排序。

2、对于多个Index，queryNorm实际上是会影响的评分和排序。只是这影响是降低不同的index之间在搜索时的影响，因此可以认为没有影响。

• 实践公式即将出现

整理可得:

·4、源码分析

• 概述：从索引文件角度来说搜索过程，在IndexSearch 初始化的时候先就将.tip .tim文件的内容加载到内存中，在Search的过程中，会从.tip .tim文件中查找到关键词（Terms），然后顺着这些Terms 去.doc文件中查找命中的文档，后取出文档ID。这是一个复杂的过程，我们主要来讲解评分的过程。
• lucene检索时序图大致如下：

• 首先我们看IndexSearcher.search主入口

/** Lower-level search API.
*
* <p>{@link LeafCollector#collect(int)} is called for every matching document.
*
* @throws BooleanQuery.TooManyClauses If a query would exceed
* {@link BooleanQuery#getMaxClauseCount()} clauses.
*/
public void search(Query query, Collector results)
throws IOException {
//search主入口
search(leafContexts, createNormalizedWeight(query, results.needsScores()), results);
}

• 再看IndexSearcher.CreateNormalizedWeight
• /**
* Creates a normalized weight for a top-level {@link Query}.
* The query is rewritten by this method and {@link Query#createWeight} called,
* afterwards the {@link Weight} is normalized. The returned {@code Weight}
* can then directly be used to get a {@link Scorer}.
* @lucene.internal
*/
public Weight createNormalizedWeight(Query query, boolean needsScores) throws IOException {
query = rewrite(query);//重写查询
//生成Weight
Weight weight = createWeight(query, needsScores);
float v = weight.getValueForNormalization();
float norm = getSimilarity(needsScores).queryNorm(v);
if (Float.isInfinite(norm) || Float.isNaN(norm)) {
norm = 1.0f;
}
weight.normalize(norm, 1.0f);
return weight;
}
• rewrite重写查询： Lucene 将Query 重写成一个个TermQuery组成的原始查询 ，调用的是Query的Rewrite 方法，比如一个PrefixQuery 则会被重写成由TermQuerys 组成的BooleanQuery 。所有继承Query的 比如BooleanQuery ,PhraseQuery，CustomQuery都会覆写这个方法以实现重写Query。
• createWeight： 计算weight，Weight 类是Search过程中很重要的类，它负责生成Scorer (一个命中Query的文档集合的迭代器，文档打分调用Similarity 类就是Lucene自己的TF/IDF打分机制) 。createWeight是Query 主动发起的，BooleanQuery 发起，内部其实又是TermQyery发起的，TermQyery发起createWeight，其实内部是new了一个对象TermWeight， TermWeight很重要，几乎所有的核心计算都是在这里完成的，TermWeight也是TermQyery的一个内部类。在TermWeight生成过程中，构造方法内，会主动获取相似度插件，相似度插件在去计算computeWeight，如果是用的tf-idf相似度插件，那就是看TFIDFSimilarity.computeWeight， 在调用前，会传递俩个参数，
• CollectionStatistics collectionStats： 主要包含文档和字段的相关统计信息
• TermStatistics... termStats： 名字term的统计信息，包括词频docFreq,totalTermFreq

• 后computeWeight返回生成SimScorer， 以TFIDFSimilarity为例，就是IDFStats，该对象主要包含了idf统计信息。部分代码如下：
• 
  

public class TermQuery extends Query {

private final Term term;
private final TermContext perReaderTermState;

final class TermWeight extends Weight {
private final Similarity similarity;
private final Similarity.SimWeight stats;
private final TermContext termStates;
private final boolean needsScores;

public TermWeight(IndexSearcher searcher, boolean needsScores, TermContext termStates)
throws IOException {
super(TermQuery.this);
if (needsScores && termStates == null) {
throw new IllegalStateException("termStates are required when scores are needed");
}
this.needsScores = needsScores;
this.termStates = termStates;
this.similarity = searcher.getSimilarity(needsScores);

final CollectionStatistics collectionStats;
final TermStatistics termStats;
if (needsScores) {
collectionStats = searcher.collectionStatistics(term.field());
termStats = searcher.termStatistics(term, termStates);
} else {
// we do not need the actual stats, use fake stats with docFreq=maxDoc and ttf=-1
final int maxDoc = searcher.getIndexReader().maxDoc();
collectionStats = new CollectionStatistics(term.field(), maxDoc, -1, -1, -1);
termStats = new TermStatistics(term.bytes(), maxDoc, -1);
}
/**
* collectionStats 主要包含文档和字段的相关统计信息
* termStats： 名字term的统计信息，包括词频docFreq,totalTermFreq
* 调用相似度算法，执行计算weight,如果是TFIDFSimilarity相似度，即返回IDFStats对象，这块具体参考 org.apache.lucene.search.similarities.TFIDFSimilarity$IDFStats
*/
this.stats = similarity.computeWeight(collectionStats, termStats);
}
....

• 再来看看createNormalizedWeight里面后面的代码
• 1、float v = weight.getValueForNormalization();
• 2、float norm = getSimilarity().queryNorm(v);
• 3、weight.normalize(norm, 1.0f);

• 其中步1的计算就是 ：

• 其实这部主要是调用IDFStats.getValueForNormalization,
• private static class IDFStats extends SimWeight {
private final String field;
/** The idf and its explanation */
private final Explanation idf;
private float queryNorm;
private float boost;
private float queryWeight;
private float value;

public IDFStats(String field, Explanation idf) {
// TODO: Validate?
this.field = field;
this.idf = idf;
normalize(1f, 1f);
}
@Override
public float getValueForNormalization() {
//这里的queryWeight 其实在初始化时调用了normalize已经确定，queryWeight = （queryNorm * boost * idf.getValue()) * （queryNorm * boost * idf.getValue()) ;
//公式里其实还有一个求和计算，其实是在BooleanWeight递归计算的
return queryWeight * queryWeight; // sum of squared weights
}
@Override
public void normalize(float queryNorm, float boost) {
this.boost = boost;
this.queryNorm = queryNorm;
queryWeight = queryNorm * boost * idf.getValue();
value = queryWeight * idf.getValue(); // idf for document
}
}
//BooleanWeight.getValueForNormalization如下：
@Override
public float getValueForNormalization() throws IOException {
float sum = 0.0f;
int i = 0;
for (BooleanClause clause : query) {
// call sumOfSquaredWeights for all clauses in case of side effects
float s = weights.get(i).getValueForNormalization(); // sum sub weights
if (clause.isScoring()) {
// only add to sum for scoring clauses
sum += s;
}
i += 1;
}

return sum ;
}
• 第二部的计算就是：

• 通过这两步计算得出打分公式中的queryNorm。
• 这部在代码里其实是直接调用的IDFStats.normalize， 但要注意的是，这里面传的queryNorm的值其实是上一步的输出的值
• @Override
public float queryNorm(float sumOfSquaredWeights) {
return (float)(1.0 / Math.sqrt(sumOfSquaredWeights));
}
• 第三部计算：
• weight.normalize(norm, 1.0f);，首先调用的booleanWeigt.normalize, 里面是一个循环调用每个weight的value, 终内部是调用的相似度IDFStats.normalize方法，至此weightValue=queryNorm(q) * idf * idf * t.boost,至此我们已经分析了下面红色的那部分了：

• 这部计算首先是调用BooleanWeight循环调用weightlist，然后调用IDFStats.normalize
• @Override
public void normalize(float queryNorm, float boost) {
this.boost = boost;
this.queryNorm = queryNorm;
queryWeight = queryNorm * boost * idf.getValue();
value = queryWeight * idf.getValue(); // idf for document
}
• 红色的这部分主要是依靠weight对象树构造计算的，上面也是主要分析了weight对象树的计算过程，终也就是计算了一个query的分词后每个term的得分，都保持在weightvalue中。剩下就要把weight对象树对于每个文档doc进行合并，这就依靠SumScore对象树，这部分又是一大块，篇幅有限，待下次分析。