使用Python bitstring测量哈夫曼编码效率

Question

我有一个字符串，想把它用霍夫曼编码压缩存储到一个位数组里：

>>> print sequence
GTCAGGACAAGAAAGACAANTCCAATTNACATTATG|

在这个sequence中，各个符号出现的频率是：

>>> print freqTuples
[(0.40540540540540543, 'A'), (0.1891891891891892, 'T'), (0.16216216216216217, 'C'), (0.16216216216216217, 'G'), (0.05405405405405406, 'N'), (0.02702702702702703, '|')]`

我把这些频率转化成了一个霍夫曼编码字典：

>>> print codeDict
{'A': '1', 'C': '010', 'G': '001', 'N': '0110', 'T': '000', '|': '0111'}

然后我使用Python的bitstring库，把这个字符串逐个字符地转换成了一个BitArray类的实例，我叫它bitArray，这个数组里包含了每个字符用对应的霍夫曼编码表示的位：

>>> print bitArray.bin
0b001000010100100110101100111100110101101100000100101100000001101010100000010000010111

这是以字节形式表示的位数组：

>>> print bitArray.tobytes()
!I\254\363[^D\260^Z\240Ap

我必须用tobytes()而不是bytes，因为我生成的位数组不能整除成8位的段。

当我计算BitArray表示的存储效率（即位数组和输入字符串大小的比率）时，发现效果比直接用原字符串还要差：

>>> sys.getsizeof(bitArray.tobytes()) / float(len(sequence))
1.2972972973

我这样计算存储效率对吗？（如果我编码更长的输入字符串，这个比率会改善，但似乎接近一个大约0.28的极限。我想确认这是不是正确的测量方式。）

编辑

以下两种方法得出的结果不同：

>>> print len(bitArray.tobytes()) / float(len(mergedSequence))
0.297297297297

>>> print bitArray.len / (8.*len(mergedSequence))
0.283783783784

我不太确定该相信哪个结果。不过在写数据到存储时，我觉得我需要字节表示，这让我更倾向于选择第一个结果。

Answer 1

你知道这个答案是错的，因为霍夫曼字典每个字符的位数少于4位，所以正确的答案应该小于0.5。如果字典和字符频率在更长的字符串中没有变化，那么随着字符串变长，压缩比不应该朝着某个极限减少。

根据sys的文档：

"getsizeof() calls the object’s __sizeof__ method and adds
 an additional garbage collector overhead if the object is
 managed by the garbage collector."

你需要一个函数，它返回的是比特串本身的长度，而不是比特串加上额外开销的长度。BitString的文档说，len或length属性返回的是以位为单位的长度。所以可以试试这样做：

bitArray.len / 8.*len(sequence)

Answer 2

我对bitarray的东西不是很了解，但你是不是可以直接这样做：

>>> len(bitArray.tobytes()) / float(len(sequence))

我不是说这样就能解决你的问题，但可能是“getsizeof”这个东西（我也不是特别熟悉）让你感到困惑。

根据你上面写的内容，看起来你有点像是在拿不同的东西做比较。

Answer 3

>>> sys.getsizeof(bitArray.tobytes()) / float(len(sequence))
1.2972972973

这意味着编码后的版本比原始序列要长30%。

我觉得你不应该在这里用 getsizeof -- 如果你想让Python对象的大小尽量小，应该用 getsizeof(sequence)，而不是 len。

如果你想实现霍夫曼编码的目的，尽量减少二进制表示的大小，那么你应该在两个上都使用 len（假设序列是每个字符占一个字节表示的）。

所以，你真正的比例是 11 / 37。

我猜你是在练习霍夫曼编码，因为这似乎不是一个有效存储仅仅是四位代码和一个结束字符的逻辑方法。至少使用算术编码会更好，这样你可以使用基数为5的编码，而不是基数为2的编码，这对于5个可能的字符是最优的。

实际上，我认为在一个足够长的序列中，值得进行压缩时，G:A:C:T的比例是已知的，或者固定长度的2位编码同样有效（比例接近1:1:1:1），因为你实际上并不需要编码结束字符。