哈夫曼树-哈夫曼编码
哈夫曼树-哈夫曼编码
哈夫曼编码是一种广泛应用于数据压缩领域的编码方式，它通过构建最优二叉树（哈夫曼树）来实现数据的高效编码。本文将详细介绍哈夫曼编码的基本原理、构建过程及其在数据压缩中的应用。
哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
如果需要传输一段文字“BADCADFEED”，可以用二进制编码表示。
这个时候数据编码后是“001000011010000011101100100011”，对方接受后每三位一分进行译码。但是在一段文章中，字母的出现频率肯定有高有低，出现频率高的元素的二进制越短，传输的时候的数据也会越短。如果把上面表格中多余的前导0去掉，例如：B：1，D：11,那么编码之后的二进制的确变短了，但是译码的时候无法知道接受的数据中的11代表两个B还是一个D。
通过哈夫曼编码可以构造出最优的二叉树-哈夫曼树来确定如何编码。假设
字母 A B C D E F
频率(%) 27 8 15 15 30 5
哈夫曼编码的规则就是：
1、先找出权值（频率）{30，27，15，15，8，5}最小的两个作为左右子树构造一棵新树。即取5，8构成新树，其结点为5+8=13，如图：
2、再把新生成的权值为13的结点放到剩下的集合中，所以集合变成{30，27，15，15，13}，再根据1，取最小的两个权值构成新树，如图：
3、再依次建立哈夫曼树，如下图：
4、带入对应的字符，左分支为0，右分支为1。
对字母用其从树根到所在叶子所经过路径的0或1来编码，可以得到下表：
字母 A B C D E F
二进制字符 01 1001 101 00 11 1000
对比一下两种编码方式：大于节约17%的存储或传输成本。
编码中非0即1，长短不等的话其实很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作无前缀编码。
哈夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。如果考虑到进一步节省存储空间，就应该将出现概率大（占比多）的字符用尽量少的0-1进行编码，也就是更靠近根（节点少），这也就是最优二叉树-哈夫曼树。