如何使用霍夫曼树获得正确的编码数据？

Question

我正在尝试使用霍夫曼树对字母进行编码。

我已经有了我的树，现在我得到了一串字符，我正在尝试使用树对其进行编码。

我不want/cannot使用dict()。

我运行遇到了问题。 b 应该被编码为 01 并用一个 b 尝试它我得到 0101010101 （好像有 5 b）

我的python代码：

def go_through_tree(huffmanTree, encod, el, result):
    """
    go through the tree returning the encoded element.
    """
    if huffmanTree.left == None and huffmanTree.right == None:
        letter = huffmanTree.key
        if letter == el:
            return encod
    else:
        child0 = huffmanTree.right
        child1 = huffmanTree.left
        result += go_through_tree(child0, encod + "0", el, result)
        result += go_through_tree(child1, encod + "1", el, result)
    return result

def encodedata(huffmanTree, dataIN):
    """
    Encodes the input string to its binary string representation.
    """
    result = ""
    for el in dataIN:
        result += go_through_tree(huffmanTree, "", el, "")
    return result

Answer 1

逻辑确实有问题。当匹配时，函数 returns 编码。在那种情况下 result 成为该编码。到目前为止，一切都很好。但随后我们到达了树中的另一片叶子，这次 if letter == el 为 False，因此函数只是 return 已经存在的 result。但现在问题来了：这个结果是 appended 我们已有的结果（使用 += 运算符）。这就是你重复的原因。

你应该在匹配后立即退出递归。无需继续搜索。

因此，您不需要 result 参数，当您得到返回结果时，您应该立即退出并将该结果传播给调用者。如果没有匹配项，return 空字符串。

def go_through_tree(huffmanTree, encod, el):
    if huffmanTree.left is None and huffmanTree.right is None:
        return encod if huffmanTree.key == el else ""  # Empty when no match
    else:
        # Return the first search that is successful (using OR):
        return (go_through_tree(huffmanTree.right, encod + "0", el)
             or go_through_tree(huffmanTree.left,  encod + "1", el))


def encodedata(huffmanTree, dataIN):
    return "".join(go_through_tree(huffmanTree, "", el) for el in dataIN)

如何使用霍夫曼树获得正确的编码数据？

How do get the correct encoded data with huffman tree?

python

tree

huffman-code