作者future1234 (Low)
看板TransCSI
標題Re: [問題] 數值表示範圍、unsigned int表示範圍、 …
時間Tue Oct 14 23:26:11 2008
: 3.Huffman Code到底要怎麼編碼呢? 之前補習的時候老師教的是
: Step1:找出每個符號出現的機率.
: Step2:合併出現機率最低的兩個符號,將出現機率相加,重複此Step
: 直到合併出最後一個符號(root)為止
: Step3:依據合併的關係,將合併出來的符號以1個bit表示.即是說一個符號用0表示
: 一個符號用1表示.
: 可是依照老師教的這個方式寫的話..有的時候寫出來的答案又跟解答不一樣.
: 或是可能會畫出兩種不一樣的圖案兩種不一樣的編碼...搞的我都不知道哪一個解法
: 是正確的. 有沒有板上的前輩可以教教我>"<
我拿我之前解過題目來說:
出現頻率
A: 12
B: 8
C: 9
D: 20
E: 31
F: 14
G: 8
{12,8,9,20,31,14,8} 拿來建Binary Tree , 樹不一定唯一 , 以下就是建好其中一棵
其中"/"為0 ,"\"為1
102
/ \
49 53
/ \ / \
20 29 31 22
/ \ / \ E / \
12 8 9 20 14 8
A B C D F G
編碼解果如下:
A 000
B 001
C 010
D 011
E 10
F 110
G 111
總bits= 12x3 + 8x3 + 9x3 + 20x3 + 31x2 + 14x3 + 8x3 = ...
所以你建另一棵B.T tree , 在算他們的總bits , 會發現都一樣
我想考試重點應該是看你的總bits是否相同 , 那代表有透過Huffman code的方法做正常的編碼
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51
1F：推 zptdaniel:future大..我就是這一題寫出兩種不一樣的答案||| 10/14 23:30
2F：→ future1234:所以你找的出第二棵 總bits不同的樹? 10/14 23:32
3F：→ future1234:這篇是錯的 請按頻率大小順序建樹 10/15 21:11