<p>使用<a href="https://pypi.python.org/pypi/bitarray/" rel="noreferrer">^{<cd1>}</a>模块,您可以免费获得huffman en-/de编码,而且可能比任何其他模块都更高效:</p>
<pre><code>from bitarray import bitarray
huffman_dict = {
'!': bitarray('01110'), 'B': bitarray('01111'),
'l': bitarray('10100'), 'q': bitarray('10110'),
'y': bitarray('10111')
}
a = bitarray()
a.encode(huffman_dict, 'Bylly!')
print(a)
dec = bitarray('011111011101110').decode(huffman_dict)
print(dec)
print(''.join(dec))
# # output:
# bitarray('011111011110100101001011101110')
# ['B', 'y', '!']
# By!
</code></pre>
<p>如果不想安装模块,请阅读下面的部分。</p>
<hr/>
<p>这里有一个使用<em>哈夫曼树</em>解码的变体-程序可以工作,但可能有更好的变体来表示二叉树(我选择了一个元组)。</p>
<p>当你的码字长度不同时,这个版本可能更适合。二叉树的另一个优点是代码显然没有前缀。</p>
<p>您的树形代码如下所示(为了使树结构可见而过度缩进):</p>
<pre><code>huffman_tree = \
( # 0
( # 00
None,
# 01
( # 010
None,
# 011
( # 0110
None,
# 0111
( # 01110
'!',
# 01111
'B')))),
# 1
( # 10
( # 100
None,
# 101
( # 1010
( # 10100
'l',
# 10101
None
),
# 1011
( # 10110
'q',
# 10111
'y'))),
# 11
None))
</code></pre>
<p>使用它,您可以解码:</p>
<pre><code>def huffman_decode(strg):
ret = ''
cur_node = huffman_tree
for char in strg:
cur_node = cur_node[int(char)]
if cur_node is None:
raise ValueError
elif isinstance(cur_node, str):
ret += cur_node
cur_node = huffman_tree
return ret
print(huffman_decode('011111011101110'))
</code></pre>
<p>如果解码命中<code>None</code>则会发生一些错误,并引发<code>ValueError</code>。一旦解码命中字符串,当前节点<code>cur_node</code>将重置为“根节点”,游戏从树的开头开始。</p>
<p>因为我可以:这里是一个可视化的哈夫曼树(不完整的)显示(这可能有助于理解算法的作用:每当你遇到一个<code>0</code>:向右+向下;每当你遇到一个<code>1</code>:向右+向上);如果你碰到一个结束节点:返回该节点的字符并在根节点重新启动。
<a href="https://i.stack.imgur.com/YoP4T.png" rel="noreferrer"><img src="https://i.stack.imgur.com/YoP4T.png" alt="binary huffman tree"/></a></p>