day9-哈夫曼樹

哈夫曼樹編碼

哈夫曼樹編碼可以很有效的壓縮數據，通常可以節省20%~90%的空間

根據每個字元的出現頻率，哈夫曼樹演算法構造出最優二進位表示

def find_min(freq):ntitem = min(freq,key=lambda i:i[0])ntfreq.remove(item)ntreturn itemnndef print_codes(tree,prefix=):ntif isinstance(tree,tuple):nttprint_codes(tree[0],prefix+0)nttprint_codes(tree[1],prefix+1)ntelse:nttprint(tree,prefix)nndef huffman_codes(text):ntfrom collections import Counterntfreq = [(i,x) for x,i in Counter(text).items()]nntwhile len(freq) > 1:nttli,lx = find_min(freq)nttri,rx = find_min(freq)nttfreq.append((li+ri,(lx,rx)))ntprint_codes(freq.pop()[1])nnif __name__ == __main__:ntx = astala vista tastanthuffman_codes(x)n

1. 首先將字元串進行統計
2. 找到最小頻率的2個字元，將其合併，並將頻率相加，字元串變用tuple進行表示
3. 當字典中只有一個的時候，將其列印出來。

推薦閱讀：