要點

• 位圖基本算法及其應用場景。
• 位圖算法的優化實現。

概述

位圖算法，是指使用一個bit位來表示數據狀態。通常應用于海量數據去重、海量數據計算及判斷海量數據中是否存在某個數據的場景中。

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

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

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

算法實現

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

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

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

寫入在某個bit位寫入數據時，首先通過整除，計算出該bit位在數組的哪個下標，然后，用取余計算出char元素中的哪個bit上。最后通過或運算將對應位設置為1。

// 置bit位
void set(BitSet& bits, int pos) {
    // 查找對應數組下標
    int unit = pos / CHAR_SIZE;
    // 查找在字節中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運算實現對應bit位置1
    bits[unit] = bits[unit] | (0x1 << p);

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

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

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

// 清空bit位
void clear(BitSet& bits, int pos) {
    // 查找對應數組下標
    int unit = pos / CHAR_SIZE;
    // 查找在字節中的bit位
    int p = pos % CHAR_SIZE;
    // 通過與運算實現對應bit位置1
    bits[unit] = bits[unit] & (~(0x1 << p));
}

交集對數組逐個元素進行或運算。

// 求位圖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];
    }
}

并集對數組逐元素進行與運算。

// 求位圖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];
    }
}

在生產實現時，可能會進行一些優化：

• 使用CPU指令優化，如SSE等，一次能進行128位的運算，可以提高計算速度。
• 某些業務場景下，一個數據狀態可能有大于2個，可以使用多個bit位來表示一個數據狀態。

擴展

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

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

roaring bitmap

容器的結構有三種類型：有序數組、未壓縮位圖、和行程長度編碼。

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

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

參考

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