作者may87236 (慈)
看板Examination
標題[問題] 霍夫曼碼相同值的情況
時間Sun Apr 6 10:04:33 2014
非資訊背景,對這很不熟悉,希望能幫我解答!!
在霍夫曼樹的步驟中
1. 將出現頻率大小依序存入佇列
2. 取出頻率最小節點兩個合併
3. 合併之後將其頻率合放佇列(依順序大小,相同大小合併值會放後面)
4. 直到合併數=1
上課時老師也是說合併值放後面
但是WIKI裡的範例跟我解的不一樣
http://0rz.tw/MUZe9 (Fig.2霍夫曼編碼演算步驟)
2,3,4,4,5,7
2+3=5*(合併後的)
4,4,5,5*,7 -> 5,5*,7,8 這時候合併過後的節點(5*)不是應該在節點(5)右邊嗎?
希望有高手可以為我解惑!!> <
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.255.184.92
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Examination/M.1396749875.A.BA2.html
1F:推 gary22204:未看先答,霍夫曼碼大部分都不是唯一解,老王上課有說 04/06 10:57
2F:推 jdtrue:不是唯一解沒錯 但原po的問題跟這個無關 編碼過程要合乎規 04/06 11:10
3F:→ jdtrue:則不然不會是最短碼長 04/06 11:10
4F:推 gary22204:總之原PO就是困惑在第三點的順序,我覺得只要是從權重小 04/06 11:23
5F:→ gary22204:開始運算就可以得到最短碼長,至於順序就依照你看到的原 04/06 11:24
6F:→ gary22204:則做應該是不會錯的,因為樹不唯一所以我覺得都對 04/06 11:24
所以我想g大的意思是"合併值若遇相同值會放後面"這個準則並不是絕對
只要結果出來為最短碼長都是可以的,對吧!
※ 編輯: may87236 (111.255.184.92), 04/06/2014 12:12:45
7F:推 ao3100:答案不是唯一解,所以左右沒差,外部路徑權重一樣就可以 04/06 12:15
8F:→ may87236:感謝a大補充這點 這樣我更清楚了!!!^^ 04/06 21:22