哈夫曼编码与哈夫曼树详解
哈夫曼编码与哈夫曼树详解
哈夫曼编码是一种用于数据压缩的编码方式，通过构建哈夫曼树来实现。本文将详细介绍哈夫曼编码的原理、构造方法以及哈夫曼树的相关性质。
编码问题
现思考下面的一个问题：现有字符串ABACACD，如果需要对四个字符A、B、C、D用二进制进行编码，问如何能使字符串编码长度最小且不出现歧义。
普通编码
最容易想到的方法如下：
A-0 B-1 C-10 D-11
这种编码方式符合思维惯性，每一个字符是其前面的编码+1，但是这样编出来的码会有一点问题。根据这种方法，字符串ABACACD表示为0101011011，很明显可以看出0101011011无法逆着推出原字符串ABACACD。比如0101011011可以视为0101011011，即ABABADAD。
为什么会出现这种情况呢？原因很简单，就是被编码的字符中出现了某一个字符是另一个字符的前缀（前缀的概念可以转【数据结构】KMP算法保姆级教程）。这里B-1是D-11的前缀，所以编码"110"既可以倒推为"BBA"又可以倒推为"DA"。
如果在编码过程中，没有一个编码是另一个编码的前缀，我们称这样的编码为前缀编码（注意名字）。
那么如何构造出前缀编码呢？
等长编码
首先根据前缀的定义，当我们把待编码的所有字符的编码长度都设定成一样的，那么自然就不会出现互为前缀的情况了。这里我们假设编码长度为2，可以按照下面的方式编码：
A-00 B-01 C-10 D-11
按照这样的方法编出来的码不会产生歧义，不信可以试试（ABACACD-00010010001011）。但有个问题是，按照等长编码编出来的码有点过于长了，有没有别的方法既可以节省空间，又能够保证编码为前缀编码呢？
哈夫曼编码
这里给出哈夫曼编码的构造方法，一会再看看为什么所谓哈夫曼编码方式能够达到我们的要求：
- 将每个字符构造成一个节点，并统计出其在字符串中出现的次数，设置为节点的权值。
- 构造一个新的节点，将节点集合中权值最小的两个树拉出来，使他俩成为这个新节点的孩子，并且令新结点的权值为这俩权值之和。
- 将集合中被拉出的两棵树删除，并将新生成的树加入集合。
- 重复步骤2、3，直至集合里只有一棵树。
以字符串ABACACD为例：
此时如果令这个二叉树的左边为'0'，右边为'1'，并且令根节点到达某个字符代表的叶节点的路径为其编码，则得到的编码序列就能够同时满足短且不产生歧义的两个要求。
那么这种编码方式为什么能够满足短且唯一两个要求呢？理由如下：
- 由于权值大（出现次数多）的字符位于比较浅的层次，所以根节点到该字符的路径长度就比较短，所以编码长度就短；权值小（出现次数少）的字符位于比较深的层次，所以根节点到该字符的路径长度就比较长，所以编码长度较长。（此消彼长）
- 由于一个编码A想要成为另一个编码B的前缀必须满足两个条件：（1）A长度比另一个编码B短。（2）另一编码B的前几个字符要与编码A一样。这样的关系体现在二叉树上，则该字符所代表的节点一定会出现在另一编码节点的路径上，即一定是另一编码的祖先节点。而我们使用哈夫曼编码的过程中所有字符代表的节点都是最终树上的叶节点，所以不会出现这种情况。
哈夫曼树
上面所述的树即为哈夫曼树，这里再补充几点哈夫曼树的相关概念和性质。
带权路径长度（WPL）
从树的根到一个结点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。公式如下：
式中，
是第i个叶结点所带的权值，
是该叶结点到根结点的路径长度。
在含n个带权节点的二叉树中，哈夫曼树的WPL最小，所以哈夫曼树也称为最优二叉树。
哈夫曼树的性质
- 哈夫曼树不唯一。当选择两个节点构成新树时，左右次序不同，则编码方式也不同。同时注意我这里将哈夫曼树的左树枝置为0，右树枝置为1，你当然也可以左置1右置0，这样生成的哈夫曼树也不一样。所以可以看出，哈夫曼树不唯一，但是构造出的哈夫曼树WPL都相等。
- 构造过程中共新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1。
- 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。
本文原文来自CSDN