为什么标签排列会产生不同的哈夫曼码？

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在不同的箱子里。你知道吗

但是，当我使用以下函数对它们进行编码时：

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']]