數據包位圖索引壓縮算法研究

◆袁沐春 郭育辰

（中國人民公安大學 北京 102600）

數據包位圖索引壓縮算法研究

◆袁沐春 郭育辰

（中國人民公安大學 北京 102600）

為解決從存儲海量數據包的數據庫中快速找到少量的被需要的數據包的時間效率問題，本文引入位圖索引數據庫，并對三種常見的位圖索引壓縮算法做簡要分析。

數據包；位圖索引；數據庫；算法

0 引言

傳統的關系型數據庫是面向更改的，存儲在數據庫中的數據需要經常改動。而位圖索引數據庫專門為科學數據設計，這些數據通常是由科學儀器或是科學仿真產生的，特點是數據量極其大，而且不再更改。位圖索引數據庫解決了如何在存儲海量數據包的數據庫中快速地找出那些少量被需要的數據包的問題，而傳統的關系型數據庫并不適合這項任務。

位圖索引數據庫中用到的技術主要是位圖索引、位圖壓縮和歸類。在位圖索引數據庫中，數據是按列存儲的，一個列的數據存儲在一起，并做位圖索引。一個簡單的位圖索引的例子如表1所示。其中RowID表示對應值在表中第幾行，生成的索引是一個矩陣，矩陣中每一行只有一個1，其余都是0，標1的位置對應于該行數據在這一列上的取值。這樣生成的位圖索引有一個比較大的缺點，索引的列數隨著取值的多樣性而線性增長。為了控制索引的大小和查詢時間，需要對索引壓縮和歸類。壓縮是減小索引中大量0帶來的空間消耗，歸類是對位圖索引的一些列的合并。比如值1.01和1.02可以歸類成1。通過歸類可以減少位圖索引的列數，增加查詢和存儲的效率。

表1 位圖索引示例

下面主要研究三種位圖索引壓縮算法WAH[1]、PLWAH[2]、COMPAX[3]。

1 WAH索引壓縮算法

WAH索引壓縮算法示例如表2所示。

表2 WAH索引壓縮算法示例

WAH算法是FastBit索引數據庫的默認算法，將位序列分成以31b（對于WAH64就是63b）為單位的group。這樣，group有兩種類型。

（1）Literal，即這31b中有0有1。

（2）Fill，即這31b全為0或者全為1。

在WAH算法中，最終形成的word是32b，其中最高位為類型的標志位。Literal類型的Group：類型標志位為0，余下的31b即為原來的literal group；Fill類型的Group：分為1-Fill和0-Fill。此時32b中類型標志位為1，第二位作為Fill類型的標志（0-Fill即為0，1-Fill即為1），余下的30b作為counter，表示連續出現多少個0-Fill（或者1-Fill）的 group。

2 PLWAH算法及改進

PLWAH算法和WAH算法類似，同樣是將原始碼流分成以31b為單位的group。Group也和WAH算法中提到的相同，一樣分成Literal和Fill兩種類型，但是壓縮方式有變化，具體如下所示。

第一步：依照WAH算法對于Fill-Group和Literal-Group添加標志位與編碼，形成一組以32b為單位的編碼（標志位為0稱為literal-word，標志位為1稱為fill-word，下同）。此處的區別是對于fill-word只有低25b作為counter（WAH算法是低30b都是counter，PLWAH要留出中間的5b作為position list）。

第二步：檢查每個fill-word后的word。如果下一個word是literal-word且是nearly identical（表現為literal-word和上一個fill-word的差異小于等于s位，s此處暫且為1），則在fill-word的position list上填入下一個word（此時為literal-word）的差異位位置（此處是31b，因此差一位標號是1～3，留出5b目的在此），同時刪去下一個word（因為信息已經保存在此fill-word中，沒有必要繼續留著），若fill-word后的word是如下三種情況：

（1）異類型的fill-word。

（2）非nearly identical的literal-word。

（3）同類型的fill-word（這種情況產生的原因是連續的fill-group超出了1個fill-word的counter計數范圍），則position list不變。

進行擴展討論：

對于32位PLWAH，由于nearly identical的定義中的s不為1，則在第一步時需要留出5*s位nearly identical，余下的32-2-5*s位為counter。在第二步時，向fill-word中的position list添加差異位時需按序添加差異位位置（5b標識一個差異位，5*s位標識至多s個差異位），當s=0時，PLWAH退化為WAH。

對于64位PLWAH，position list以6為單位，即留出6*s位作為position list，余下的64-2-6*s位為counter。

以PLWAH32，s=1為例，對PLWAH進行了小幅改進，即考慮連續出現極多的0或者1以至于1個word的counter無法完全容納。此處選用的方法為使用兩個連續的同類型fill-word，把兩個counter部分視為一個大的counter，第一個fill-word記錄LSB25位，第二個fill-word記錄MSB25位（相當于50b的大counter），同時第一個fill-word的position list為空，第二個fill-word的position list照常計算，如表3所示。這樣的好處是無需擴展word位數即可完成對更多連續碼流的編碼任務，節約index空間。

表3 PLWAH改進舉例

25 MSB of counter

3 COMPAX算法

COMPAX壓縮算法示例如圖1所示。

COMPAX算法也是WAH的改進，這里以32b為例，但COMPAX的標志位相對較多。這里Literal和Fill的定義同WAH和PLWAH。同樣是每31b分成一個group，并且將這些group按照以下特征分組。

（1）Literal-Fill-Literal（LFL），即一個literal group +N個Fill group+1個literal group，且這兩個literal group 的非0位（或者非1位）在同一個byte上（一個group在前面補一位0即構成4個完整的byte，要求非0位在同一個完整的byte上）。

（2）Fill-Literal-Fill（FLF），即N個Fill-group+1個literal group+N個fill-group（對literal group要求同上）。

（3）Fill（F），分為0-Fill和1-Fill，無法按照（1）和（2）進行分組的fill-group即歸入此類型。

（4）Literal（L），無法按照（1）和（2）進行分組的literal group 即歸入此類型。

圖1 COMPAX壓縮算法示例

對于這4種類型，就有4種不同的word。

（1）L-word第一位為標志位1，余下31b即為原來的literal group。

（2）F-word第一位為標志位0，對于0-Fill第二、三位為00，對于1-Fill第二、三位為11。余下29b位counter，即記錄有多少個連續這樣的group。

（3）LFL-word第一位為標志位0，第二、三位為01，第四、五位標識第一個literal group的非零字節位置（共4b，標號為0～3），第六、七位標識第二個literal group的非零字節位置（共4b，標號為0～3），第八位標識F類型，0為0-Fill，1為1-Fill；第九到十六位為第一個literal group中非零字節，第十七到二十四位為Fill的counter，標示有多少個連續的fill group，第二十五到三十二位為第二個literal group中的非零字節。

（4）FLF-word第一位為標志位0，第二、三位為10，第四、五位為第一個fill的類型（0-Fill為00，1-Fill為11），第六、七位為第二個fill的類型，第八位空閑。第九到十六位為第一個fill的counter，第十七到二十四位為literal group的非零字節，第二十五到三十二位為第二個fill的counter。

在已知COMPAX的情況下，具體讀碼方式如下：

（1）如果第一位為1，為L-word。

（2）如果第一位為0；

1第二、三位為00：0-fill-word。

2第二、三位為11：1-fill-word。

3第二、三位為01：LFL。

4第二、三位為10：FLF。

4 結語

隨著互聯網的普及滲透，網絡日常運營中生成積累的用戶行為數據往往達到TB級甚至PB級。本文對數據包查詢優化過程中的三種位圖索引壓縮算法進行研究改進，以期為龐大的數據流量管理與網絡流量檔案化提供更多的技術手段。

[1]Wu K,Otoo E J,Shoshani A.Optimizing bitmap indices with efficient compression[J].Acm Transactions on Database Systems,2006.

[2]Deli&#,ge,Fran&#,Pedersen T B.Position list word aligned hybrid:optimizing space and performance for compressed bitmaps[C]//EDBT 2010,13thInternational Conference on Extending Database Technology，Lausanne,Switzerland,March 22-26,2010.

[3]Fusco F,Stoecklin M P,Vlachos M.Net-Fli:On –thefly Compression,Archiving and Indexing of Streaming Network Traffic.[J].Proceedings of the Vld Endowment，2010.