求bitmap（位图）的压缩算法

burt2007

最近在用C做一个UID排重的程序，在尝试bitmap（位图）存储与比较。

先把源UID存到内存中，和需要对比的UID进行对比。

效率挺高的，可是内存利用率太低了。

比如申请了(unsigned int)(~0)字节的内存=4294967295*4*8bit，如果源uid有4亿个，利用率也只是接近1/42

请教各位大神有没有位图的压缩算法或者其他更好的处理方式？

先谢过啦

bruceteen

把位图压缩一下那就是hashtable
std::unordered_map

fenghw8088

我觉得将bitmap做压缩不好，因为是正在使用过程中，每个记录查重都有解压，之后再压缩，不但浪费CPU，而且也不见得省内存。

哈希表也不好，因为哈希是做压缩映射，冲突不可避免，这样每条记录必须保存pk的数据项，而不只是存储记录有无的标记位，PK肯定比1个位标记空间大得多。

比较好的办法是将bitmap分页，根据内存大小选择部分在内存，部分在磁盘。方案的缺点是编程复杂，性能也不如驻留内存好，但是有很好的弹性。

burt2007

回复 3# fenghw8088

咱两想的差不多。压缩之后再做对比的时候会浪费时间，也不一定有效。

我在尝试在bitmap的基础上再做索引，进行中


   

starwing83

回复 3# fenghw8088


    推荐Judy Array，有做标记的版本Judy1，网址：http://judy.sourceforge.net/

这是一个数组，可以高效存储dword（4bit int）到指针的映射。其中Judy1是按bit存储的。即dword到1bit的映射。实质上就是一个按需扩展的bitmap。Judy Array的优势是内存使用率和效率都比较高。

burt2007

回复 5# starwing83


测试效果不错。
测试文件为有29904140行的uid文件，有重复

效果对比：
# time ./bitmap.test.out
real    0m8.002s
user    0m7.653s
sys     0m0.299s

# time ./judy.test.out
real    0m11.257s
user    0m11.063s
sys     0m0.174s

#ps aux
root     17370 56.6  0.4 138416 132836 pts/0   S+   14:44   0:10 ./judy.test.out
root     17579 53.8  0.8 530420 280572 pts/0   S+   14:45   0:09 ./bitmap.test.out