Question

给定某英文文本，采用哈夫曼编码方法时的总编码长度为________位？

给定某英文文本为“this_is_an_ideal_string”, 采用哈夫曼编码方法时的总编码长度为________位.
答案是79位，我想问是怎么算出来的？

Answer 1

79位，解法如下：

先统计一下每个字母的出现的次数：

t：2、h：1、i：4、s：3、a：2、n：2、d：1、e：1、l：1、r：1、g：1。

然后构造哈夫曼树：

23

/ \

15 8

/ \ / \

7 8 i4 _4

/ \ / \

s3 4 4 4

/ \ / \ / \

2 2 2 t2 a2 n2

/ \ / \ / \

h1 d1 e1 l1 r1 g1

所以对应的所有叶子结点的路径长度 * 出现次数 之和便是总编码长度。

WPL = 3 * 3 + 5* （1+1+1+1+1+1） + 4*（2+2+2） + 2*（4 + 4） = 79。

哈夫曼编码简介：

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

Answer 2

先统计一下每个字母的出现的次数
t:2 h:1 i: 4 s:3 _:4 a:2 n:2 d:1 e:1 l:1 r:1 g:1
然后构造哈夫曼树
23
/ \
15 8
/ \ / \
7 8 i4 _4
/ \ / \
s3 4 4 4
/ \ / \ / \
2 2 2 t2 a2 n2
/ \ / \ / \
h1 d1 e1 l1 r1 g1
所以对应的所有叶子结点的路径长度 * 出现次数 之和便是总编码长度
WPL = 3 * 3 + 5* （1+1+1+1+1+1） + 4*（2+2+2） + 2*（4 + 4） = 79