※ 引述《jolinboyfrie (宇)》之銘言：
: 請教一下各位題目如下
: 在一個以英文字母 A、B、C、D、E 組成的檔案裡,各字母出現的次數分別為:A=250 次,
: B=1000 次,C=200 次,D=250 次,E=500 次。如利用 Huffman 編碼(Huffman encoding),
: 則記錄此檔案 (不計算記錄對應之 Huffman 樹本身)共需要使用多少個位元(bits)?
: 答案4550
: 像這種題目他不是問我編出來是多少,而是問總共要多少bits要如何計算啊？
: 如果遇到2個頻率是一樣的時候該怎麼處理阿?
: 謝謝
如題
畫個圖出來應該會比較好解題
如果頻率一樣 要假設是依據甚麼犯斷方式來處理
假設如果一樣的話依字母順序來排(A>D)
但是這題沒有問你編碼多少
只問你是總共bits
所以頻率一樣是不影響答案的
畫出來的huffman樹應該是
2200
/ \
0/ \1
/ \
/ \
1000(B) 1200
/ \
0 / \1
/ \
/ \
500(E) 700
/ \
0/ \1
/ \
/ \
250(D) 450
/ \
0/ \1
/ \
/ \
200(C) 250(A)
符號 編碼 位元數 次數
A 1111 4 250
B 0 1 1000
C 1110 4 200
D 110 3 250
E 10 2 500
總共編碼=次數*位元數 250*4+1000*1+200*4+250*3+500*1=4550