《倒排索引设计公开》PPT课件

《《倒排索引设计公开》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、倒排索引设计吴凯2012年6月2日信息源网页集合Query检索候选信息页面相关性排序结果关键词Query基本思路关键字匹配好文档至少要包含query中的所有词分词清华大学邮编分词清华大学邮编＋最初的思路索引查询、归并Term:清华大学倒排索引doc1doc2doc3…docNDoclistA…………DoclistB……索引归并候选集目标生存能够实现简单的倒排索引建立和检索发展针对高性能索引加载的设计针对高性能索引归并的设计针对索引压缩的设计生存篇第一步：建立词到文档&位置的映射关系…for(my$i=0;$i<$documentCount;++$i){my$docum

2、ent=&ReadDocument($i);my$words=&WordBreak($document);#分词my$wordCount=$#$words+1;for(my$j=0;$j<$wordCount;++$j){printf“%st%dt%d”,$words->[$j],$i,$j;#建立映射}}…生存篇第二步：按照词排序LC_ALL=Csort-k1,1-k2,2n-k3,3n相同词的映射记录被调整到邻近行相同词的记录，按照文档号从小到大排序相同词对应的相同文档的记录，按照出现位置从小到大排序Why?a35b31b32b35b50b51b63d34a35

3、b31b32b35b50b51b63d34生存篇第三步：归并a35b31b32b35b50b51b63d34a3:5b3:1,2,55:0,16:3d3:4生存篇第四步：加载索引&检索while(my$line=){chomp($line);nextunless(length($line)>0);my@fields=split(/t/,$line);my@docs;for(my$i=1;$i<=$#fields;++$i){my%doc;my@cols=split(/:/,$fields[$i]);my@pos=split(/,/,$cols[1]);$do

4、c{"docId"}=$cols[0];$doc{"pos"}=@pos;push(@docs,%doc);}$index{$fields[0]}=@docs;}my$info=$index{$term};加载检索生存篇第四步：加载索引&检索$VAR1={'a'=>[{'docId'=>'3','pos'=>['5']}],'b'=>[{'docId'=>'3','pos'=>['1','2','5']},{'docId'=>'5','pos'=>['0','1']},（续）{'docId'=>'6','pos'=>['3']}],'d'=>[{'docId'=>'3

5、','pos'=>['4']}]};生存篇回顾索引建立映射关系建立排序归并索引加载&检索Hash表二分查找发展篇核心问题性能！性能！性能！前面的简易版本10万文档，加载需要分钟级实际应用，单机百万到千万量级文档简易版本基本不可用发展篇如何更快加载？仅靠读文件，即能获取词到文档的映射关系如何做到？Keyvalue分离Key：词信息Value：词对应的文档和位置信息发展篇Key结构设计至少包含三类信息Term文本信息映射关系数据的位置映射关系数据的长度变长字符串定长整数定长整数Term信息是否也可定长?发展篇考虑一个数学问题1000万个随机数，取值均在[1,2^64]之间，均

6、匀分布，有多大的概率，所有的数字均互不相同？>99.9999%这说明了什么？发展篇对Term算md5，取64bit，key文件变为Term签名（8字节定长）映射关系数据的位置映射关系数据的长度Key文件变成了元素定长的数组加载时，直接读取检索时，二分查找文件加载问题解决发展篇如何快速归并问题简化两个已排序的整数链表A和B，长度分别为M和N，求其交集，如何做？发展篇最直接的思路直接归并while((iB[j])++j;else{printf(“%d”,A[i]);++i;++j;}}时间复

7、杂度O(M+N)发展篇如果M<