找到倒排表里两个关键字对应的doc交集

找出倒排表里两个关键字对应的doc交集
     下面这段文字摘自http://blog.csdn.net/ToBeAndNotToBe/archive/2010/09/25/5904467.aspx
介绍了lucene里边倒排表n个关键字所对应的doc的交集。

     可能大家都知道,lucene采用了传统搜索引擎中倒排表的数据结构.在搜索时，假设我们要查询"+(a:test)+(b:test1)"的话,首先要先查询得到a字段中包含 test关键字的倒排表,然后查询得到b字段中包含test1关键字的倒排表,然后对两个倒排表结构进行merge操作：计算两者间的交集就是我们的查询结果.

      当然这只是其中一个例子罢了.实际情况中,因为查询条件不同和复杂性,我们可能会遇到更 多对倒排表的操作:交集,并集,差集等.本文主要讲述lucene如何对交集进行处理:合并倒排表,生成SumScorer结果.

     第一步:过滤筛选:

     先对每个倒排表进行检查:每个倒排表都是一个DocIdSetIterator,如果其中一个倒排表中list为空,则说明交集肯定为空,不需要进行接下来的工作:

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;      }    }

时间复杂度为O(N)常量级别

      第二步:对倒排表数组进行排序:效果是倒排表数组按照每个倒排表第一个docid进行升级排序:

 Arrays.sort(scorers, new Comparator() {         // sort the array      public int compare(Object o1, Object o2) {        return ((Scorer) o1).docID() - ((Scorer) o2).docID();      }    });

     第三步:删减无用docid:因为是对多个倒排表求交集,所以需要先筛选去掉倒排表中那些比较小的docid:
 

if (doNext() == NO_MORE_DOCS) {      // The scorers did not agree on any document.      lastDoc = NO_MORE_DOCS;      return;    }/*doNext():该方法做的事情就是:比如倒排表数组中每个倒排表第一个docId分别为1,3,4,5,6,7;因为每个倒排表迭代器都是升序的,所以其实1,3,4,5,6在最后一个倒排表中没有,所以每个倒排表都应该从7开始,而不是1:*/  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;/*advance方法: if (lastDoc == NO_MORE_DOCS) {      return lastDoc;    } else if (scorers[(scorers.length - 1)].docID() < target) {      scorers[(scorers.length - 1)].advance(target);    }    return lastDoc = doNext();*/

我对上一段文字的看法是
1.既然是倒排表，关键字本身应该来自爬虫爬取网页所得到文字，所以一个关键字所对应文档是空，有些不合理；而且代码中也没有处理空文档的情况；如果是文档集合为空，可以去掉这个关键字；估计只有government出面要求某搜索引擎公司和谐掉某些敏感文档的快照的时候才会出现关键字对应文档为空的情况吧。。。总之这一点感觉是不太合理，当然也无大碍。
2.原来关键字对应的是文档id的集合，排序是按照id进行排列的，也就是对int型数据排列的。
3.百度的这道面试题问的是找出倒排表里两个关键字对应的doc交集，如果是针对两个关键字求其docid交集的话，应该还有更好的改进办法。比如在比较的时候，可以用二路归并的思路（a>b，a进入集合，a=b，舍掉b，a<b,b进入集合，++循环直到两组docid都被遍历过一遍，复杂度o(n)）。（如果求n个关键字的doc交集，n>2时需要编写一个求n个值最大值的小程序，这样也增加了百度所出题目的难度，求两个关键字的，感觉这道题还是比较仁慈的）

总之，觉得这道题考到了对倒排的理解，和算法。需要一定的知识面。

查看更多 下一篇