分层压缩
By Minidxer | October 8, 2007
※作者：BitMagic 翻译:丁志刚
Hierarchical Compression简介
通常用bit vectors来表示一系列数据。bit vector比linked list，array，red-black tree更加有效。bit vector能够很好的进行联合(unions)和交叉(intersections)的逻辑运算。以bit为单位能够最快的进行各种逻辑运算。
bit vector能够提供数据的随机存取，非常方便重要的开发设备。我们只需给每个对象一个唯一索引地址所以就可以了。
但是bit vector也有缺点，如果我们想要对一系列对象进行编码那么就需要成百上千的输入。传统的bit vector需要占用一定的内存并且所占内存大小取决于对象的大小。就这一点就使使用bit vector变得得不偿失。bit vector的数量越多就要求越大的存储空间。
比如，存贮4百万的 一个bitmap代表的任何一部分都需要488k大小的字节。即便我们仅仅保存100个这样大小的bit vector，也将需要48M。
很明显多数的应用程序并不能单纯使用bit vector。所以当我们在数据库中存储bit vector时就可以使用一些的压缩方法。比如arithmetic coding或者哈夫曼树(Huffman trees)。但是从数据库中读取压缩后的值有一定的困难。如果频繁的逻辑运算使用这种解压缩将耗费大量的时间。
大多数的应用程序并不需要保留随机信息。因此在很多应用程序中很少使用或者减少使用bit vector。但是bit vectors有一个特点就是在某些部分很稀疏但是在某些部分可以很紧密。因此可以利用bit vectors的这个特性用嵌入压缩使得bit vector实现高效率应用。
显而易见，设法组织bit vectors意味着我们必须在存贮空间和表现间做出选择。什么方法能够高效灵活的使用获得两者间的平衡。
一种选择就是使用hierarchical compression，现在就让我们来看看他是如何运行的。
Hierarchical Compression 分层压缩
Bit被分成了树形结构。树顶上的0代表它之后的所有子枝都是0。树顶上的1代表之后的子枝有非零的bit。对于第一种树顶是0的情况，我们不需要保存，因此可以大大的减少内存消耗。可能对于这样解释还有疑惑，下面的图示会帮你了解的更清楚。
Fig.1.
使用树形结构的BitMagic是一种高效率的分级压缩方法。
一个分枝使用三个点代替用bit vectors对高层编码，指针被广泛使用。空点用0表示，非空点用1表示。压缩树的深度很低是因为我们需要用来比较低的数目来找到bit值。如果向量稀疏，那么只需要查找上层根目录来确定是否有对象。
叶结点变成bit动态分配短块形成堆。如果有一块只包含一个bit，我们可以用static global memory替代。这种情况下，我们有效执行，如下图所示。
Fig. 2
如你所见，bit的存取内容被分割成大小相同的块，每一块完全独立于其他。我们就有能力操纵这些块，建立bit的平行计算应用，使用不同方法压缩块，内存中交换出非经常使用的块，集中块已提高内存的再配置操作。
Hierarchical Compression and Memory 分层压缩和内存
分层，bit的块节段组织扩展了编码地址空间到64位，可以有效的建立庞大的稀疏矩阵。大bit矩阵是个有趣的话题，适用于不同的压缩和块形成
Summary 小节
分层压缩是一种有效的灵活的操纵bit的方法，效率和空间的合理交换。
Topics:
数据压缩 |
Tags: bit vectors, Hierarchical Compression, 分层压缩