倒排索引设计公开课件

1、倒排索引设计倒排索引设计2012年6月2日倒排索引设计公开PPT课件信息源信息源网页集合网页集合Query检索检索候选信息候选信息页面页面相关性排序相关性排序结果结果关键词关键词Query倒排索引设计公开PPT课件基本思路 关键字匹配关键字匹配 好文档至少要包含query中的所有词 分词分词清华大学邮编清华大学邮编分词分词清华大学清华大学邮编邮编倒排索引设计公开PPT课件最初的思路 索引查询、归并索引查询、归并Term:清华大学清华大学倒排倒排索引索引doc1doc2doc3docNDoc list ADoc list B索引归并候选集候选集倒排索引设计公开PPT课件目标 生存 能够实现简单的

2、倒排索引建立和检索 发展 针对高性能索引加载的设计 针对高性能索引归并的设计 针对索引压缩的设计倒排索引设计公开PPT课件生存篇 第一步：建立词到文档&位置的映射关系for (my $i = 0; $i $documentCount; +$i) my $document = &ReadDocument($i); my $words = &WordBreak($document); #分词分词 my $wordCount = $#$words + 1; for (my $j = 0; $j $j, $i, $j; #建立映射建立映射 倒排索引设计公开PPT课件生存篇 第二

3、步：按照词排序 LC_ALL=C sort -k1,1 -k2,2n -k3,3n 相同词的映射记录被调整到邻近行 相同词的记录，按照文档号从小到大排序 相同词对应的相同文档的记录，按照出现位置从小到大排序Why?a35b31b32b35b50b51b63d34a35b31b32b35b50b51b63d34倒排索引设计公开PPT课件生存篇 第三步：归并 a35b31b32b35b50b51b63d34a3:5b3:1,2,55:0,16:3d3:4倒排索引设计公开PPT课件生存篇 第四步：加载索引&检索 while (my $line = ) chomp($line); next u

4、nless (length($line) 0); my fields = split(/t/, $line); my docs; for (my $i = 1; $i 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 ;倒排索引设计公开PPT课件生存篇 回顾 索引建立 映射关系建立 排序 归并 索引加载&检索 Hash表 二分查找倒排索引设计公开PPT课件发展篇 核心问题 性能！性能！性能！

5、前面的简易版本 10万文档，加载需要分钟级 实际应用，单机百万到千万量级文档 简易版本基本不可用倒排索引设计公开PPT课件发展篇 如何更快加载？ 仅靠读文件，即能获取词到文档的映射关系 如何做到？ Key value 分离 Key：词信息 Value：词对应的文档和位置信息倒排索引设计公开PPT课件发展篇 Key结构设计 至少包含三类信息 Term文本信息 映射关系数据的位置 映射关系数据的长度变长字符串变长字符串定长整数定长整数定长整数定长整数Term信息是否也可定长?倒排索引设计公开PPT课件发展篇 考虑一个数学问题 1000万个随机数，取值均在1, 264之间，均匀分布，有多大的概率，所

6、有的数字均互不相同？这说明了什么？倒排索引设计公开PPT课件发展篇 对Term算md5，取64bit，key文件变为 Term签名（8字节定长） 映射关系数据的位置 映射关系数据的长度 Key文件变成了元素定长的数组 加载时，直接读取 检索时，二分查找文件加载问题解决倒排索引设计公开PPT课件发展篇 如何快速归并 问题简化 两个已排序的整数链表A和B，长度分别为M和N，求其交集，如何做？倒排索引设计公开PPT课件发展篇 最直接的思路 直接归并while (i M) & (j N) if (Ai Bj) +j; else printf(“%dn”, Ai); +i; +j; 时间复杂度O

7、(M+N)倒排索引设计公开PPT课件发展篇 如果M N 二分查找 谁在谁里面找？ 时间复杂度 O(M * log(N) 这对索引结构有什么样的要求？ 单文档信息定长 Value中文档信息与Pos信息分离倒排索引设计公开PPT课件发展篇 如果介于前两种情况之间，M与N是10倍左右的差别，有没有更快的方法？AB比较每C个单元划分为一个Block倒排索引设计公开PPT课件发展篇 跳读 A小，则A后移一位 B小，则B移到下一个Block的头部 如果B还是小，继续移动 如果A小，则从上一个Block的头部开始线性遍历AB比较移到下一个Block的头部倒排索引设计公开PPT课件发展篇倒排索引设计公开PPT

8、课件发展篇 如果N超级大，M也不小，但M还是比N小很多 有没有可能进一步加快？ 实际的问题中，超高频词数目不多，但在query中出现次数不小 值得为它们的性能来加上额外的设计和开销倒排索引设计公开PPT课件发展篇 Bitmap索引 仅对于超高频词 空间开销，每个词N/8字节，按N为2000万算，即2.5M，存top 100，也才250M 时间复杂度，O(M)0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 01 0 1 0 0 1 1 0倒排索引设计公开PPT课件发展篇 总结 加速加载 KeyValue分离 定长签名 加速归并 M与N接近，线性归并 M N，10倍左右差别，跳读 M N，二分 M