2

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

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 返回的代码字都不相同——这不是我想要的！

4

1 回答 1

3

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

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']]
于 2013-10-31T15:24:28.067 回答