加载中…
个人资料
不是天津饭
不是天津饭
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,049
  • 关注人气:14
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

一道来自百度的面试题--倒排索引的AND操作

(2009-12-14 14:29:04)
标签:

it

    倒排索引是以关键词作为索引项来索引文档的一种机制,如图中Brutus、Calpurnia、Caesar为关键词,2、4、8等等为文档ID。
一道来自百度的面试题--倒排索引的AND操作

    现在有一个查询:Brutus AND Calpurnia AND Caesar。这个查询实际上就是要找出Brutus(以下简称B)、Calpurnia(以下简称C1)和Caesar(C2)的索引文档中的相同项。假设B、C1、C2的长度分别为m、n、p。
    比较容易想到的是用归并排序的思想来解决这个问题。即:对3个线性表进行归并排序并对相同项计数,计数为3的项即为结果,这个方法时间复杂度为O(m+n+p),就这个例子我们需要比较7+8+2=17次。
    百度的面试题经常会问到一个问题,有没有更快的方法?答案是肯定的。
    这个题目的目的只是找到计数为3的项,而不是排序结果,所以实际上,对2个表经过一次归并之后,计数小于2的项可以舍去了,这样剩下的结果再进行归并,表长度会下降,比较次数自然也就少了。自然而然的,我们会想到先把两个能生成更短结果的表进行比较。
    怎样的两个表AND生成的表长度会比较短?严格判断这个问题很难,但是我们可以进行一个很简单的假设:两个长度最短的表AND结果会比较短。于是这里我们可以先将B和C1进行AND,得到结果:16。然后与C1进行AND,得到空集。需要比较4+2+7=13次。
    为什么仍然需要比较这么多次呢?因为16和C1比较时,仍然需要找到21(>16)时才能知道:不需要再比较了。那么我们可不可以再缩短这个比较次数呢?答案仍是肯定的。
    如下图,我们可以每隔k项建立一个skip项,保留下一个skip项的值。在比较A、B表时,如果A表当前项大于B表当前项,就可以比较A表当前项是否大于B表下一个skip项,如果大于,则B表直接跳到下一个skip项;如果小于,则依然逐个对B表的项进行比较。
一道来自百度的面试题--倒排索引的AND操作
    还是说开始的例子,当C1表与16比较时,假设1保留了skip值,为8,则可以直接跳过3项,与8进行比较,从而减少次数到4+2+4=10次。
    如何建立skip项是个问题:太密集则skip成功次数多,但是跳过的数量少,建立skip复杂度较大,比较次数变多;太稀疏则skip项跨度太大,不容易skip成功,反而徒增比较skip项次数。有人提出用sqrt(length)作为skip长度。而我认为,可以基于项的密度来做:项密度较大,如 1 2 3 4 5 6 ..100的表,可以取50个一跳;相应的,如果1 10 20 30 40 50 60 70 80 90的表,可以取7、8个一跳。当然这样因为skip长度是不等的,就需要额外开辟一个空间来存储skip项的index。但是比较次数是不会增加的,所以仍然可行,当然在构建skip项的时候会麻烦一点。但是搜索引擎更加关心如何使查询的响应时间缩短,对于文档的预处理工作的时间要求则会低一点,所以这样做也是可以的。
    说完了AND,也说说OR和NOT。OR自然是线性表合并,用归并排序可以解决,可以考虑将其中AND部分排序到前面。
    NOT比较麻烦。假设S为全集,对单个表A做NOT操作,则相当于S-A。但是显然不会有人只用一个NOT A进行查询,一般的查询都是X AND (NOT B)形式,实际上也就是X-B。如何求X-B?依然可以用X AND B的方法,只不过找两个表的相同项变成找两个表的不同项了。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有