文档章节

BitMap 的基本原理和实现

大数据之路
 大数据之路
发布于 2012/09/04 09:20
字数 1636
阅读 406
收藏 1

前言

文章是自己写了后先发到了公众号里,再转到了内部的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 来解决。

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

Refer:

[0] 拜托,面试官别问我「布隆过滤器」了(修订补充版)

https://bit.ly/2YHlKV4

[1] BitMap 的基本原理和实现

https://cloud.tencent.com/community/article/813907

[2] No.17【大数据算法】Bloom Filter 的数学背景

http://bit.ly/2gx6y84

[3] No.15【大数据算法】Bloom Filter 的基本原理和实现

http://bit.ly/2hYN5gT

[4] No.19 【大数据算法】Counting Bloom Filter 的原理和实现

http://bit.ly/2y02fNu

[5] 大数据计数原理1+0=1这你都不会算(八)No.60

http://bit.ly/2l7t64i

[6] 大数据分析常用去重算法分析『Bitmap 篇』

http://bit.ly/2ZLY2HR

本文转载自:https://cloud.tencent.com/community/article/813907

大数据之路
粉丝 1605
博文 514
码字总数 333882
作品 0
武汉
架构师
私信 提问
No.14 【大数据算法】BitMap的原理和实现

0x00 前言 本篇是大数据算法系列 第一篇《BitMap的原理和实现》,BitMap 的思想的和原理是很多算法的基础,因此我们以BitMap开篇。 既然是说大数据算法,我们先尝试给大数据算法一个定义,或...

dantezhao
2017/10/09
0
0
bitset bitmap 海量数据处理

bitmap:是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 适用范围...

您这磨人的小妖精
2015/09/05
841
0
Photoshop色阶、曲线命令图解和编程实现(附源码)

Photoshop功能强大,使用灵活。初级使用者通常有几个禁区: 1.图像->调整 菜单(色阶,曲线等命令都在此菜单中) 2.蒙版与矢量工具(如钢笔工具) 3.通道与色彩模式 4.图层混合模式 要用好这...

云栖希望。
2017/12/04
0
0
Android 圆角、圆形 ImageView 实现

一、 特点 基于AppCompatImageView扩展 支持圆角、圆形显示 可绘制边框,圆形时可绘制内外两层边框 支持边框不覆盖图片 可绘制遮罩 ...... 二、基本原理 我们要实现的图片控件继承自,它是的...

Othershe
2018/06/25
0
0
No. 15【大数据算法】Bloom Filter 的原理和实现

0x00 前言 Bloom Filter 是由 Burton H. Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。 Bloom Filter 最初的论文发表...

dantezhao
2017/10/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js中将字符串转换成json的三种方式

使用ajax的开发项目过程中,经常需要将json格式的字符串返回到前端,前端解析成js对象(JSON )。 ECMA-262(E3) 中没有将JSON概念写到标准中,还好在 ECMA-262(E5) 中JSON的概念被正式引入了...

物种起源-达尔文
2分钟前
0
0
centos7下面python3.7安装

我这里使用的是CentOS7,默认系统自带python2.7的版本,这个版本被系统很多程序所依赖,所以不建议删除,如果使用最新的Python3那么我们知道编译安装源码包和系统默认包之间是没有任何影响的...

chenhongjiang
8分钟前
0
0
带你入门SpringCloud统一配置 | SpringCloud Config

前言 在微服务中众多服务的配置必然会出现相同的配置,如果配置发生变化需要修改,一个个去修改然后重启项目的方案是绝对不可取的。而 SpringCloud Config 就是一个可以帮助你实现统一配置选...

桌前明月
8分钟前
0
0
9.21 日常记录

先说说最近的状态: 一句话,很不好。缺失了目标感,做什么事都是浑浑噩噩的。 每天都是想着轻松的活路去做复习,没有看书,根本没有去思考如何让自己变得更好。 回想起年初的约定,也是一个...

Garphy
18分钟前
0
0
借助Python 函数进行模块化代码

你是否对函数、类、方法、库和模块等花哨的编程术语感到困惑?你是否在与变量作用域斗争?无论你是自学成才的还是经过正式培训的程序员,代码的模块化都会令人困惑。但是类和库鼓励模块化代码...

问题终结者
21分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部