使用Python位串测量Huffman编码的效率

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) 因为您实际上不需要对终止字符进行编码。