5

我有以下字符串，我想对其进行霍夫曼编码并有效地存储到一个位数组中：

>>> 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'}

然后，我使用 Pythonbitstring包将字符串逐个字符地转换为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

我不确定该相信哪个。但是在将数据写入存储的过程中，我认为我需要字节表示，这使我倾向于选择第一个结果。

4

3 回答 3

2

我不太确定 bitarray 的东西，但你不应该这样做：

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

我并不是说这会解决你的问题，但它可能是“getsizeof”的东西（同样，我不太熟悉的东西）让你失望。

从您在那里写的内容来看，您似乎有点将苹果与橙子进行比较。

于 2011-11-07T23:49:34.447 回答
2 
>>> 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) 因为您实际上并不需要对终止字符进行编码。

于 2011-11-07T23:52:28.097 回答
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 文档说lenorlength属性以位为单位返回长度。所以尝试这样做：

bitArray.len / 8.*len(sequence)
于 2011-11-08T00:06:24.597 回答