Return 到原文 Python 遍历霍夫曼树

Question

我正在尝试在我的程序中使用 Huffman。我正在使用此代码 here 从输入文本生成代码。我按照他们的解释使用它，例如：

message='man the stand banana man'    
huffman.codebook(collections.Counter(message).items())

这将为文本生成一棵树并为每个字符分配代码。树显示为 dict.

huffTree= {'m': '0111', 'a': '10', 'n': '00', ' ': '111', 't': '1101', 'h': '0101', 'e': '0100', 's': '0110', 'd': '11001', 'b': '11000'}

我应用它来生成比特流：

bitStream = []
for ch in message:
     bitStream.append(huffTree[ch])

那么从句子生成的比特流是：011110001111101010101001110110110110001100111111000100010001011101111000

我现在要的是如何return遍历python中的树生成的码流到原文中。我尝试了很多方法来解决这个问题，但无济于事，而且这一步没有明确的解决方案。

Answer 1

知道霍夫曼编码是 prefix code 我们可以利用它来解码您的比特流：

# Create a lookup map
lookup = { v:k for k,v in huffTree.items()}

# The decode function
def huffman_decode(msg):                   
 left = 0
 decoded = ''
 for right in range(len(msg)+1):
     token = msg[left:right]
     if token in lookup:
         decoded += lookup[token]
         left = right
 return decoded

 huffman_decode(bitStream) #'man the stand banana man'

Return 到原文 Python 遍历霍夫曼树

Return to the Original Text by Traversing Huffman Tree in Python

huffman-code

python-3.x