D-Gap压缩
By Minidxer | October 8, 2007
简介在某些情况下，bit块经常会有非随机分布格局，见下例：0001000111001111
这些可以用不同的形式来表示。最常见的是整型，每一位代表一个bit，比如：
{ 3, 7, 8, 9, 12, 13, 14, 15, 16 }
这是一串bit作为整数顺序存贮的数字
另一种常见的方式是使用D-Gap，顺便一提，BitMagic函数库使用的就是D-Gap。
什么是D-Gap压缩
在D-Gap压缩中，序列里的第一个整数总是1或0，作用相当于标志bit的开始。在上面的例子中第一位是0。在这个标志之后的整数代表之后每个等份连续bit块的长度。所有序列元素的总和除了开头的标志1或0代表了块的总长度。这种编码模式被称为RLE。之前例子的D-Gap形式如下。
{[0], 3, 1, 3, 3, 2, 4}
转变为三个0，一个1，三个0，三个1，两个0，四个1，或者如下：
000 1 000 111 00 1111
这种方法的优点
D-Gap的优点之一，我们能够在没有解码/解压缩的情况下执行所有的逻辑运算
举例来说，逻辑非（NOT）的运算。这是个简单的例子，我们只需要改变第一位标志位就能实现。NOT运算只需要改变开头第一位值而不需要改动其他的地方，可以简单迅速的完成。
逻辑与（AND）运算相对来说就比较复杂涉及到整数的操作。算法是通过依次融合两组整数数组里的整数，比较两者的长度。结果我们有了一个新长度的D-Gap块。这种方法对不同的数据产生不同的结果。如果D-Gap 块的层结构清晰，这个算法有惊人的表现。该算法在非压缩块中比迭代（iteration）和组合法（combination）更加快速。
逻辑或（OR）运算，是一系列非（NOT）和与（AND）的操作。换句话来说，
(X or Y) 和 (not(not(X) && not(Y)) 相同。
实施逻辑非（NOT）的操作是非常迅速的，结果基本是零耗时。
这种方法的缺点
这种方法的缺点在于寻找一个随机Bit时总要反复查找整个序列。查找一个Bit平均要遍历一半的块。使用一个简单的bit我们就能通过bitwise shifts精确定位，这是最简单最快速的方法
例如流水操作，选择连续bit并不是一个问题，因为我们总能记住当前位置。
设置和清除bit可能是个问题。举例来说，我们可能需要增加或减少一两个整数，但是如果所要改变的bit位于连接处（gap）的边缘，那我们不得不分裂原来的结构模式。这意味着我们需要释放大量内存后才能继续操作。这是是否能准确实现bit修改的一个问题。
然而，BitMagic library 能够适应处理此事。若D-Gap压缩模式效率低时，会自动关闭。软件以普通的向量继续工作，而不会产生任何影响。如果应用程序不需要大量的随机存取操作，我们能通过转换一些bit块变成D-Gap块从而实现bit优化。
优化D-Gap编码
正如现在所看到的D-Gap的主要缺点在于必须反复查找bit值。这意味存取时间和组成元素的数量成正比。假设O(N)，如果N很小那时间短，但随着它的增长，编码代价也趋于增高。
让我们来看看下面的例子
{[0], 3, 1, 3, 3, 2, 4}
和下面的例子是否相同？
{[0], 2, 3, 6, 9, 11, 15}
我们需要做什么？从第一个值开始从左至右把原有序列转化成等量的块，形成新的序列。每下一个GAP含有指示下一个GAP形式的坐标。公式：GAP(N) = GAP(N-1) + Length(GAP(N)) （和Fibornacci 很相似吧）
最重要的意义是，序列变得很整齐，有利于让我们抛弃线性搜索转而使用更加有效的二进制搜索。二进制搜索的bit预估存取时间大约是O(log(N))，其中N是实际列的长度（不会超过定额GAP块的长度）
物有所值否？
绝对值得，不过D-Gap的整体表现依赖于我们所要压缩的数据。
Fig. 1
假设bit分布如上图所示。在bit密度增长高于一定限度的区域D-Gap较为适用。在向量变得稀疏的地方同样适用。有时某些区域处于这两者之间处于非随机的平坦的结构部分成为压缩的内容。
使用这种方法很有效，D-Gap编码块尽量短以避免低性能。由于设置清理了随机bit，块最终得到分散，有效序列变得更长。因此，达到一定限度后，我们不该把块作为D-Gap。BitMagic library发现了这个问题，并转换块成为普通的bit块