我正在编写一个代码,它为给定字母表中的符号序列生成哈夫曼代码。它通过一个构建节点的哈夫曼树的算法来实现这一点。每个节点都有一个来自此字母表的唯一符号,并且是叶节点,或者将其符号设置为None
,并且是父节点。所有节点都有一个表示从根节点到它的路径的代码。你知道吗
我现在尝试编写一个函数,通过执行以下操作对编码的符号序列进行解码:
""
x
个字符-x
是当前节点上该代码的长度x
字符x
字符以下是我尝试递归搜索的代码:
def decode(root, current, coded_sequence): # Initially called as decode(root, root, coded_sequence)
decoded_sequence = ""
for child in current.children:
if child.symbol and child.code == coded_sequence[:len(child.code)]:
decoded_sequence += child.symbol
coded_sequence = coded_sequence[len(child.code):] # Remove this matching code from the beginning of the coded sequence
decoded_sequence += decode(root, root, coded_sequence)
if child.children:
decoded_sequence += decode(root, child, coded_sequence) # Go back to the root of the tree with the new shortened coded_sequence
return decoded_sequence
我的算法是有效的,而且decoded_sequence
在开头有正确的解码序列,但后面是解码序列结尾的部分,我不知道为什么。为什么我的函数从我认为coded_sequence
现在将是空的开始继续呢?你知道吗
下面是一个示例输出:
下面是我对本例中使用的树的最佳表示:
Root
0/ 1|
X6 None
0/ 1|
X5 None
0/ 1|
X4 None
0/ 1|
X3 None
0/ 1|
X2 X1
解决方案
我想如果我换衣服会更干净
coded_sequence = coded_sequence[len(child.code):]
decoded_sequence += decode(root, root, coded_sequence)
至
decoded_sequence += decode(root, root, coded_sequence[len(child.code):])
这就完全解决了这个问题,我不能让我的头周围。。。你知道吗
目前没有回答
相关问题 更多 >
编程相关推荐