将哈夫曼编码字符串转换为二进制

Question

我在用Python把霍夫曼编码的字符串转换成二进制时遇到了问题。

这个问题和霍夫曼算法本身没有关系。

情况是这样的：

我可以得到一个编码后的霍夫曼字符串，比如说 01010101010。注意，这只是一个字符串。

但现在我想把这个字符串的表示保存成真正的二进制。

在霍夫曼编码的字符串中，每个0和1代表一个字节。

我想要的是每个0和1代表一个位。

我该如何在Python中做到这一点呢？

编辑 1：

请原谅我没有清楚地描述我的问题。

让我解释一下我当前的写入0和1到二进制的方式。

假设我们有一个代码字符串 s='010101010'。

1. 我用 int 把它转换成整数。
2. 然后用 unichr 把它转换成字符串，这样我就可以写入文件了。
3. 以二进制模式把字符串写入文件。

还要注意的是，我需要读取这个文件来解码霍夫曼编码。

所以我的方法是：

1. 从文件中读取字节。
2. 把它们恢复成整数。
3. 把整数转换成它们的二进制表示字符串。
4. 解码这个字符串。

在第二步时，问题就出现了，我感到无从下手。

因为有些霍夫曼字符串可能很短（比如 10），而有些可能很长（010101010101001）。这导致它们在整数值中的字节长度不同（有些短字符串可能只占用一个字节，而长的可能占用两个甚至更多）。

下面的代码展示了我的问题：

ss=['010101','10010101010'] 
# first one is short and takes only one byte in its int value
# second one is long and takes two bytes   

print 'write it to file'
with open('binary.bin','wb') as f:
    for s in ss:
        n=int(s,2)
        print n
        s=unichr(n)
        f.write(s)

print 'read it to file'
with open('binary.bin','rb') as f:
    for s in f.read(): 
        print ord(s)

在第二个with部分，我一次读取一个字节，但这其实是不对的。因为字符串 10010101010 占用了两个字节。

那么，当我从文件中读取这些字节时，我一次应该读取多少字节呢？

Answer 1

你有一个字符串，需要把它转换成数字。int函数可以接受一个可选的'基数'作为参数。所以在你给出的字符串例子中，

>>> int('01010101010', 2)
682

一旦你得到了一个数字（而不是字符串），那么想要“真实”的二进制就没有意义了，因为这个数字是一样的，你可以用任何进制来显示它。这意味着二进制的100和十进制的4其实是同一个数字，在你的程序里它们并不是不同的数字。所以，一旦你把字符串变成了数字，你就可以对它的二进制位进行操作。

Answer 2

在Python中，有两种不同的“二进制”表示方式，你可能会想用到。

大数（Bignum）

一种是“大数”或任意精度整数。在Python 2.x中，这种类型叫做long，而在Python 3.x中叫做int。顾名思义，这种表示方式可以表示任意长度的整数，所以如果你打算对这个数字进行数学运算，这种方式就非常有用。如果你想把一串二进制数字转换成这种格式，可以使用

# Python 2
long(digit_str, 2)

或者

# Python 3
int(digit_str, 2)

bitstring库

另外，正如Marc B在评论中提到的，你也可以使用bitstring库。特别是对于转换，可以使用bitstring.pack函数。

在霍夫曼编码中，使用bitstring可能比用byte字符串来存储数据更好，因为霍夫曼编码通常不是8位的倍数；bitstring允许你处理任意长度的位字符串。缺点是：bitstring并不是标准库的一部分。

Answer 3

这里有一种可能的方法（使用 bitstring 库），虽然有些地方不太对，但还是有点道理：

使用 bitstring 库（感谢 Mechanical snail 和 Marc B）

来写入文件。

步骤：

1. 把普通文本编码成二进制字符串
2. 把所有这些字符串连接起来，形成一个更长的字符串
3. 使用 bitstring.BitArray 转换成十六进制格式
4. 把这个十六进制字符串写入文件

读取时：

1. 从文件中读取十六进制字符串
2. 使用 BitArray 把它转换回位字符串
3. 开始解码

代码：

ss=['01010100','10010101010','010101110101010101'] #encoded message


from bitstring import BitArray,BitStream
print 'write it to file'
with open('binary.bin','wb') as f:
    s=''.join(ss);
    b=BitArray(bin=s)                 
    f.write(b.tobytes())# thanks to Scott, tobytes() method is very useful

print 'read it to file'
b=BitArray(filename='binary.bin')
print b.bin