一种新的压缩比特位图索引的方法

摘要

本发明公开了计算机网络或大数据分析领域的一种新的压缩比特位图索引的方法，即ICX算法，用以解决目前压缩比特位图的研究中存在的问题。该方法主要是对COMPAX算法进行改进，提出Nearly Identical的概念，具体包括：把待压缩的01比特序列分成以31bits为单位的块，对块进行分类标记：F-块和L-块，L块又分为C-L-块，0-NI-L-块和1-NI-L块，0-NI2-L块，1-NI2-L块；根据ICX码本与编码规则，在码本编码FL序列基础上，进一步编码，具体分为：L-字编码，F-字编码，FLF-字编码，LFL-字编码，NI-FL字编码，NI2-FL字编码。与COMPAX算法相比，本发明提高了编码效率，有效实现了一种新的压缩比特位图索引的方法。

说明书

技术领域

本发明涉及计算机网络或大数据分析领域，特别涉及一种新的压 缩比特位图索引的方法。

背景技术

互联网技术的迅猛发展把我们带进了信息爆炸的时代，海量信息 内容极大丰富了用户。而移动互联网的爆发，使得用户可以从任何地 方，任何时间访问网络上的任何内容，产生更为丰富流量数据。

据思科(Cisco)公司预测，任何一家大型互联网公司在日常运 营中生成和累计的用户流量数据是相当庞大的，以至于不能用千兆 (Giga，G)或万亿(Trillion，T)级字节的数据来衡量。为此，思 科曾预言，网络的数据流量在2011到2016年之间将以4倍的速率增 长，并于2016年达到1.3泽(Zetta，十万亿亿)字节。据中国联通 的数据，联通WCDMA3G网络移动用户流量的年复合增长率为 135％，目前已经达到5千万亿字节(Petabyte，PB)规模。

对网络的内容和运行状况监控，保证网络健康正常地运行已成为 一项重要工作。在中国“十二五”规划纲要第三篇第十三章第二节中， 已经明确提出要“加强网络与信息安全保障”，充分体验了国家对信 息安全的重视。而网络的自由性造成了网络攻击的普遍性。在网络链 路方面，网络中某个节点的错误配置可能会给整个网络带来灾难性的 后果；网络攻击会造成链路的阻塞，服务器的崩溃，甚至是局部网络 通信的中断。在网络内容方面，人们可以在各个地方上传不良信息， 进行非法活动，给其他互联网的使用者带来不好的思想、精神、经济 等方面的影响和损失。由于这些行为常常不能在发生时被发现，因此 需要对网络流量进行记录，以供后期进行研究、分析和举证。

流量记录的一项核心技术是高速网包索引，流量记录的目的是为 以后检索与查找，从而识别可能的网络事件。以10Gbps链路为例， 如果按每个网包64字节计算，每秒将达1400万网包，产生的索引量 巨大，检索查找速度慢。

因特网服务提供商(Internet Service Provider，ISP)管理和运行 的大型的高速网络，链路速度在10-100Gbps级，即每秒中产生的数 据量为1-10GB量级，如果要进行流量的记录，代价非常高。这样的 设备和技术的价格也是一般用户无法承受的。而同时，互联网的发展 使得许多公司拥有自己的企业网络，也有许多公司将自己的服务器托 管到因特网数据中心(Internet Data Center，IDC)运行。这样的局部 网络的数目非常庞大，他们的网络带宽一般在100～1000Mbps。管理 这些局部的网络也是一个非常现实的问题，为这样的网络设计和实现 廉价的网络流量记录工具具有很大的应用前景。

网包的索引信息具有以下一些特点：海量、数据结构固定、只增 不改、重复性较高。海量是指网包索引信息条数众多，一天可以产生 几百万条甚至上亿条索引信息。数据结构固定是指每一条网包的索引 信息都有固定的格式和固定的长短。只增不改是指网包的索引信息只 会不断增加，一旦产生，以后不可能也不需要在进行修改。重复性高 指就每一个域来看，一个域中的千万条数据出现大量的重复。这些特 点导致使用关系型数据库处理这样的数据效率并不高，因为传统的关 系型数据库是面向更改的，储存在数据库中的数据需要经常的改动。

Bitmap压缩数据库

Bitmap索引数据库专门为科学数据而设计，这些数据通常是由 科学仪器或是科学仿真产生的，特点是数据量极其大，而且不再更改。 Bitmap索引数据库解决了如何在海量的科学数据中快速的找出那些 需要的少量的数据的问题，而传统关系型数据库并不适合这项任务。

Bitmap索引数据库中用到的技术主要是Bitmap索引、Bitmap压 缩和归类。在Bitmap索引数据库中，数据是按列存储的，一个列的 数据存储在一起，并做Bitmap索引。一个简单的Bitmap索引的例子 如图1所示。其中RowID表示对应值在表中第几行，生成的索引是 一个矩阵，矩阵中每一行只有一个1，其余都是零，标1的位置对应 于该行数据在这一列上的取值。这样生成的Bitmap索引有一个比较 大的缺点，索引的列数随着取值的多样话而线性增长。为了控制索引 的大小和查询时间，需要对索引压缩和归类。压缩是减小索引中大量 0或1带来的空间消耗，归类是对Bitmap索引的一些列的合并。比 如值1.01和1.02可以归类成1。通过归类可以减少Bitmap索引的列 数，增加查询和储存的效率。

目前主要的位图索引压缩算法为字对齐混合编码(Word-Aligned  Hybrid code，WAH)，Position List Word-Aligned Hybrid code(PLWAH) 和Compressed Adaptive Index(COMPAX)。其中PLWAH有改进版(即 为PLWAH with adaptive counter)，COMPAX也有改进版(COMPAX+ oLSH)。

1WAH索引压缩算法

WAH是Fastbit比特位压缩数据库的默认算法，如图2。将原始 码流分成以31bits(对于WAH64就是63bits)为单位的块(chunk)。 chunk有两种类型：

(1)Literal，即这31bits中有0有1。

(2)Fill，即这31bits全为0或者全为1。

Literal类型的Chunk：类型标志位为0，余下的31bit即为原来的 literal chunk；Fill类型的Chunk:分为1-Fill和0-Fill。此时32bits 中类型标志位为1，第二位作为Fill类型的标志(0-Fill即为0，1-Fill 即为1)，余下为30bits作为counter，表示连续出现多少个0-Fill(或 者1-Fill)的chunk的。

2PLWAH索引压缩算法

同样是将原始码流分成以31bits为单位的chunk。Chunk也和上 文一样分成Literal和Fill两种类型，但是压缩方式有变化。

第一步：依照WAH方法对于Fill-chunk和Literal-chunk添加标 志位与编码，形成一组以32-bits word为单位的编码(标志位为0称 之为literal-word，标志位为1的称之为fill-word，下同)。此处的区 别是对于fill-word只有低25bits作为counter(WAH方法是低30bits 都是counter,PLWAH要留出中间的5bits作为position list，下面会用 到.)

第二步：

检查每个fill-word后的word。如果下一个word是literal-word 且是”nearly identical”的(nearly identical定义是literal-word和上 一个fill-word的差异小于等于s位，s此处暂时为1,后面会进一步讨 论)，则在fill-word的position list上填入下一个word(此时为 literal-word)的差异位位置(此处是31位，因此差异位标号为1-31， 留出5bits目的在此)，同时删去下一个word(因为信息已经保存在 此fill-word中，没有必要继续留着)若fill-word后的word是如下三 种情况：(1)异类型的fill-word(2)非nearly-identical的literal-word (3)同类型的fill-word(这种情况产生的原因是连续的fill-chunk超 出了1个fill-word的counter的计数范围)，则position list不变。

进行扩展讨论：

对于32位PLWAH,但是nearly identical的定义中的s不为1,则在 第一步(即利用WAH原理编码)时需要留出5*s位position list，余 下的32-2-5*s位为counter.在第二步时，向fill-word中的position list 添加差异位时须按序添加差异位位置(5个bits标示一个差异位，5*s 个bits标示至多s个差异位，但是原文没有明确说当实际差异位小于 s时是向最高有效位(most significant bit，MSB)对齐还是向最低有 效位(Least significant bit，LSB)位对齐，只给了个接口)，当s＝0 时PLWAH退化成WAH。

对于64位PLWAH，position list以6为单位，即留出6*s位为 position list，余下的64-2-6*位为counter.

PLWAH+adaptive counter方法，如图4所示，对PLWAH进行 了小幅改进，即考虑连续出现极多的0或者1以至于1个word的 counter无法完全容纳。此处选用的方法为使用两个连续的同类型 fill-word，把两个counter部分视为一个大的counter，第一个fill-word 记录LSB25位，第二个fill-word记录MSB25位(相当于50位的大 counter)，同时第一个fill-word的position list为空，第二个fill-word 的position list照常进行计算。这样的好处是无需将扩展word位数即 可完成对更多连续码流的编码任务，节约index空间。

3COMPAX算法

COMPAX算法如图5所示，这里以32位为例。

COMPAX的标志位相对较多。这里Literal和Fill的定义同WAH 和PLWAH。

同样是每31bits分成一个chunk，并且将这些chunk按照以下特 征分组：

(1)Literal-Fill-Literal(LFL),即1个literal chunk+N个Fill  chunk+1个literal chunk，且这两个literal chunk的非0位(或者非1 位)在同一个byte上(一个chunk在前面补一位0即构成4个完整 的byte，要求非零位在同一个完整的byte上)

(2)Fill-Literal-Fill(FLF),即N个Fill-chunk+1个literal chunk +N个fill-chunk(对literal chunk的要求同上)

(3)Fill(F)，分为0-Fill和1-Fill,无法按照(1)和(2)进行 分组的fill-chunk即归入此类型。

(4)Literal(L)，无法按照(1)和(2)进行分组的literal chunk 即归入此类型。

对于这四种类型，有四种不同的word。

(1)L-word第一位为标志位1，余下31位即为原来的literal  chunk。

(2)F-word第一位为标志位0，对于0-Fill第二、三位为00， 对于1-Fill第二、三位为11。余下29bits为counter,即记录有多少个 连续这样的chunk。

(3)LFL-word第一位为标志位0，二三位为01，第4、5位(2bits) 标示第一个literal chunk的非零byte位置(共4个byte，标号为00-11), 第6、7位(2bits)标示第二个literal chunk的非零byte位置(共4 个byte,标号为0-3)第八位标识F类型，0为0-Fill,1为1-Fill；第9-16 位(8bits，1byte)为第一个literal chunk中非零byte，第17-24位 (8bits,1byte)为Fill的counter，标示有多少个连续的fill chunk(即 多少个连续31bits的0/1),第25-32位(8bits，1byte)为第二个literal  chunk中的非零byte。

(4)FLF-word第一位为标志位0，第二、三位为10，第四位为 第一个fill的类型(0-Fill为0，1-Fill为1，下同),第五位为第二个 fill的类型，第六、七位为L的非零byte位置(标号为00-11),第八 位空闲。第9-16位(8bits)为第一个fill的counter，第17-24位 (8bits,1byte)为literal chunk的非零byte，第25-32位为第二个fill 的counter。

在已知COMPAX的情况读码方式如下：

(1)第一位如果为1，为L-word；

(2)第一位如果为0：

(2.1)第二、三位为00：0-fill word

(2.2)第二、三位为11：1-fill word

(2.3)第二、三位为01：LFL

(2.4)第二、三位为10：FLF

COMPAX+oLSH(online-locality-sensitive-hashing)

压缩方式同COMPAX，但是先对输入码流进行处理，将相近的 包放在相近的位置，这样对压缩率提高非常明显。

发明内容

本发明的目的在于，提出一种新的压缩比特位图索引的方法 (Improved COMPAX，ICX)，用以解决目前位图索引压缩算法中存 在的问题。

为实现上述目的，本发明提出的技术方案是，一种新的压缩比特 位图索引的方法，其特征是所述方法包括下列步骤：

步骤1：把待压缩的01比特序列分成以31bits为单位的块，对块 进行分类标记；

步骤2：根据ICX码本与编码规则，在码本编码FL序列基础上， 进一步编码。

所述步骤1中把待压缩的01比特序列分成以31bits为单位的块， 对块进行分类标记，具体包括：F-块和L-块，L块又分为C-L-块， 0-NI-L-块和1-NI-L块，0-NI2-L块，1-NI2-L块。

所述0-NI-L-块的定义为：一个L-块(补0后)与全0字比较， 差异比特在同一个字节内，则记做0-NI-L-块。

所述1-NI-L-块的定义为：一个L-块(补1后)与全1字比较， 差异比特在同一个字节内，则记做0-NI-L-块。

所述0-NI2-L-块的定义为：一个L-块(补0后)与全0字比较， 差异比特在同2个字节内，则记做0-NI2-L-块。

所述1-NI2-L-块的定义为：一个L-块(补1后)与全1字比较， 差异比特在同2个字节内，则记做1-NI2-L-块。

所述步骤2中根据ICX码本与编码规则，在码本编码FL序列基 础上，进一步编码，具体包括：L-字编码，F-字编码，FLF-字编码， LFL-字编码，NI-FL字编码，NI2-FL字编码。

所述FLF-字编码的定义为：对满足[1个或多个同类型F-块]-[1个 0-NI-L块或者1-NI-L块]-[1个或多个同类型的F-块]的块组合进行编 码。

所述LFL-字编码的定义为：对满足[一个NI-L-块]-[1个或多个F- 块]-[一个NI-L块]的块组合进行编码。

所述NI-FL-字编码的定义为：对满足[一个NI-LF块]-[一个或者 多个同类型F块]的块组合进行编码。

所述NI-FL-字编码的定义为：对满足[一个NI2-LF块]-[一个或多 个同类型的F-块]的块组合进行编码。

本发明的有益效果在于ICX比COMPAX有更好的编码效率。

附图说明

图1是Bitmap索引示例。

图2是WAH算法示例。

图3是PLWAH32算法示例。

图4是PLWAH+adaptive counter：(以PLWAH32，s＝1为例)。

图5是COMPAX算法。

图6是将1个C-L-块编码为L-字。

图7是当原比特序列中连续出现7个0-F-块时的编码结果。

图8是当原比特序列中连续出现3个1-F-块时的编码结果。

图9是通过COMPAX和ICX算法分别将原比特序列编码为FLF。

图10是用ICX将原比特序列编码为FLF，用COMPAX将原比 特序列编码为一个F字+一个L字+一个F字。

图11是可以被COMPAX和ICX两种方式编码为LFL的一个原 比特序列。

图12是不可以被COMPAX方式编码为LFL，只能被ICX编码 为LFL的一个原比特序列。

图13是图12中的原比特序列被COMPAX编码的结果。

图14是不可以被COMPAX方式编码为LFL，只能被ICX编码 为LFL的一个原比特序列。

图15是图14中的原比特序列被COMPAX编码的结果。

图16是NI-L类型且第二个是Fill时编码的流程图。

图17是无法被WAH和COMPAX进行编码的一个原比特序列。

图18是NI2-FL字编码中第6-8位的编码规则。

图19是无法被WAH和COMPAX进行编码的一个原比特序列。

图20是ICX的码本。

具体实施方式

下面结合附图，对优选实施例作详细说明。应该强调的是，下述 说明仅仅是示例性的，而不是为了限制本发明的范围及其应用。

本发明解决问题的思路是完成ICX算法：首先，对01比特序列 进行有效压缩的算法，通过设计的ICX码本，对符合特征的01串转 换为两类31比特块，称为F-块和L-块，L块又分为C-L-块，0-NI-L- 块和1-NI-L块,0-NI2-L-块和1-NI2-L块；然后，根据ICX码本与编 码规则，在码本编码FL序列基础上，进一步编码，具体包括：L-字 编码，F-字编码，FLF-字编码，LFL-字编码，NI-FL字编码，NI2-FL 字编码。

下面以互联网流量大数据检索系统为例，实现ICX位图索引压 缩算法。

基于提出位图索引编码的大数据检索系统实现分成三个模块：数 据预处理模块，位图索引构建模块，数据检索模块。

1数据预处理模块：

在数据进入模块之前有预处理过程，以动态和静态模式进行数据 处理。对于静态模式(对于已经存储的原始数据文件进行重新处理来 实现压缩与构建索引)，将数据文件中的数据项利用局部敏感函数 (LSH，相近的数据项得到的哈希值也相近)计算哈希值，并按照哈 希值顺序进行重排序(reorder)过程，之后将数据提交给数据压缩模块 与索引构建模块进行下一步处理。对于动态模式，用一段固定存储空 间，缓存接收实时抓取的流量，当缓存数据达到上限时，提交给下一 级来进行重排序的操作(类似于静态模式)，之后数据提交给索引构 建模块进行下一步处理。而由于此时缓存已经被清空，可以继续接受 网络上的实时流量，这样就实现了动态处理的过程。

2位图索引构建模块：

位图编码部分为利用所提的编码方法，将原始位图编码成最终的 位图索引文件，并进行存储。利用位图索引的理由是检索速度快，在 实际对海量数据进行查找分析时相对更为实用与方便，但是位图本身 的特点是空间占用巨大，会成为空间开销的主要负担，需要对于位图 进行重新编码来降低此部分的空间开销。位图索引构建传统有两个步 骤：位图生成与位图编码，也可以合二为一。

3数据检索模块：

用户输入希望检索的条件，之后系统从构建的位图索引文件中依 照索引查找对应的条目，可快速执行与，或，非与JOIN操作。如果 对索引文件全部解码的话，会造成巨大的时间开销与空间开销，因此 引入了动态判断策略，输入检索条件通过动态判断策略的处理决定是 部分解码(partial-decompression)还是全部解码(full-decompression).部 分解码的方法是只对命中条目附近的块(block)进行解码并抽出检索 命中的数据,而全部解码则利用在部分解码带来收益不大的场景，这 样可以相对提高检索效率。

下面的实施例是按照本发明提出的ICX算法对位图索引构建模 块中的位图编码部分进行处理，将其原始位图编码成最终的位图索引 文件，并进行存储的过程。

下面结合附图说明本发明的具体实现方式。该方法包括如下的步 骤：

步骤1：把待压缩的01比特序列分成以31bits为单位的块，对 块进行分类标记，可分为以下几类：Fill(F-块)和Literal(L-块)， L-块又分为common-literal-chunk(C-L-块)，0-nearly  identical-literal-chunk(0-NI-L-块)和1-nearly identical-literal-chunk (1-NI-L块)，0-nearly identical-2-literal-chunk(0-NI2-L块)，1-nearly  identical-2-literal-chunk(1-NI2-L块)。

1.F-块，代表块中31比特全为0或者全为1，全为0的块定义为 0-Fill块(下面简称0-F-块)，全为1的块定义为1-Fill块(下面简 称1-F-块)。

2.L-块，代表块中31比特不全为0且不全为1。

3.将31比特块分为7-8-8-8四部分，最前面补上一位空白位(不 一定是零，下面会分情况说明)，构成四个字节(一个32位字)，如 果和一个全0字比较，空白位置0；如果和全1字比较，空白位置1。

定义Nearly Identical块为如下四种类型：

1.如果一个L-块(补0后)与全0字比较，差异比特在同一个 字节内，则认为这个L-块和一个0-F-块是nearly identical的，记作 0-NI-L-块；

2.如果一个L-块(补1后)与全1字比较，差异比特在同一个 字节内，则认为这个L块和一个1-F-块是nearly identical的，记作 1-NI-L-块；

3.如果一个L-块(补0后)与全0字比较，差异比特在两个字 节内，则认为这个L-块和一个0-F-块是nearly identical(type2)的，记 作0-NI2-L-块；

4.如果一个L-块(补1后)与全1字比较，差异比特在两个字 节内，则认为这个L块和一个1-F-块是nearly identical的，记作 1-NI2-L-块。

5.其他的L-块记作C-L-块。

步骤2：根据ICX码本与编码规则，在码本编码FL序列基础上， 进一步编码。主要分为以下几种类型：Literal word(L-字)编码，Fill  Word(F-字)编码，Fill-Literal-Fill Word(FLF-字)编码， Literal-Fill-Literal Word(LFL-字)编码，Fill(Nearly Identical)-Literal  Word(NI-FL字)编码，Fill(Nearly Identical-Type Two)(NI2-FL字) 编码。

1.一个L-字是对1个C-L-块进行编码，编码方式为在这个C-L- 块的最高位前补1构成一个字。图6是将1个C-L-块编码为L-字。

2.一个F-字是对1个或多个同类型的F-块进行编码，前五位为 类型标志位00000，第六位表示的为F-字所编码的F-块的类型(0为 0-F-块，1为1-F-块)，后26位为计数器(counter)，标志着连续出现的 同类型F-块的数量。

图7是当原比特序列中连续出现7个0-F-块时的编码结果。

图8是当原比特序列中连续出现3个1-F-块时的编码结果。

3.一个FLF-字是对满足如下条件的块的组合进行编码：[1个或 多个同类型F-块]-[1个0-NI-L块或者1-NI-L块]-[1个或多个同类型 的F-块]，或者说[F-字]-[NI-L块]-[F-字].(此处说F-字并不完全准确， 但是首先COMPAX中原文写的也是Fill Word，且此处实质上也是对 多个同类型F-块合并后所得，因此借用F-字概念，实际长度并非为 一个字，FLF-字整个的长度为一个字，本段后文以及下一段中提到的 F-字与此处均相同)

前三位为字的类型标志位011，第四位为第一个F-字的类型(0 为0-Fill,1为1-Fill.下同)，第五位为第二个F-字的类型，第六位为 NI-L块的类型(0为0-NI-L-块，1为1-NI-L-块)，第七、八位为差异 位所在字节的位置(从00到11，可表示四个字节)。第二个字节(9-16 位)为第一个F-字的计数器，第三个字节(17-24位)为NL-块的差 异字节(dirty byte,如果为第一个字节，则在最高位补一位，内容为 NI-L块对应的类型，如果是其余三个字节中的一个的话原样复制即 可)。

图9是通过COMPAX和ICX算法将原比特序列编码为FLF。

图10是用ICX将原比特序列编码为FLF，用COMPAX将原比 特序列编码为一个F字+一个L字+一个F字。ICX能够将原比特序 列编码为FLF，但是由于原比特序列不满足COMPAX对于FLF的定 义，COMPAX无法将原比特序列编码为FLF，只能编码为一个F字+ 一个L字+一个F字。

4.一个LFL-字是对满足如下条件的块的组合进行编码：[一个 NI-L-块]-[1个或多个F-块(或者直接称作F-字)]-[一个NI-L块].

由于两个NL-块的类型不一定一致，因此前三位分配了两种编码 方法：001表示两个NI-L-块类型相同，010表示两个NI-L-块类型不 同。但二者仅在第四位的含义上有差别：

对于001-：第四位表示两个NI-L块的类型。为0表示均为0-NI-L 块，为1表示均为1-NI-L块。

对于010-：第四位为0表示第一个为0-NI-L-块，第二个为1-NI-L 块；第四位为1表示第一个为1-NI-L块，第二个为0-NI-L块。0为 0-NI-L块，1为1-NI-L块。

第5-6位表示第一个NI-L块的差异位所在字节的位置(00-11), 第7-8位表示第二个NI-L块差异位所在字节的位置。第9-16位为第 一个NI-L块的差异字节(dirty byte,与FLF中的复制方式相同)，第17 位为F-字类型标志位，第18-24位为F-字的计数器，第25-32位为第 二个NI-L块的差异字节(dirty byte，与上文中的复制方式相同).

例如：

(1)图11是可以被COMPAX和ICX两种方式编码为LFL的一 个原比特序列。它符合符合COMPAX和ICX对于LFL的定义，因 此可以被两种方式编码。这里解释ICX的编码。由于从原比特序列 可看出两个NI-L块均为0-NI-L块，因此为0；第5-6位标志第一个 NI-L块差异字节位置，此处为01；第7-8位表示第二个NI-L块的差 异字节位置，此处为11(需要在填入第二个NI-L块差异字节时补上 NI-L块类型，对于本例相当于在第25位填0)。第17位标示F-字的 类型，此处为0。

(2)图12是不可以被COMPAX方式编码为LFL，只能被ICX 编码为LFL的一个原比特序列。此时COMPAX无法将其归入LFL 类。图13是图12中的原比特序列被COMPAX编码的结果。 可以看出，COMPAX将其编为Literal Word+1-Fill Word+Literal  Word。而ICX可以将其归入LFL类型，因此此时ICX比COMPAX 有更好的编码效率。

(3)图14是不可以被COMPAX方式编码为LFL，只能被ICX 编码为LFL的一个原比特序列。图15是图14中的原比特序列被 COMPAX编码的结果。此时ICX比COMPAX有更好的编码效率。

由上述(1)(2)(3)的例子可以看出当原比特序列只能被ICX 编码为LFL，不可以被COMPAX编码为LFL时，ICX比COMPAX 有更好的编码效率。

5.一个NI-FL字是对满足如下条件的块的组合进行编码：[一个 NI-LF块]-[一个或者多个同类型F块(即1个F字)]。对于一个NI-FL 字，前五位为类型标志位00001，第六位表示NI-L块的类型，第七、 第八位表示NI-L块的差异位所在字节的位置，第9-16位为NI-L的 差异位，第17位为Fill Word的类型，第18-32位作为Fill Word的计 数器。

由于编码过程中NI-FL字和FLF字的判断可能产生部分重叠， 现将二者的编码过程区分如下：

如果出现NI-L类型下一个是Fill：先判断计数器大小，如果小于 128，且再下一个是NI-L类型，将这三个块编码成LFL；否则再考虑 压缩成LF类型；如果上述情况均不满足，则为L和F分开的类型。 图16是NI-L类型且第二个是Fill时编码的流程图。

下面举例说明。

图17是无法被WAH和COMPAX进行编码的一个原比特序列。 由于WAH和COMPAX都无法对原比特序列进行编码，只能将图17 中的原比特序列编码为一个L字+一个F字+一个L字的形式，但原 比特序列能够满足ICX中对于NI-FL的定义，因此ICX将其编码为 一个NI-FL字+一个L字，此时能够看出ICX相比于COMPAX有着 更高的编码效率。

6.一个NI2-FL字对于满足如下条件的块的组合进行编码：[一个 NI2-LF块]-[一个或多个同类型的F-块].前四位为类型标志位0001， 第五位为NI2-LF块的类型，第6-8位通过一定的编码方式来标示两 个差异位的位置。图18是NI2-FL字编码中第6-8位的编码规则。

第9-16位为第一个差异位的内容，第17-24位为第二个差异位 的内容，第25位为Fill Word的类型，第26-32位为Fill Word的计数 器。

下面举例说明：

图19是无法被WAH和COMPAX进行编码的一个原比特序列。 由于WAH和COMPAX都没有办法对于原比特序列进行压缩，只能 编成一个L字+一个F字的形式，而ICX能够将原比特序列压缩成一 个NI2-LF字的形式。

图20是ICX的码本。

由上面的具体实施例可以看出ICX是以COMPAX为基础进行了 改进，ICX的优点如下所示：

1.对于FLF字情况：

COMPAX只能处理两个F-字属于同种类且L-块为0-NI-L块的情 况(事实上，COMPAX没有考虑1-NI-L块的所有情况)，而ICX对 于F-字是否同种类，以及NI-L块的类型没有要求，这样相当于扩展 了大约三倍的可编码情况数(假定0-F字出现的概率和1-F字出现的 概率相近，1-NI-L块和0-NI-L块出现的概率相近)。

而在ICX可以处理而COMPAX无法处理的情况时COMPAX的 编码效率退化成WAH(如FLF中的例2)。也就是说ICX比COMPAX 有着更好的编码效率。

2.对于LFL字情况：

COMPAX只能处理两个L同为0-NI-L块这种情况，而ICX对于 NI-L的种类没有要求，这样相当于扩展了三倍的可编码情况数(假 定1-NI-L块和0-NI-L块出现的概率相近，1-NI2-L块和0-NI2-L块 出现的概率相近)。

3.对于NI-LF字的情况

如果无法满足LFL字，ICX可以对于NI-LF字这种情况进行处 理，而COMPAX则直接编码成一个L字+一个F字。

4.对于NI2-LF字的情况

COMPAX中没有对于NI2-LF块的定义，因此无法对于这种情况 进行进一步的压缩，而ICX对于这种情况进行了考虑并且可以将这 两部分合并成为一个字。

在上述ICX可处理而COMPAX无法处理的情况时，COMPAX 的编码效率退化成WAH(如LFL中的例(2)、(3))。

也就是说ICX比COMPAX有更好的编码效率。

因此可知，对于互联网流量大数据检索系统中的位图索引构建模 块，ICX编码的效率比COMPAX更高。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范 围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技 术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围 之内。因此，本发明的保护范围应该以权利要求的保护范围为准。