問題:
用二進制來編碼字元串“abcdabaa”,需要能夠根據編碼,解碼回原來的字元串,最少需要多長的二進制字元串?
分析:
哈弗曼編碼根據字元出現的機率來構造平均長度最短的碼字,是一種文本壓縮算法。
1,先統計各字元出現的頻率;
2,構造哈弗曼樹,左邊為0,右邊為1,每次選取最小權的兩棵樹組成新樹,直到最終形成一棵最優哈弗曼編碼樹。
此題,
4個a, 2個b,1個c,1個d
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2QvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2Lc5WNXp1bwhVZyYUbhZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39TMzATMwYDN2EzMxETM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
第一次,挑兩個最小的 c 和 d
第二次,再挑選兩個最小的
最後,組成一棵哈弗曼編碼樹。
是以,a 的編碼是 0,b的編碼是 10, c 的編碼是110, d的編碼是111.
最短是 1*4 + 2*2 + 3*1 + 3*1 = 14.