Bitmap算法简介

发表于 2018-02-01 更新于 2023-03-22

本文主要介绍Bitmap算法，包括其思路、实现与应用。

引入

问题描述

给定一台32位的2GB内存主机与一个含有40亿个整数的文件，整数满足以下三个条件：

均为unsigned int类型
不重复
乱序

现给出一个整数，如何快速判断此数是否在文件中？

传统解法

首先，最容易想到的解法应该是遍历法。理论上它的时间复杂度为$o(N)$，但由于这40亿个整数存在于磁盘中，因此实际上要耗费相当多的时间。

其次，在算法竞赛中也经常用到一种方法，申请一个大数组char a[]，将文件中出现的数字置为1，没有出现的置为0。这种方法又叫直接寻址表法。但40亿个unsigned int所占空间约为4G，远远超出了机器的内存。

注意到，在上面的char a[]中，每个整数所占空间为一个字节（即8位），但其实我们用一位二进制数字就可以。也就是说，上述方法还可以进一步压缩空间，压缩后占用空间仅为原来的$\frac{1}{8}$。这就是Bitmap算法的基本思想：使用一个字节表示布尔值，避免空间的浪费。

Bitmap算法

原理

直接寻址表法用一个char类型（8个二进制位）的变量来表示一个布尔值，但其实一个布尔值使用一个二进制位就可以表示。将直接寻址表法的空间进行压缩就得到了BitMap算法。例如要把整数11映射到数组char a[]的某一位置，11/8=1，11%8=3，因此11对应的是a[1]的第三个位，如图。

整数11映射示意图

实现

C++、Java等语言中，有bitset类库可直接实现。在C语言中，没有直接操作位的数据结构，我们只能用位运算来操作位。下面主要针对C语言进行分析。

首先我们定义一个数组char a[]，用于保存位。设N为需要保存的最大数，因为一个char类型含有8个二进制位，可以表示8个数，所以数组大小为N/8。

1 2	#define N 4000000000 char a[1 + N/8];

之后我们使用位运算，对位进行增、删、查等常用操作。从BitMap数组里增加一个数，代码如下。

void BitMap(int n){
    int row = n >> 3;
    int pos = n & 0x7;
    a[row] = a[row] | 1<<pos;
}

首先，row表示数字n对应数组a的哪一个元素，n >> 3是n右移3位，相当于n/8。pos表示数字n对应数组a元素的哪一位，n & 0x7是取n的二进制后三位，相当于n%8。之后将对应的位置1，使用或操作可以只修改pos位，而不影响其它位。

判断一个数是否存储在BitMap数组中，代码如下。

int isExist(int n){
    int row = n >> 3;
    int posNum = 1 << (n & 0x7);
    return (a[row] & posNum) = 0 ? 0 : 1;
}

row表示数字n对应数组a的哪一个元素，a[row] & posNum为0，则说明对应位是0，这个数没有存储在BitMap数组中。否则说明BitMap数组中存有这个数字。

从一个BitMap数组里删除一个数，代码如下。

void DelFromBitMap(int n){
    int row = n >> 3;
    int posNum = 1 << (n & 0x7);
    a[row] = a[row] & ((1<<posNum) ^ 0x7);
}

与上同理，^是异或运算符，(1<<posNum) ^ 0x7得到的是pos位为0、其它位为1的数，a[row]与它做与运算，相当于将pos位置0，即删除了这个数。

算法应用

基本应用

显然，Bitmap算法非常适合于对大量、不重复、无符号整数进行查找与排序。此外，它还可以用于计算字符串的全组合枚举。例如，找到abcdef的全组合枚举，每个字母均可出现或不出现，就可以构造一个从字符串到二进制的映射关系，通过枚举二进制来进行全排序。

对于有重复数据的数组，可以进行一些改造。例如，使用两个位存储一个数字，若未出现，记为00；若出现一次，记为01；若出现两次，记为10；11未定义。

数据表操作

在一个用户画像系统中，实现用户信息标签化。如小明的用户信息标签可以是：程序员、90后、宅。现需统计所有90后的程序员。传统的实现方法可能为：将这些信息存在一个数据表里，数据表字段是用户标签，每一个记录对应一个用户。使用一条求交集的SQL语句Select count（distinct Name） as 用户数 from table whare age = ’90后’ and Occupation = ‘程序员’;但标签逐渐增多，会使维护越来越困难；且SQL语句过长，运行缓慢，难于阅读。

这里可以使用BitMap算法实现，思路是将用户对应多个标签转换为标签对应多个用户。首先，建立用户和用户id的映射；之后，每一个标签存储包含此标签的所有用户ID，每一个标签都是一个独立的Bitmap。如图。

用户标签示意图

若要查询使用苹果手机的程序员用户，对Occupation的BitMap表以及和phone的BitMap表进行与运算就可以得出，运算效率很高。

这种情景下使用BitMap的优是点占用字节数少，大多操作为位运算，效率高；缺点是不适用于数据分散的情况，且进行非运算比较困难。如得到非90后的用户，只能通过计算全部用户的BitMap解决。

布隆过滤器

布隆过滤器（Bloom Filter）是一个判断元素是否存在集合中的快速概率算法。

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为$O(n),O(\log n),O(n/k)$。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（$O(k)$）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。另外，一般情况下不能从布隆过滤器中删除元素。

参考文献

维基百科 - 布隆过滤器