先说题目：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