孤惯|微软 Bing 搜索核心技术 BitFunnel 原理揭秘( 二 )
这样的代价无疑是非常高昂的 ， 因为现在文章的数量和长度乘积无疑是一个天文数字 。 一个非常巧妙的办法就是将这个矩阵反转过来 ， 行列倒置 ， 那么我们的存储由N＊P行列矩阵就变成了P＊N ， 很显然 ， P远远小于N 。 那么 ， 我们的查询文档Query对应的只需要去匹配其中位为1的对应的文档的行向量即可 ， 过程如下：
从上图流程可以看出 ， 对应的只需要查询对应为1的位向量行数的文章的情况就可以了 ， 假设真实中查询的文档Query的为1位数是W位 ， 在现实查询中 ， W往往是少数几个单词去查询 ， W远远小于P ， 对应列进行并运算 ， 结果为1则该篇位置可能匹配 ， 这样查询速度就大大提升 。 但是 ， 还有一个问题就是现实中 N 的数量也非常庞大 。
那么这点如何处理呢？这就引进了今天要讲的重点算法：BitFunnel 。
BitFunnel发明等级行
等级行是原始行的简单压缩版本 ， 能够提高过滤速度 ， 但同时也带来了更高的错误率 ， 让我们看看等级行是怎么运行的 。 我们将原始行称为0-等级行 ， 假设原始行是32位长度 ， 那么1-等级行就是由0－等级行对等截成两半进行或运算获得 ， 那么长度就降低了一半 ， 更高等级行依此进行计算获得 ， 如下图举例所示：
那么现在我们怎么使用我们获取的等级行呢？假设我们有3行32列需要匹配处理 ， 那么我们可以考虑将第一行压缩成2－等级行 ， 第二行压缩成1－等级行 ， 第三行保持不变 。 如果我们没有这样做 ， 我们需要将3*32＝96位全部放进内存进行查询处理才可以完成 。 而现在 ， （8+16+32）＝56位 ， 详细如下图所示：
那么查询的时候 ， 我们先将得出第一行和第二行的并运算结果 ， 仅两列需要去与第三行在进行处理 ， 然后平移到第三行另一边处理 ， 再将第一行移动到第二行的另外一边 ， 这时候也是两列均为1出现 ， 然后与第三行处理 ， 再转移回去处理最后一次即可得出结果 ， 四次处理计算流程如下：
以上这样的处理我们可以大量地利用中间结果加快计算 。
频率布隆过滤器
传统的布隆过滤器需要花费超长度的位向量才能做到满足较低的错误率 ， 而BitFunnel则使用频率布隆过滤器来降低内存总量 。 什么是频率布隆过滤器？当我们在布隆过滤器中查询仅仅查询一个项目时 ， 假设整个布隆过滤器为1的密度为10% ， 那么当我们只使用一个哈稀函数（假设哈稀函数是完全随机哈稀函数） ， 那么对应的碰撞率为10％ ， 那么随着我们哈稀函数种类的增加 ， 我们可以计算出错误率,d为布隆过滤器的概率密度 ， 但这里我们可以进一步提出新的概念信噪比：
推荐阅读
- 忘川彼岸|启迪设计中标微软（中国）苏州科技园区二期办公楼项目设计总包
- 孤惯|性价比最高的电脑音箱有哪些？20款50-500元电脑音箱推荐
- 游戏机|最佳游戏平台评选！任天堂、索尼和微软全都败给了PC电脑
- 微软|硬盘满了别发愁，Windows 10小工具帮你轻松释放存储空间
- 轻拔琴弦|非常强大，硬核！微软云K8S学习指南免费领取了
- 那年初夏|一更新就出事的win10！SSD硬盘被坑寿命受损，微软已正视
- 西红柿小生|到底值不值？微软轻薄超极本放到现在，还有吸引力吗？
- |5分钟读懂微软新技术：未来游戏如何消灭读条
- 孤惯|通用人工智能啥时候能实现？这是我的最新预测
- 韭菜花音乐|翻新机6.4折起，微软商城启动开学季活动：Surface等新品享9折