看过谍战电影《风声》的观众都会对影片中神奇的消息传递惊叹不已！吴志国大队长在受了残忍的“针刑”之后躺在手术台上唱空城计，变了音调，把消息传给了护士，顾晓梦在衣服上缝补了长短不一的针脚……那么，片中无处不在的摩尔斯码到底是什么？它又有着怎样的神秘力量呢？

摩尔斯电码（Morse code）由点dot（. ）、划dash（-）两种符号组成。它的基本原理是：把英文字母表中的字母、标点符号和空格按照出现的频率排序，然后用点和划的组合来代表这些字母、标点符号和空格，使频率最高的符号具有最短的点划组合。

1 问题分析

我们先看一个生活中的例子：

有一群退休的老教授聚会，其中一个老教授带着刚会说话的漂亮小孙女，于是大家逗她：“你能猜猜我们多大了吗？猜对了有糖吃哦！”小女孩就开始猜：“你是1岁了吗？”，老教授摇摇头。“你是两岁了吗？”，老教授仍然摇摇头。“那一定是3岁了！”……大家哈哈大笑。或许我们都感觉到了小女孩的天真可爱，然而生活中的确有很多类似这样的判断。

曾经有这样一个C++设计题目：将一个班级的成绩从百分制转为等级制。一同学设计的程序为：

在上面程序中，如果分数小于60，我们做1次判定即可；如果分数为60～70，需要判定2次；如果分数为70～80，需要判定3次；如果分数为80～90，需要判定4次；如果分数为90～100，需要判定5次。

这段程序貌似是没有任何问题，但是我们却犯了从1岁开始判断一个老教授年龄的错误，因为我们的考试成绩往往是呈正态分布的，如图31所示。

也就是说，大多数（70%）人的成绩要判断3次或3次以上才能成功，假设班级人数为100人，则判定次数为：

100×10%×1+100×20%×2+100×40%×3+100×20%×4+100×10%×5=300（次）

如果我们改写程序为：

则判定次数为：

100×10%×3+100×20%×3+100×40%×2+100×20%×2+100×10%×2=230（次）

为什么会有这样大的差别呢？我们来看两种判断方式的树形图，如图32所示。

从图32中我们可以看到，当频率高的分数越靠近树根（先判断）时，我们只用1次猜中的可能性越大。

再看五笔字型的编码方式：

我们在学习五笔时，需要背一级简码。所谓一级简码，就是指25个汉字，对应着25个按键，打1个字母键再加1个空格键就可打出来相应的字。为什么要这样设置呢？因为根据文字统计，这25个汉字是使用频率最高的。

五笔字根之一级简码：

G 一 F 地 D 在 S 要 A 工

H 上 J 是 K 中 L 国 M 同

T 和 R 的 E 有 W 人 Q 我

Y 主 U 产 I 不 O 为 P 这

N 民 B 了 V 发 C 以 X 经

通常的编码方法有固定长度编码和不等长度编码两种。这是一个设计最优编码方案的问题，目的是使总码长度最短。这个问题利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需logn要位。例如，3个不同的字符a、b、c，至少需要2位二进制数表示，a为00，b为01，c为10。如果每个字符的使用频率相等，固定长度编码是空间效率最高的方法。

不等长编码方法需要解决两个关键问题：

（1）编码尽可能短

我们可以让使用频率高的字符编码较短，使用频率低的编码较长，这种方法可以提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。

（2）不能有二义性

例如，ABCD四个字符如果编码如下。

A：0B：1C：01D：10

那么现在有一列数0110，该怎样翻译呢？是翻译为ABBA，ABD，CBA，还是CD？那么如何消除二义性呢？解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。

1952年，数学家D.A.Huffman提出了根据字符在文件中出现的频率，用0、1的数字串表示各字符的最佳编码方式，称为哈夫曼（Huffman）编码。哈夫曼编码很好地解决了上述两个关键问题，被广泛应用于数据压缩，尤其是远距离通信和大容量数据存储方面，常用的JPEG图片就是采用哈夫曼编码压缩的（图片的许多像素值是相同的，如果出现频率高的像素值，采用较短的编码，则需要的字节数较少）。

2 算法设计

哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权值，以自底向上的方式，通过n-1次的“合并”运算后构造出的一棵树，核心思想是权值越大的叶子离根越近。

哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中，求解步骤如下。

2.1 确定合适的数据结构。编写程序前需要考虑的情况有：

哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点（n-1次的“合并”，每次产生一个新结点），

构成哈夫曼树后，为求编码，需从叶子结点出发走一条从叶子到根的路径。

译码需要从根出发走一条从根到叶子的路径，那么我们需要知道每个结点的权值、双亲、左孩子、右孩子和结点的信息。

2.2 初始化。构造n棵结点为n个字符的单结点树集合T={t1，t2，t3，…，tn}，每棵树只有一个带权的根结点，权值为该字符的使用频率。

2.3 如果T中只剩下一棵树，则哈夫曼树构造成功，跳到步骤（6）。否则，从集合T中取出没有双亲且权值最小的两棵树ti和tj，将它们合并成一棵新树zk，新树的左孩子为ti，右孩子为tj，zk的权值为ti和tj的权值之和。

2.4 从集合T中删去ti，tj，加入zk。

2.5 重复以上（3）～（4）步。

2.6 约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。算法结束。

3 完美图解

假设我们现在有一些字符和它们的使用频率，如何得到它们的哈夫曼编码呢？

我们可以把每一个字符作为叶子，它们对应的频率作为其权值，为了比较大小方便，可以对其同时扩大100倍，得到a～f分别对应5、32、18、7、25、13。

3.1 初始化。构造n棵结点为n个字符的单结点树集合T={a，b，c，d，e，f}，如图33所示↑。

3.2 从集合T中取出没有双亲的且权值最小的两棵树a和d，将它们合并成一棵新树t1，新树的左孩子为a，右孩子为d，新树的权值为a和d的权值之和为12。新树的树根t1加入集合T，a和d从集合T中删除，如图34所示。

3.3 从集合T中取出没有双亲的且权值最小的两棵树t1和f，将它们合并成一棵新树t2，新树的左孩子为t1，右孩子为f，新树的权值为t1和f的权值之和为25。新树的树根t2加入集合T，将t1和f从集合T中删除，如图35所示↑。

3.4 从集合T中取出没有双亲且权值最小的两棵树c和e，将它们合并成一棵新树t3，新树的左孩子为c，右孩子为e，新树的权值为c和e的权值之和为43。新树的树根t3加入集合T，将c和e从集合T中删除，如图36所示↑。

3.5 从集合T中取出没有双亲且权值最小的两棵树t2和b，将它们合并成一棵新树t4，新树的左孩子为t2，右孩子为b，新树的权值为t2和b的权值之和为57。新树的树根t4加入集合T，将t2和b从集合T中删除，如图37所示。

3.6 从集合T中取出没有双亲且权值最小的两棵树t3和t4，将它们合并成一棵新树t5，新树的左孩子为t4，右孩子为t3，新树的权值为t3和t4的权值之和为 100。新树的树根t5加入集合T，将t3和t4从集合T中删除，如图 38所示↑。

3.7 T中只剩下一棵树，哈夫曼树构造成功。

3.8 约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码，如图39所示。

4 伪代码详解

在构造哈夫曼树的过程中，首先给每个结点的双亲、左孩子、右孩子初始化为-1，找出所有结点中双亲为-1、权值最小的两个结点t1、t2，并合并为一棵二叉树，更新信息（双亲结点的权值为t1、t2权值之和，其左孩子为权值最小的结点t1，右孩子为次小的结点t2，t1、t2的双亲为双亲结点的编号）。重复此过程，构造一棵哈夫曼树。

4.1 数据结构

每个结点的结构包括权值、双亲、左孩子、右孩子、结点字符信息这 5 个域。如图 40所示，定义为结构体形式，定义结点结构体HnodeType：

typedef struct{double weight; //权值int parent; //双亲int lchild; //左孩子int rchild; //右孩子char value; //该节点表示的字符} HNodeType;

在编码结构体中，bit[]存放结点的编码，start记录编码开始下标，逆向译码（从叶子到根，想一想为什么不从根到叶子呢？）。存储时，start从n-1开始依次递减，从后向前存储；读取时，从start+1开始到n-1，从前向后输出，即为该字符的编码。如图41所示↑。

编码结构体HcodeType：

typedef struct{int bit[MAXBIT]; //存储编码的数组int start; //编码开始下标} HCodeType; /* 编码结构体 */

4.2 初始化

初始化存放哈夫曼树数组HuffNode[]中的结点（见表14）：

for (i=0; i<2*n-1; i++){HuffNode[i].weight = 0;//权值HuffNode[i].parent =-1; //双亲HuffNode[i].lchild =-1; //左孩子HuffNode[i].rchild =-1; //右孩子}

输入n个叶子结点的字符及权值：

for (i=0; i<n; i++){cout<<"Please input value and weight of leaf node "<<i + 1<<endl;cin>>HuffNode[i].value>>HuffNode[i].weight;}

4.3 循环构造Huffman树

从集合T中取出双亲为-1且权值最小的两棵树 ti 和 tj，将它们合并成一棵新树 zk，新树的左孩子为 ti，右孩子为 tj，zk的权值为 ti 和 tj 的权值之和。

图解：

4.3.1 i=0时，j=0；j<6；找双亲为-1，权值最小的两个数：

x1=0 x2=3；//x1、x2为两个最小权值结点的序号m1=5 m2=7；//m1、m2为两个最小权值结点的权值HuffNode[0].parent = 6; //x1的父亲为新结点编号n+iHuffNode[3].parent = 6; //x2的父亲为新结点编号n+iHuffNode[6].weight =12; //新结点权值为两个最小权值之和m1+m2HuffNode[6].lchild = 0; //新结点n+i的左孩子为x1HuffNode[6].rchild = 3; //新结点n+i的右孩子为x2

数据更新后如表15所示。

对应的哈夫曼树如图42所示。

4.3.2 i=1时，j=0；j<7；找双亲为-1，权值最小的两个数：

x1=6 x2=5；//x1、x2为两个最小权值结点的序号m1=12 m2=13；//m1、m2为两个最小权值结点的权值HuffNode[5].parent = 7; //x1的父亲为新结点编号n+iHuffNode[6].parent = 7; //x2的父亲为新结点编号n+iHuffNode[7].weight =25; //新结点权值为两个最小权值之和m1+m2HuffNode[7].lchild = 6; //新结点n+i的左孩子为x1HuffNode[7].rchild = 5; //新结点n+i的右孩子为x2

数据更新后如表16所示。

对应的哈夫曼树如图43所示。

4.3.3 i=2时，j=0；j<8；找双亲为-1，权值最小的两个数：

x1=2 x2=4；//x1、x2为两个最小权值结点的序号m1=18 m2=25；//m1、m2为两个最小权值结点的权值HuffNode[2].parent = 8; //x1的父亲为新结点编号n+iHuffNode[4].parent = 8; //x2的父亲为新结点编号n+iHuffNode[8].weight =43; //新结点权值为两个最小权值之和m1+m2HuffNode[8].lchild = 2; //新结点n+i的左孩子为x1HuffNode[8].rchild = 4; //新结点n+i的右孩子为x2

数据更新后如表17所示。

对应的哈夫曼树如图44所示。

4.3.4 i=3时，j=0；j<9；找双亲为-1，权值最小的两个数：

x1=7 x2=1；//x1、x2为两个最小权值结点的序号m1=25 m2=32；//m1、m2为两个最小权值结点的权值HuffNode[7].parent = 9; //x1的父亲为新结点编号n+iHuffNode[1].parent = 9; //x2的父亲为新结点编号n+iHuffNode[8].weight =57; //新结点权值为两个最小权值之和m1+m2HuffNode[8].lchild = 7; //新结点n+i的左孩子为x1HuffNode[8].rchild = 1; //新结点n+i的右孩子为x2

数据更新后如表18所示。

对应的哈夫曼树如图45所示。

4.3.5 i=4时，j=0；j<10；找双亲为-1，权值最小的两个数：

x1=8 x2=9；//x1、x2为两个最小权值结点的序号m1=43 m2=57；//m1、m2为两个最小权值结点的权值HuffNode[8].parent = 10; //x1的父亲为生成的新结点编号n+iHuffNode[9].parent =10; //x2的父亲为生成的新结点编号n+iHuffNode[10].weight =100; //新结点权值为两个最小权值之和m1+ m2HuffNode[10].lchild = 8; //新结点编号n+i的左孩子为x1HuffNode[10].rchild = 9; //新结点编号n+i的右孩子为x2

数据更新后如表19所示。

对应的哈夫曼树如图46所示。

4.3.6 输出哈夫曼编码

图解：

哈夫曼编码数组如图47所示。

① i=0时，c=0；

cd.start = n-1=5;p = HuffNode[0].parent=6;//从哈夫曼树建成后的表HuffNode[]中读出//p指向0号结点的父亲6号

构建完成的哈夫曼树数组如表20所示。

如果p != -1（p=-1时为根结点），那么从表HuffNode[]中读出6号结点的左孩子和右孩子，判断0号结点是它的左孩子还是右孩子，如果是左孩子编码为0；如果是右孩子编码为1。

从表20可以看出：

HuffNode[6].lchild=0;//0号结点是其父亲6号的左孩子cd.bit[5] = 0;//编码为0cd.start--=4; /* start向前移动一位*/

哈夫曼编码树如图48所示，哈夫曼编码数组如图49所示。

c = p=6; /* c、p变量上移，准备下一循环 */p = HuffNode[6].parent=7;

② c、p变量上移后如图50所示。

p != -1;

HuffNode[7].lchild=6;//6号结点是其父亲7号的左孩子

cd.bit[4] = 0;//编码为0

cd.start--=3; /* start向前移动一位*/

c = p=7; /* c、p变量上移，准备下一循环 */

p = HuffNode[7].parent=9;

③ 哈夫曼编码树如图51所示↑，哈夫曼编码数组如图52所示↑。

p != -1;HuffNode[9].lchild=7;//7号结点是其父亲9号的左孩子cd.bit[3] = 0;//编码为0cd.start--=2; /* start向前移动一位*/c = p=9; /* c、p变量上移，准备下一循环 */p = HuffNode[9].parent=10;

④ 哈夫曼编码树如图53所示，哈夫曼编码数组如图54所示。

p != -1;HuffNode[10].lchild!=9;//9号结点不是其父亲10号的左孩子cd.bit[2] = 1;//编码为1cd.start--=1; /* start向前移动一位*/c = p=10; /* c、p变量上移，准备下一循环 */p = HuffNode[10].parent=-1;

⑤ 哈夫曼编码树如图55所示↑，哈夫曼编码数组如图56所示。

p = -1;该叶子结点编码结束。

/* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */for (j=cd.start+1; j<n; j++)HuffCode[i].bit[j] = cd.bit[j];HuffCode[i].start = cd.start;

HuffCode[]数组如图57所示↑。

注意：图中的箭头不表示指针。

5　代码

输入

Please input n：

6

Please input value and weight of leaf node 1

a 0.05

Please input value and weight of leaf node 2

b 0.32

Please input value and weight of leaf node 3

c 0.18

Please input value and weight of leaf node 4

d 0.07

Please input value and weight of leaf node 5

e 0.25

Please input value and weight of leaf node 6

f 0.13

输出x1.weight and x2.weight in round 1 0.05 0.07x1.weight and x2.weight in round 2 0.12 0.13x1.weight and x2.weight in round 3 0.18 0.25x1.weight and x2.weight in round 4 0.25 0.32x1.weight and x2.weight in round 5 0.43 0.57a: Huffman code is: 1000b: Huffman code is: 11c: Huffman code is: 00d: Huffman code is: 1001e: Huffman code is: 01f: Huffman code is: 101

再回过头来认识Huffman编码，再来看一下6个字符及其使用频率的列表：

首先是六个字符的编码没有二义性，任何一个字符的编码都不是其它编码的前缀，这样字符排列在一起就不会引起歧义，如0010001001，只能解码为cad。

其次，使用频率最高的采用二位编码，使用频率最低的采用四位编码，体现了“频率越高、编码越短”的原则。

6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：由程序可以看出，在函数HuffmanTree()中，if (HuffNode[j].weight<m1&& HuffNode[j].parent==-1)为基本语句，外层i与j组成双层循环：

i=0时，该语句执行n次；i=1时，该语句执行n+1次；i=2时，该语句执行n+2次；……i=n-2时，该语句执行n+n-2次；

则基本语句共执行n+（n+1）+（n+2）+…+（n+（n-2））=（n-1）*（3n-2）/2次（等差数列）；在函数HuffmanCode()中，编码和输出编码时间复杂度都接近n2；则该算法时间复杂度为O(n2)。

（2）空间复杂度：所需存储空间为结点结构体数组与编码结构体数组，哈夫曼树数组?HuffNode[]中的结点为n个，每个结点包含bit[MAXBIT]和start两个域，则该算法空间复杂度为O(n* MAXBIT)。

2．算法优化拓展

该算法可以从两个方面优化：

（1）函数HuffmanTree()中找两个权值最小结点时使用优先队列，时间复杂度为logn，执行n-1次，总时间复杂度为O( n logn)。

（2）函数HuffmanCode()中，哈夫曼编码数组HuffNode[]中可以定义一个动态分配空间的线性表来存储编码，每个线性表的长度为实际的编码长度，这样可以大大节省空间。

参考：

附代码

#include<iostream>#include<algorithm>#include<cstring>#include<cstdlib>using namespace std;#define MAXBIT 100#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1typedef struct{	double weight;	int parent;	int lchild;	int rchild;	char value;} HNodeType; /* 结点结构体 */typedef struct{	int bit[MAXBIT];	int start;} HCodeType; /* 编码结构体 */HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */HCodeType HuffCode[MAXLEAF];/* 定义一个编码结构体数组*//* 构造哈夫曼树 */void HuffmanTree (HNodeType HuffNode[MAXNODE], int n){/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。	*/	int i, j, x1, x2;	double m1,m2;	/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */	for (i=0; i<2*n-1; i++)	{		HuffNode[i].weight = 0;//权值		HuffNode[i].parent =-1;		HuffNode[i].lchild =-1;		HuffNode[i].rchild =-1;	}	/* 输入 n 个叶子结点的权值 */	for (i=0; i<n; i++)	{		cout<<"Please input value and weight of leaf node "<<i + 1<<endl;		cin>>HuffNode[i].value>>HuffNode[i].weight;	}	/* 构造 Huffman 树 */	for (i=0; i<n-1; i++)	{//执行n-1次合并		m1=m2=MAXVALUE;		/* m1、m2中存放两个无父结点且结点权值最小的两个结点 */		x1=x2=-1;/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */		for (j=0; j<n+i; j++)		{			if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)			{				m2 = m1;				x2 = x1;				m1 = HuffNode[j].weight;				x1 = j;			}			else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)			{				m2=HuffNode[j].weight;				x2=j;			}		}		/* 设置找到的两个子结点 x1、x2 的父结点信息 */		HuffNode[x1].parent = n+i;		HuffNode[x2].parent = n+i;		HuffNode[n+i].weight = m1+m2;		HuffNode[n+i].lchild = x1;		HuffNode[n+i].rchild = x2;		cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<< \HuffNode[x1]. weight<<"\t"<<HuffNode[x2].weight<<endl; /* 用于测试 */	}}/* 哈夫曼树编码 */void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n){	HCodeType cd; /* 定义一个临时变量来存放求解编码时的信息 */	int i,j,c,p;	for(i = 0;i < n; i++)	{		cd.start = n-1;		c = i;		p = HuffNode[c].parent;		while(p != -1)		{			if(HuffNode[p].lchild == c)				cd.bit[cd.start] = 0;			else				cd.bit[cd.start] = 1;			cd.start--; /* 求编码的低一位 */			c = p;			p = HuffNode[c].parent; /* 设置下一循环条件 */		}/* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */		for (j=cd.start+1; j<n; j++)			HuffCode[i].bit[j] = cd.bit[j];		HuffCode[i].start = cd.start;	}}int main(){	int i,j,n;	cout<<"Please input n："<<endl;	cin>>n;	HuffmanTree (HuffNode, n); /* 构造哈夫曼树 */	HuffmanCode(HuffCode, n); /* 哈夫曼树编码 */	/* 输出已保存好的所有存在编码的哈夫曼编码 */	for(i = 0;i < n;i++)	{		cout<<HuffNode[i].value<<": Huffman code is: ";		for(j=HuffCode[i].start+1; j < n; j++)			cout<<HuffCode[i].bit[j];		cout<<endl;	}	system("pause");	return 0;}

－End－