[問題] 詭異的霍夫曼建樹編碼問題Orz

看板CSSE (電腦科學及軟體工程)作者hb0303 ( )時間19年前 (2005/04/21 00:31)推噓3(3推 0噓 8→)

留言11則, 2人參與討論串1/3 (看更多)

先說題目：E=24 A=21 H=16 C=14 B=10 D=7 F=4 G=4 先說原則：霍夫曼編碼是動態編碼，不同的人編，每個字所編出的位元碼甚至是位元碼長度都有可能不同，不過只要建樹編碼的過程方法正確，算出的平均編碼長度一定是相同的。問題：我學校教的建樹編碼的方法不同於一般大眾所用的。但用一般的方法和我學校教的方法算出的平均編碼長度竟然不同，是有其他原因還是真的是我的書寫錯和老師教錯？兩種方法分述如下，過程和答案都已確定無誤： ======================================================================== 最一般的方法是在建立霍夫曼樹中，往上建立父節點時，是選取所有可用自由點中最小的兩個值相加，也就是過程中一開始排序的leaf有可能會變動順序。上題例：一開始可做到 15 / \ 24 / 8 / \ / / \ E A H C B D F G 24 21 16 14 10 7 4 4 但在這之後，最小的兩個點是15和16(H)，所以要把H移到可和15建立父節點的地方變成 15 / \ 24 / 8 / \ / / \ E A C B D F G H 24 21 14 10 7 4 4 16 再來可直接做到root 100 / \ / 55 / / \ / / 31 / / / \ / / 15 \ / / / \ \ 45 24 / 8 \ / \ / \ / / \ \ E A C B D F G H 24 21 14 10 7 4 4 16 以這種方法，建立出來各字元的位元碼長度分別為 E:2 A:2 H:3 C:3 B:3 D:4 F:5 G:5 平均編碼長度是2.78個位元 ========================================================================== 另外一種方法是我學校教的，書是McGrawHill出版的Data communications and networks，方法是在建立霍夫曼樹中，往上建立父節點時，是選取所有可用自由點中任兩相鄰自由點相加最小的值相加，也就是過程中一開始排序的leaf不會再變動順序。用這種方式編碼此題可一次完成為(P.S這我們老師有給答案也確定是正確的，所以不懂這個算法的人可以直接看答案。)： 100 / \ / 39 / / \ 61 / 15 / \ / / \ / 37 24 / 8 / / \ / \ / / \ E A H C B D F G 24 21 16 14 10 7 4 4 以這種方法，建立出來各字元的位元碼長度分別為 E:2 A:3 H:3 C:3 B:3 D:3 F:4 G:4 平均編碼長度是2.84個位元 =========================================================================== 為什麼這兩種方法所算出的平均編碼長度是不同的呢？有人可以指出問題所在嗎？用各自的方法時，過程和答案都是正確的，那麼錯的是？每個人都說是我學的方法錯了，難到真的該去電老師了？Orz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.165.147.159