bitmap算法简介

今天看到海量数据处理算法————bitmap（又称为bitset, 或者bit array）， 有意思的算法。

C++ 有一个头文件是<bitset>。 

bitmap的思想就是数据压缩。 用一个二进制bit(0或者1)去标记某个元素对应的value， 这就是bit + map啊。

由于使用bit单位存储数据， 所以可大大节省内存空间。下面举一个使用bitmap 的例子。

我们要对0-7内的五个元素进行排序， 假设这5个元素为（4， 7， 2， 5， 3）。 假设元素没有重复的。 要表示8个数， 我们需要8个bit。也就是1byte.

下面我们只需要开辟1byte的空间， 对这个1byte的所有的bit都初始化为0。

如下： 0000 0000

我们可以规定， 有如下的map。 

0000 0000 ---> 0

0000 0010 ---> 1

0000 0100 ---> 2

0000 1000 ---> 3

0001 0000 ---> 4

0010 0000 ---> 5

0100 0000 ---> 6

1000 0000 ---> 7

以上的map是我们默认的， 不需要去另外开辟空间存这个映射表格(不过我们也可以吧index设为从1开始， 就有如下映射：

0000 0001 ----> 1

0000 0010 ----> 2

.............................

1000 0000 -------> 8

)

试着想想， 如果我们直接存放， 需要 8 x sizeof(int) = 32byte。

但是由于我们使用了bitmap， 我们只需要8 x 1 bit = 1byte既可以。 好节省空间啊。 节省32倍。 太牛了。

下面我们就应用这一个byte存储着5个元素， 得到的存储信息如下：

首先， 输入第一个元素4， 对应如下：

0001 000.

第二个元素输入是7， 所以将第8位设置为1, 变成如下：

1001 0000

最终， 如下：

1011 1100代表着所有的元素4， 7， 2， 5， 3。

然后我们遍历一遍bit区域， 将改为编号是1的编号（索引）输出， 就是（2， 3， 4， 5， 7）。

#include <bitset>
#include <iostream>

using namespace std;

int main() {
    int arr[5] = {4, 7, 2, 5, 3};
    bitset<8> mybit; // default constructor all to 0

    for(int i = 0; i < 5; ++i) {
        mybit.set(arr[i]); // set bit arr[i]， 即置1
    }

    cout << mybit << endl;

    cout << "sorting using bitmap: ";
    for(int i = 0; i < 8; ++i) {
        if(mybit[i]) {
            cout << i << " ";
        }
    }
}

运行结果如下：

这样， 我们就在O（n）的线性时间内完成了排序操作。 太好了， 就想counting sort的性能。 

注意， 使用bitmap 的前提是出现的元素不重复的， 这是这个算法的缺点。

现在在举一个bitmap算法例子。

使用bitmap 实现8位（表示10进制位）电话号码的存储， 插入， 查找， 删除等操作。

分析：    首先， 我们知道， 8位电话号码总共有0----999999999个号码。 我们使用bitmap的办法， 每一个bit（二进制位）代表一个8个数字的电话号码。

需要 100000000bit = 100000000/8 = 12500000bytes的内存进行存储， 也就是12.5M的内存空间进行存储。

关键是map的映射表， 如下：

我们需要申请的内存大小为 :

int arr[1 + N / 32], 我们当然可以使用<bitset>下面的bitset class了，但是这里重新造轮子， 只是为了说明原理。

arr[0]在内存中占用32bit， 可以对应0 - 31， 依次类推， bitmap 表如下：

arr[0] ------> 0 --- 31

arr[1] -------> 32 -- 63

arr[2] --------> 64 -- 95

arr[3] ---------> 96 --- 127

...........................

就这样， 完成了映射。 

bitmap的应用如下：

（1）可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

（2）去重数据而达到压缩数据

 int型变量a的第k位清0，即a=a&~(1<<k)
 将int型变量a的第k位置1， 即a=a|(1<<k)

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

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）。 去重， 使用bitmap 线性时间就可以了。


2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。 
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。