bit地图算法简介

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 << " ";
        }
    }
}

运行结果如下：

bit地图算法简介

这样，我们就在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，都是一样的道理。

1楼u010700335昨天 22:02: 请问，大神要是不知道最大的数值是多少，怎么办呢？

bit地图算法简介

相关推荐