一个关于用户标签的需求

为了帮助公司精准定位用户群体，咱们需要开发一个用户画像系统，实现用户信息的标签化。

用户标签包括用户的社会属性、生活习惯、消费行为等信息，例如下面这个样子。

 

通过用户标签，我们可以对多样的用户群体进行统计。例如统计用户的男女比例、统计喜欢旅游的用户数量等。

为了满足用户标签的统计需求，小灰利用关系数据库设计了如下的表结构，每一个维度的标签对应着数据库表中的一列：

 

要想统计所有“90后”的程序员，该怎么做呢？

用一条求交集的SQL语句即可。

 

看起来很简单嘛，嘿嘿……

事情没那么简单，现在标签越来越多，例如，用户去过的城市、消费水平、爱吃的东西、喜欢的音乐……都快有上千个标签了，这要给数据库表增加多少列啊！

筛选的标签条件过多的时候，拼出来的SQL语句像面条一样长……

不仅如此，当对多个用户群体求并集时，需要用distinct来去掉重复数据，性能实在太差了……

用BITMAP算法解决问题

你听说过Bitmap算法吗？在中文里叫作位图算法。

这里所说的位图并不是像素图片的位图，而是内存中连续的二进制位（bit）所组成的数据结构，该算法主要用于对大量整数做去重和查询操作。

举一个例子，假设给出一块长度为10bit的内存空间，也就是Bitmap，想要依次插入整数4、2、1、3，需要怎么做呢？

很简单，具体做法如下。

第1步，给出一块长度为10的Bitmap，其中的每一个bit位分别对应着从0到9的整型数。此时，Bitmap的所有位都是0（用紫色表示）。

 

第2步，把整型数4存入Bitmap，对应存储的位置就是下标为4的位置，将此bit设置为1（用黄色表示）。

 

第3步，把整型数2存入Bitmap，对应存储的位置就是下标为2的位置，将此bit设置为1。

 

第4步，把整型数1存入Bitmap，对应存储的位置就是下标为1的位置，将此bit设置为1。

 

第5步，把整型数3存入Bitmap，对应存储的位置就是下标为3的位置，将此bit设置为1。

 

如果问此时Bitmap里存储了哪些元素，显然是4、3、2、1，一目了然。

Bitmap不仅方便查询，还可以去掉重复的整数。

你仔细想一想，你所做的用户标签能不能用Bitmap的形式进行存储呢？

我的每一条用户数据都对应着成百上千个标签，怎么也无法转换成Bitmap的形式啊？

别急，我们不妨转换一下思路，为什么一定要让一个用户对应多个标签，而不是一个标签对应多个用户呢？

信息不一定非要以用户为中心存储，也能够以标签为中心来存储，让每一个标签存储包含此标签的所有用户ID，就像倒排索引一样！

第1步，建立用户名和用户ID的映射。

 

第2步，让每一个标签存储包含此标签的所有用户ID，每一个标签都是一个独立的Bitmap。

 

这样一来，每一个用户特征都变得一目了然。

例如，程序员和“00后”这两个群体，各自的Bitmap分别如下所示。

 

BitMap好处

1.高性能的位运算

2.相比使用哈希表的话，每一个用户ID都要用整型数据存储，少则占用4字节（32bit），多则占用8字节（64bit）。而一个用户ID在Bitmap中只占1bit，内存是使用哈希表所占用内存的1/32，甚至更少！

3.Bitmap在对用户群做交集和并集运算时也有极大的便利

如何取反操作呢

我们可以使用异或 运算进行操作，即相同位为0，不同位为1。

同样是刚才的例子，我们给出“90后”用户的Bitmap，再给出一个全量用户的Bitmap。最终要求出的是存在于全量用户，但又不存在于“90后”用户的部分。

 

实现方式

长度计算公式

int nSize = (width * bitPixel + 64) / 64 ;

（高效写法是(((width * bitPixel + 64)>>6)) )

通过位移操作，可以很方便的扩容

而且越往上就是指数扩容，满足过亿级别数据量的时间复杂度也是O(1)

class MyBitmap:
    def __init__(self,size):
        self.words=[0]*(self.get_word_index(size-1)+1)
        self.size=size
    def get_bit(self,bit_index):
        if bit_index<0 or bit_index>self.size-1:
            raise Exception("超过Bitmap有效范围！")
        word_index=self.get_word_index(bit_index)
        return (self.words[word_index]&(1<<bit_index))!=0
    def set_bit(self,bit_index):
        if bit_index<0 or bit_index>self.size-1:
            raise Exception("超过Bitmap有效范围！")
        word_index=self.get_word_index(bit_index)
        self.words[word_index] |=(1<<bit_index)
    def get_word_index(self,bit_index):
        #右移6位，相当于除以64
        return bit_index>>6

bitMap=MyBitmap(128)
bitMap.set_bit(126)
bitMap.set_bit(75)
print(bitMap.get_bit(126))
print(bitMap.get_bit(78))