BitMap 的基本原理和实现

前言

文章是自己写了后先发到了公众号里,再转到了内部的KM。算是一个系列的学习笔记,一篇篇来。

本篇是大数据算法系列 第一篇《BitMap的原理和实现》,BitMap 的思想的和原理是很多算法的基础,因此我们以BitMap开篇。

既然是说大数据算法,我们先尝试给大数据算法一个定义,或者说是限定一下这个系列的范围。

大数据算法:在给定的资源约束下,以大数据为输入,在给定时间约束内可以计算出给定问题加过的算法。

大数据算法会有传统的算法有不一样的地方:

  1. 资源有约束
  2. 时间有约束
  3. 大数据作为输入
  4. 不一定是精确算法

前三点可以看作是对算法的要求,第四点可以看作是在大数据场景下算法可以做出的让步。比如说在10亿的数据中求 count distinct 操作,完全精确的算法会十分占用空间资源,而且也很难在快速计算出结果。如果这时候允许一定的误差,就可以在极短的时间使用少量的内容算出结果,比如基数估计算法中的Hyperloglog。

本系列会包括 BitMap、Roaring BitMap、Bloom Filter、Counting Bloom Filter、Linear Counting、Loglog Counting、HyperLogLog Counting 等算法。我会把这些算法一个个过一遍,看论文、写代码、整理学习笔记。

对于技术人员来讲,文章应该做到 图文码并茂,因此我会尽量做到每篇文章都有原理说明和示例代码的实现,原理说明会通过配图的方式来理解,代码的话会有一个比较简单的demo。

一、原理

基本原理

BitMap 的基本原理就是用一个 bit 来标记某个元素对应的 Value,而 Key 即是该元素。由于采用一 个bit 来存储一个数据,因此可以大大的节省空间。

我们通过一个具体的例子来说明 BitMap 的原理,假设我们要对 0-31 内的 3 个元素 (10, 17,28) 排序,那么我们就可以采用 BitMap 方法(假设这些元素没有重复)。

如下图,要表示 32 个数,我们就只需要 32 个 bit(4Bytes),首先我们开辟 4Byte 的空间,将这些空间的所有 bit 位都置为 0。

然后,我们要添加(10, 17,28) 这三个数到 BitMap 中,需要的操作就是在相应的位置上将0置为1即可。如下图,比如现在要插入 10 这个元素,只需要将蓝色的那一位变为1即可。

将这些数据插入后,假设我们想对数据进行排序或者检索数据是否存在,就可以依次遍历这个数据结构,碰到位为 1 的情况,就当这个数据存在。

字符串映射

BitMap 也可以用来表述字符串类型的数据,但是需要有一层Hash映射,如下图,通过一层映射关系,可以表述字符串是否存在。

当然这种方式会有数据碰撞的问题,但可以通过 Bloom Filter 做一些优化。

二、实现

懂原理之后,还是要写代码来加深一下理解,这里用 Python 实现一个最基本的版本。

代码用到了 bitarry 库来直接操作 bit 数组;用 hashlib 来将字符串映射到数字,以便插入 BitMap。

代码很简单,看懂上面的原理的话,很容易就看懂了代码。

三、使用

BitMap 的使用场景很广泛,比如说 Oracle、Redis 中都有用到 BitMap。当然更多的系统会有比 BitMap 稍微复杂一些的算法,比如 Bloom Filter、Counting Bloom Filter,这些会在后面逐一展开。

下面举一个在算法中用到 BitMap 来解决问题的例子。

已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

在这里就不再做和其它算法的对比,直接说一下 BitMap 的思路。

8 位的整数,相当于是范围在(0,99999999),也就是说 99999999 个 bit,也就是 12M 左右的内存,比起用类似 HashMap 的方式的话能节省很大的空间。 可以理解为从0 到 99999999 的数字,每个数字对应一个 Bit位,所以只需要 12M 左右的内存表示了所有的 8 位数的电话。

查询的时候就很简单了,直接统计有多少位是 1 就可以了。

四、总结

BitMap 的思想在面试的时候还是可以用来解决不少问题的,然后在很多系统中也都会用到,算是一种不错的解决问题的思路。

但是 BitMap 也有一些局限,因此会有其它一些基于 BitMap 的算法出现来解决这些问题。

  • 数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题,那就可以考虑用 Bloom Filter 来解决,Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
  • 数据稀疏。又比如要存入(10,8887983,93452134)这三个数据,我们需要建立一个 99999999 长度的 BitMap ,但是实际上只存了3个数据,这时候就有很大的空间浪费,碰到这种问题的话,可以通过引入 Roaring BitMap 来解决。

算法比较成熟,因此参考的东西也挺多,就不再列参考了。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python中文社区

用Python分析苹果公司股价数据

专栏地址:https://zhuanlan.zhihu.com/c_147297848

832
来自专栏聊聊技术

原 初学数模-MATLAB Quick S

4329
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

3576
来自专栏Java成神之路

文本相似度——自己实现文本相似度算法(余弦定理)

最近由于工作项目,需要判断两个txt文本是否相似,于是开始在网上找资料研究,因为在程序中会把文本转换成String再做比较,所以最开始找到了这篇关于 距离编辑算...

843
来自专栏互联网杂技

A*算法详解

概述 虽然掌握了 A* 算法的人认为它容易,但是对于初学者来说, A* 算法还是很复杂的。 搜索区域(The Search Area) 我们假设某人要从 A 点...

2759
来自专栏小樱的经验随笔

基于连通性状态压缩的动态规划问题

基于连通性状态压缩的动态规划问题 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题.在状态压缩的基础上,有一类问题的状态中...

2958
来自专栏编程

数控代码归纳

数控加工程序编制方法有手工(人工)编程和自动编程之分。手工编程现在大部分工厂已经不在采用,由于容易出错及效率低下。因此为了提高生产自动化程度,缩短编程时间和降低...

1845
来自专栏吉浦迅科技

DAY15:阅读CUDA C runtime之纹理内存

1083
来自专栏前端架构

图是什么玩意, 怎么表示它?

谈到数据结构,我觉得创造一种数据结构的初衷,应该是通过该数据结构完成对现实问题的建模和处理,最后当然能用数学或者计算机对这些问题进行处理和分析。 其中一种建模的...

422
来自专栏PPV课数据科学社区

【工具】SAS 常用函数汇总

? 一、数学函数 ABS(x) 求x的绝对值。 MAX(x1,x2,…,xn) 求所有自变量中的最大一个。 MIN(x1,x2,…,xn) 求所有自变量...

2263

扫码关注云+社区