霍夫曼编码表本身的压缩

本座在做的是一个需要绞尽脑汁来提升数据传输速率的项目。如果能把传输的数据本身压缩到尽可能短，是很爽的。

这里面应用到了霍夫曼压缩方法，并且需要在双方每次会话之前传输新的霍夫曼编码表。这个霍夫曼编码表是按照一个字节可能有256个不同字节值的字典来生成的。在传输过程中按照(quint8,QBitArray)这样的值对来传输每个字节值的编码，前面一个表示字节值，后面一个表示编码。在做其它方面测试的时候，本座想到这个编码表本身是否可以压缩呢？于是做了一些思考和实验。

QDataStream中QBitArray的序列化结果是这样的：

QBitArray

•.•.序列的大小(quint32) •.•.序列的位，也就是说，(size + 7)/8個字节

由于这个霍夫曼编码算法是按照256个不同字节值的字典来生成编码表的，所以单个字节值的编码最长不会超过256个比特，这样，QBitArray序列的大小实际上只需要使用一个字节就能表示，Qt使用了4个字节，就有3个高位字节是全0.这是一处冗余信息的来源。

QBitArray中序列的所有比特在序列化之后要占用(size+7)/8个字节，因为QDataStream的序列化是以字节为单位的，不足一个字节的信息也要补足一个字节。因此在序列化过程中，遇到其尺寸不是8的倍数的QBitArray，就又有几个比特浪费了。这是又一处冗余（或者叫垃圾）信息的来源。

还有一点是本座的猜测，霍夫曼编码表的生成过程中会生成带权的二叉树，然后依据这个二叉树来生成编码表，叶子节点会用来表示字典中各个不同的字节值，而叶子节点的路径表示编码。这样，在二叉树上共享的祖宗越多的叶子节点之间，其编码中共同的前缀就越长。这是又一处冗余信息的来源。

另外，做了一上午的测试，把霍夫曼编码表序列化到QByteArray中去之后再用qCompress以最高级别压缩。每次测试结果，压缩之后的长度都只有未压缩后的长度的一半左右。所以这样压缩是确实有用的。

于是本座在项目中传输霍夫曼编码表的时候，都要压缩一下了。