孤惯|微软 Bing 搜索核心技术 BitFunnel 原理揭秘导语从90年代中期开始

导语
从90年代中期开始，人们普遍认识，对于内容索引来说，文件签名技术比反向链接效果更差。最近几年必应搜索引擎开发与部署了一套基于位分割的标签索引。这种索引（也称BitFunnel）替代了之前的基于反向索引的生产系统。这项转移背后驱动的因素是反向链接需要运转存储代价。本篇内容将讲述这项算法上的创新发明，改变传统上在云计算框架上被认为无法使用的技术。 BitFunnel算法直接解决四项基础位分割块签名的限制。同时，算法的映射进入集群提供了避免和其他签名联系的代价。这里会先展示这些创新产生了比传统位分割签名的更显著的效率提升，然后将会进行BitFunnel与分块化Elias-Fano索引,MG4J,和Lucene等的对比。本文根据论文《BitFunnel: Revisiting Signatures for Search》和Bing团队实践分享视频，对BitFunnel原理进行分析解读。
问题背景
假设我们一篇非常短的文档：内容仅仅“big brown dog”这三个单词，我们可以用固定长度的位向量对这组单词进行编码，也称固定长度的位向量为文档签名或者布隆过滤器。简单样例这里采取了十六位长度的位向量来进行操作，当然，在Bing系统上不会用这么短的位向量，往往使用五千个以上的来进行表示。一开始，位向量全都是空的，因为还没有进行数据的加载操作。
布隆过滤器初始化会设置哈稀函数的种数，哈稀函数是为了让文档单词对应到位向量的固定位置上。这里我使用了三种不同的哈稀函数来映射。映射结果如下：
从上图可知，每个单词都对应着位向量上面的三个位置上置1 ，然后我们得到了这份简易文档的文档签名，假如我们要搜索“cat”单词在不在这份文档里面，我们只需要查询“cat”单词经过哈稀函数映射出来的三个位置上是否都为1就可以进行判定了，很明显，有一个不为1 ，所以“cat”单词并不在这份文档里面。
当我们搜索"big“单词时，我们会发现三个位置均置为1 ，那么我们可以判定“big”是这份文档的可能成员。如下图所示：
细心的你肯定注意到这里用了可能两个字，为什么是可能成员呢？下图是我们搜索的是“house”单词的结果：
我们会发现这个单词的所有映射位置也都是1 ，但实际上我们知道文档里并没有“house”单词，这个存在的原因是因为有哈稀函数映射碰撞的存在，导致其他的位置也有相对应的1在文档里面补充了没有为1的情况，这也是我们为什么要用多种哈稀映射函数的原因，能够降低这种错误率。
基于这样的结构我们，假设我们存储有十六篇文档：A－P ，依次建立了签名，那么有搜索需求：Query文档（包含多个单词）进来，通过下列查询就可以得到可能匹配文档：
这样的思路无疑是非常直观简单且容易实现的，但是在网络中存储的那些网页，基本需要几千位长度的位向量去表示，如果我们每一篇文档都这样去查询匹配，假设我们有N篇文章，用了P个位的文档签名标记，我们的计算机CPU每次处理的位数为64位，那么查询一篇文章需要花费的代价就是 N＊（P/64）单位时间。