python - 使用 Python 位串测量霍夫曼编码的效率

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

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

暗示编码版本比原始序列长 30%。

我不认为你想在这里使用 getsizeof -- 如果你想最小化 Python 对象的大小，你应该使用 getsizeof(sequence)同样，而不是 len。

相反，如果您想执行霍夫曼编码的目的，并最小化二进制表示，那么您想要对两者 使用len(假设序列表示为每个字符一个字节)。

所以，您的实际比率是 11/37。

我假设您正在使用霍夫曼编码作为练习，因为这似乎不是一种有效存储带有终止字符的四位代码的合乎逻辑的方法。至少使用算术编码会更好，这将允许您使用 base-5 编码而不是 base-2，这对于 5 个可能的字符是最佳的。

真的，我会假设在一个足够长的序列中值得压缩，有一个已知的 G:A:C:T 比率和/或固定长度的 2 位编码将同样有效(比率接近 1 :1:1:1) 因为您实际上并不需要对终止字符进行编码。