題目
字符串“alibaba”的二進制哈弗曼編碼有_位？
A、11 B、12 C、13 D、14
哈夫曼編碼(Huffman Coding)
是一種編碼方式，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼。
具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率 和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成1。每次相 加時都將“0”和“1”賦與相加的兩個概率，讀出時由該符號開始一直走到最後的“1”， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的赫夫曼編碼。
那我們進行解題：
先列舉“alibaba”字符串中每個字符的個數和概率：
a 3 3/7
b 2 2/7
l 1 1/7
i 1 1/7
然後從小到大排列：
l i b a
然後構造哈夫曼樹
因此
a 二進制哈夫曼編碼表示為0 （1位）
b 二進制哈夫曼編碼表示為10（2位）
l 二進制哈夫曼編碼表示為110（3位）
i二進制哈夫曼編碼表示為111（3位）
因此字符串“alibaba”二進制哈夫曼編碼有
每個字符的個數*編碼長度之和即 1*3 +2*2+3*1+3*1 = 13位，選C。
分享到:
閱讀更多 明明如月學長 的文章
