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

[hb0303 ( )]

先說題目：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
推 jeunder:第二種方法是犧牲"壓縮效率"來增進"編碼效率"
→ jeunder:也就是說重點擺在->減少編碼時期的執行花費時間
→ jeunder:所以不是"最佳的編碼"(不是最短的平均長度)
推 jeunder:第一個方法要 O(n^2), 第二方法要 O(n)
→ jeunder:介於中間的方法, 可以考慮使用 min-heap
→ jeunder:需要 O(nlogn)
→ jeunder:不過第二個方法還要考慮排序所花的時間, 所以其
→ jeunder:實也是 O(nlogn)~~~  我發現不小心推文太長了 XD
→ jeunder:所以其實還是使用 min-heap 比較好, 執行時間與
→ jeunder:平均編碼長度可兼顧
推 hb0303:拜讀受教了<(_ _)>