python - 为什么标签排列会产生不同的霍夫曼代码？

Question

我正在根据以下输入分布生成霍夫曼代码:

a = [(1,0.5),(0,0.25),(0,0.125),(0,0.125)]
b = [(0,0.5),(1,0.25),(0,0.125),(0,0.125)]

唯一的区别是 1 在不同的 bin 中。

然而，当我使用以下函数对这些进行编码时:

def encode(symbfreq):
    tree = [[wt, [sym, ""]] for sym, wt in symbfreq]
    heapq.heapify(tree)
    while len(tree)>1:
        lo, hi = heapq.heappop(tree), heapq.heappop(tree)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(tree, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(tree)[1:], key=lambda p: (len(p[-1]), p))

我得到了分布的不同代码字:

a = [[1, '1'], [0, '00'], [0, '010'], [0, '011']]

同时

b = [[0, '0'], [1, '11'], [0, '100'], [0, '101']]

为什么我会得到这种差异？

供引用:我需要将树分成左分支和右分支(基于左分支以 1 开头，右分支以 0 开头)以尝试找到 1。在第一种情况下，我的算法应该进行 1 次迭代，第二次进行 2 次迭代。但是，因为每次两个版本当前都进行 2 次迭代以找到 1，每个 bin 返回的代码字都不相同 - 这不是我想要的!

Answer 1

尽管它们看起来不同，但这个结果既正确又等价。

您可以通过对 lo 和 hi 分支进行排序使它们看起来相同，因此您总是通过替换将 1 添加到更大的分支:

lo, hi = heapq.heappop(tree), heapq.heappop(tree)

与:

lo, hi = sorted([heapq.heappop(tree), heapq.heappop(tree)], key=len)

结果

>>> encode(a)
3: [[1, '0'], [0, '10'], [0, '110'], [0, '111']]
>>> encode(b)
4: [[0, '0'], [1, '10'], [0, '110'], [0, '111']]