要點

• 位圖基本算法及其應(yīng)用場景。
• 位圖算法的優(yōu)化實現(xiàn)。

概述

位圖算法，是指使用一個bit位來表示數(shù)據(jù)狀態(tài)。通常應(yīng)用于海量數(shù)據(jù)去重、海量數(shù)據(jù)計算及判斷海量數(shù)據(jù)中是否存在某個數(shù)據(jù)的場景中。

以海量數(shù)據(jù)中是否存在某個數(shù)據(jù)的應(yīng)用場景為例，假設(shè)用16個bit位，分別表示數(shù)字0-15。bit位的值，表示該數(shù)字是否存在，0表示不存在，1表示存在。如上圖所示，在該數(shù)據(jù)集合中，存在的元素有1、2、6、10、11和13。

可以發(fā)現(xiàn)，在數(shù)據(jù)比較稠密的情況下，位圖算法能夠節(jié)約存儲空間，如圖中，使用2個字節(jié)便可以表示16個數(shù)字，同時可以在O(1)的時間復(fù)雜度下，判斷是否存在某個數(shù)字，大大提高了計算速度。

但是，在數(shù)據(jù)稀疏時，存儲空間會存在一定程度的浪費。由于位圖算法中，位圖空間的大小是一定的，并不會根據(jù)存儲數(shù)據(jù)量的大小而改變。因此，當(dāng)位圖空間中存儲的數(shù)據(jù)量很小時，大量地位圖空間是空閑的，存在大量的浪費。

算法實現(xiàn)

位圖算法在主流開發(fā)語言中，都有對應(yīng)的實現(xiàn)。基本操作主要有寫入、查詢、刪除、交集、并集等。下面通過一個示例來了解一下，位圖算法的實現(xiàn)。

位圖結(jié)構(gòu)定義例子使用char類型數(shù)組來存儲位圖信息(通常的實現(xiàn)中，會使用長整型數(shù)組)，一個char類型有8個bit位。定義結(jié)構(gòu)如下：

// 為了簡化問題，LEN必須定義為CHAR_SIZE的倍數(shù)
#define LEN 16
#define CHAR_SIZE 8
typedef char BitSet[LEN/CHAR_SIZE];

寫入在某個bit位寫入數(shù)據(jù)時，首先通過整除，計算出該bit位在數(shù)組的哪個下標(biāo)，然后，用取余計算出char元素中的哪個bit上。最后通過或運算將對應(yīng)位設(shè)置為1。

// 置bit位
void set(BitSet& bits, int pos) {
    // 查找對應(yīng)數(shù)組下標(biāo)
    int unit = pos / CHAR_SIZE;
    // 查找在字節(jié)中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運算實現(xiàn)對應(yīng)bit位置1
    bits[unit] = bits[unit] | (0x1 << p);

查詢同寫入操作，先計算出bit位置，查找到對應(yīng)的bit位，然后返回該位置的數(shù)值。

// 查詢bit位
int get(BitSet& bits, int pos) {
    // 查找對應(yīng)數(shù)組下標(biāo)
    int unit = pos / CHAR_SIZE;
    // 查找在字節(jié)中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運算實現(xiàn)對應(yīng)bit位置1
    return  (bits[unit] & (0x1 << p)) > 0 ? 1 : 0;
}

刪除首先查找到對應(yīng)的位置，然后通過與運算將該位置清空。

// 清空bit位
void clear(BitSet& bits, int pos) {
    // 查找對應(yīng)數(shù)組下標(biāo)
    int unit = pos / CHAR_SIZE;
    // 查找在字節(jié)中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運算實現(xiàn)對應(yīng)bit位置1
    bits[unit] = bits[unit] & (~(0x1 << p));
}

交集對數(shù)組逐個元素進行或運算。

// 求位圖b1和b2的并集
void unionn(const BitSet& b1, const BitSet& b2, BitSet& res) {
    for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
        res[i] = b1[i] | b2[i];
    }
}

并集對數(shù)組逐元素進行與運算。

// 求位圖b1和b2的交集
void inter(const BitSet& b1, const BitSet& b2, BitSet& res) {
    for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
        res[i] = b1[i] & b2[i];
    }
}

在生產(chǎn)實現(xiàn)時，可能會進行一些優(yōu)化：

• 使用CPU指令優(yōu)化，如SSE等，一次能進行128位的運算，可以提高計算速度。
• 某些業(yè)務(wù)場景下，一個數(shù)據(jù)狀態(tài)可能有大于2個，可以使用多個bit位來表示一個數(shù)據(jù)狀態(tài)。

擴展

為了解決位圖稀疏時，位圖低效率的問題，工業(yè)界，有多種位圖壓縮算法，其中，最經(jīng)典的是RoaringBitmap。

RoaringBitmap的核心思想是，將整數(shù)進行分桶，高16位的值作為其桶的索引，每個桶對應(yīng)一個容器。如下圖所示：

roaring bitmap

容器的結(jié)構(gòu)有三種類型：有序數(shù)組、未壓縮位圖、和行程長度編碼。

• 有序數(shù)組：當(dāng)?shù)?6位中，元素個數(shù)小于4096時，采用有序數(shù)組的結(jié)構(gòu)進行存儲。在查找元素時，使用二分查找方法。取值4096的原因是，存儲4096個16位的整數(shù)，所占用的存儲空間：。
• 未壓縮位圖：未壓縮位圖的存儲結(jié)果就是本文所描述的位圖存儲結(jié)構(gòu)，使用一個固定的連續(xù)內(nèi)存塊實現(xiàn)。
• 行程長度編碼(run-length encoding)：行程長度編碼是一種無損數(shù)據(jù)壓縮技術(shù)，其原理是，將連續(xù)出現(xiàn)的數(shù)據(jù)存儲為起始值和計算兩部分。比如，數(shù)據(jù)列表[1,2,3,4,5,6]存儲為[1,5]，表示以1開始，后面連續(xù)遞增5個數(shù)值。在很多實現(xiàn)中，行程長度編碼容器，需要手動調(diào)用，才能轉(zhuǎn)換為該容器。

在進行插入和刪除操作之后，需要根據(jù)元素個數(shù)進行容器轉(zhuǎn)換。插入元素時，若元素個數(shù)達(dá)到4096，則需要轉(zhuǎn)換為未壓縮位圖進行存儲。刪除元素時，若元素個數(shù)小于4096時，則需要轉(zhuǎn)換為有序數(shù)組存儲。

參考

• Better bitmap performance with Roaring bitmaps。
• Consistently faster and smaller compressed bitmaps with Roaring。
• https://github.com/RoaringBitmap/CRoaring.git。