注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

IR——Boolean retrieval [AND查询]  

2010-02-04 15:08:54|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

         Introduction to IR第一章12页的AND查询,文档求交的算法如下:

INTERSECT(<t1, . . . , tn>)

1       terms ß SortByIncreasingFrequency(<t1, . . . , tn>)

2      result ß postings( f irst(terms))

3      terms ß rest(terms)

4      while terms != NIL and result != NIL

5      do result ß INTERSECT(result, postings( f irst(terms)))

6               terms ß rest(terms)

7      return result

         Lucene和这个算法有些不同,这里的代码来自于lucene 3.0。在于SortByIncreasingFrequency,下文会介绍lucene中的一个近似的做法。

从构造函数开始:

public ConjunctionScorer(Similarity similarity, Scorer... scorers)

       throws IOException {

    super(similarity);

    this.scorers = scorers;

    coord = similarity.coord(scorers.length, scorers.length);

 

    for (int i = 0; i < scorers.length; i++) {

       if (scorers[i].nextDoc() == NO_MORE_DOCS) {

           // If even one of the sub-scorers does not have any documents,

           // this scorer should not attempt to do any more work.

           lastDoc = NO_MORE_DOCS;

           return;

       }

    }

         Similaritycoord直接不管,和以前的版本相同,且和我要关注的无关。中间的for 循环中的注释写到,就算有子查询搜索不到文档,也不会再做任何事情了。

// Sort the array the first time...

// We don't need to sort the array in any future calls because we know

// it will already start off sorted (all scorers on same doc).

 

// note that this comparator is not consistent with equals!

Arrays.sort(scorers, new Comparator<Scorer>() { // sort the array

           public int compare(Scorer o1, Scorer o2) {

              return o1.docID() - o2.docID();

           }

       });

         注释写到:第一次将这个数组进行排序,我们不需要将来对这个数据进行进一步排序,因我为我们知道它开始就排序过了(因为所有的scorers开始于同一文 档)。

         Arrays.sort是将那些子查询所对应的文档列表,按它们所开始的文档id进行排序。

// NOTE: doNext() must be called before the re-sorting of the array

// later on.

// The reason is this: assume there are 5 scorers, whose first docs are

// 1, 2, 3, 5, 5 respectively. Sorting (above) leaves the array as is.

// Calling doNext() here advances all the first scorers to 5 (or a

// larger doc ID they all agree on).

// However, if we re-sort before doNext() is called, the order will be

// 5, 3, 2, 1, 5 and then doNext() will stop immediately, since the

// first scorer's docs equals the last one. So the invariant that

// after calling doNext() all scorers are on the same doc ID is broken.

if (doNext() == NO_MORE_DOCS) {

    // The scorers did not agree on any document.

    lastDoc = NO_MORE_DOCS;

    return;

}

         注意,要在后面排新排序被调用之前,调用doNext()doNext又在做什么:

private int doNext() throws IOException {

    int first = 0;

    int doc = scorers[scorers.length - 1].docID();

    Scorer firstScorer;

    while ((firstScorer = scorers[first]).docID() < doc) {

       doc = firstScorer.advance(doc);

       first = first == scorers.length - 1 ? 0 : first + 1;

    }

    return doc;

}

         doc赋了最后一个子查询的第一个文档id,也就是子查询s中最大的第一个文档,好拗口,用他所举的例子,有5个子查询,它们的第一个文档分别是12355。那么5就是最大的第一个文档。advance是返回等于或大于doc值的最小docIdWhile循环要到firstScorer.docIDdoc相等时才结束,简单的说就是要让开始的第一个文档id都相同。

// If first-time skip distance is any predictor of

// scorer sparseness, then we should always try to skip first on

// those scorers.

// Keep last scorer in it's last place (it will be the first

// to be skipped on), but reverse all of the others so that

// they will be skipped on in order of original high skip.

int end = scorers.length - 1;

int max = end >> 1;

for (int i = 0; i < max; i++) {

    Scorer tmp = scorers[i];

    int idx = end - i - 1;

    scorers[i] = scorers[idx];

    scorers[idx] = tmp;

}

         除了最后一个score,其它的都要反序,注释:如果第一次跳的距离是scorer稀疏的一种度量,那我们应该尝试先跳这些scorers。举个例子:比如子查询1123466,子查询25666205292。那么可以认为子查询2更稀疏,因为查询11开始,子查询256开始。而最后一个不变的原因是,下面的nextDoc是从最后一个scorer开始的。

public int nextDoc() throws IOException {

    if (lastDoc == NO_MORE_DOCS) {

       return lastDoc;

    } else if (lastDoc == -1) {

       return lastDoc = scorers[scorers.length - 1].docID();

    }

    scorers[(scorers.length - 1)].nextDoc();

    return lastDoc = doNext();

}

         求一个doc和在构造函数差不多,最后一个scorer的文档向前走一步。然后求lastDoc

 

 

 

  评论这张
 
阅读(975)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017