倒排索引设计公开课课件

倒排索引设计2012年6月2日Query检索相关性排序结果关键词\Query基本思路关键字匹配好文档至少要包含query中的所有词分词清华大学邮编分词清华大学邮编＋目标生存能够实现简单的倒排索引建立和检索发展针对高性能索引加载的设计针对高性能索引归并的设计针对索引压缩的设计生存篇第一步：建立词到文档&位置的映射关系…for(my$i=0;$i<$documentCount;++$i){my$document=&ReadDocument($i);my$words=&WordBreak($document);#分词my$wordCount=$#$words+1;for(my$j=0;$j<$wordCount;++$j){printf“%s\t%d\t%d\n”,$words->[$j],$i,$j;#建立映射}}…生存篇第二步：按照词排序LC_ALL=Csort-k1,1-k2,2n-k3,3n相同词的映射记录被调整到邻近行相同词的记录，按照文档号从小到大排序相同词对应的相同文档的记录，按照出现位置从小到大排序Why?a 3 5b 3 1b 3 2b 3 5b 5 0b 5 1b 6 3d 3 4a 3 5b 3 1b 3 2b 3 5b 5 0b 5 1b 6 3d 3 4生存篇第四步：加载索引&检索while(my$line=<STDIN>){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]);$doc{"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','pos'=>['4']}]};生存篇回顾索引建立映射关系建立排序归并索引加载&检索Hash表二分查找发展篇如何更快加载？仅靠读文件，即能获取词到文档的映射关系如何做到？Key

\value分离Key：词信息Value：词对应的文档和位置信息发展篇Key结构设计至少包含三类信息Term文本信息映射关系数据的位置映射关系数据的长度变长字符串定长整数定长整数Term信息是否也可定长?发展篇考虑一个数学问题1000万个随机数，取值均在[1,2^64]之间，均匀分布，有多大的概率，所有的数字均互不相同？

这说明了什么？发展篇如何快速归并问题简化两个已排序的整数链表A和B，长度分别为M和N，求其交集，如何做？发展篇最直接的思路直接归并while((i<M)&&(j<N)){if(A[i]<B[j])++i;elseif(A[i]>B[j])++j;else{printf(“%d\n”,A[i]);++i;++j;}

}时间复杂度O(M+N)发展篇如果M<<N二分查找谁在谁里面找？时间复杂度O(M*log(N))这对索引结构有什么样的要求？单文档信息定长Value中文档信息与Pos信息分离发展篇跳读A小，则A后移一位B小，则B移到下一个Block的头部如果B还是小，继续移动如果A小，则从上一个Block的头部开始线性遍历…………AB比较移到下一个Block的头部发展篇

发展篇如果N超级大，M也不小，但M还是比N小很多有没有可能进一步加快？实际的问题中，超高频词数目不多，但在query中出现次数不小值得为