倒排索引优化 - 跳表求交集 空间换时间-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

倒排索引优化 - 跳表求交集 空间换时间

简介:

lucene中用的是ConjunctionScorer ,大致过程是每条倒排链不断的推进到小于等于当前最大节点的位置。当然实现细节还是很丰富的,作者很细心的把过程都列出来了,建议顺着读一边。这里摘抄部分:

首先把倒排链按第一个next排序:

    itdadao

查看0~7的倒排链的第一个和最后一个是否相同,不同就开始找;取最后一个倒排的第一个元素8作为终点, 第一个链表开始找8

itdadao

第0个链表 跳过1到了10,那么8也不用找了都去找10就行了

itdadao

第1根链表找到了11,那么10也不用找了,找11,之后都这么做

itdadao......itdadaoitdadao

之后遇到11,本次交集操作找到一个11,

itdadao

  后续的计算也是同理,当然整个代码实现会比较复杂和讨巧。基本思路就是每条倒排链能根据当前文档迅速跳过不符合的docid,由于倒排链可以用skiplist查询,因此即使很长的倒排链,如果交集的数量很少,整个求解过程可以很快跳过不需要比较的节点。

 

摘自:http://www.itdadao.com/articles/c15a1147107p0.html










本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6589849.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: