作者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/cn.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