計算機概論 huffman 編碼問題 - 考試

※ 引述《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

--
█ █ ████ ▁▃▄▅▆▇█
█ █ █ █ ▊
█ █ █ ▋
█ █ █ █ ▌▂▃▄▅ ▁
█ █ █ █ █ █ ▍ ▕飛▏
█ █ ████ ▎ ￣

--