爲什麼標籤排列會產生不同的霍夫曼編碼？

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是在不同的箱中。

然而，當這些使用下面的函數I編碼：

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次迭代才能找到1 - 這不是我想要的結果，所以返回的代碼字不同。

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