今天给大家科普一下哈夫曼编码（HuffmanCoding），一种无损数据压缩的熵编码算法，由美国计算机科学家大学DavidHoffman提出1952年的——这么专业的解释，别问，来自维基百科。说实话，很久以前就听说过哈夫曼编码。除了知道它通常用于GZIP、BZIP2、PKZIP等常规压缩格式之外，我还知道它通常用于压缩重复率比较高的字符数据。大家想一想，英文有26个字母的无限组合，重复率极高！常用汉字不多，2500左右，别问我怎么知道的，我问过搜索引擎。字符重复的频率越高，哈夫曼编码的效率就越高！是时候和大家一起了解哈夫曼编码的工作原理了。毕竟，一个好的程序员必须能够知道发生了什么知道为什么——请允许我再次使用这个近乎臭名昭著的短语。假设下面的字符串要通过网络发送。大家应该都知道，每个字符占8位，上面一串字符一共有15个字符，所以一共会占用15*8=120位。你有任何问题吗？有问题的同学，请随时离开。如果我们使用哈夫曼编码，我们可以将这串字符压缩到更小的尺寸。怎么做？哈夫曼编码首先会利用字符出现的频率来创建一棵树，然后通过这棵树的结构为每个字符生成特定的编码。出现频率高的字符使用较短的编码，出现频率低的字符使用较长的编码，这样会减少编码字符串的平均长度，从而达到数据无损压缩的目的。就拿上面这串首字母，一步步解释哈夫曼编码的工作步骤。第一步，计算字符串中每个字符出现的频率。B出现1次，C出现6次，A出现5次，D出现3次。第二步，按照字符出现的频率排序，形成一个队列Q，出现频率最低的排在前面，出现频率最高的排在后面。第三步，将这些字符作为叶节点，开始构建树。首先创建一个空节点z，将出现次数最少的字符分配给z的左边，将出现次数第二多的字符分配给z的右边，然后将z分配给两个字符的出现频率之和。B的频率最小，所以在左边，然后是D，频率为3，在右边；然后将它们的父级设置为4，即子级频率的总和。然后将B和D从队列Q中移除，并将它们的和添加到队列中上图中*指示的位置。接下来重新创建一个空节点z，左节点为4，右节点为频率为5的A，父节点为4和5之和。按照之前的思路继续建树，直到所有的字符都出现在树的节点中。第四步，对每个非叶节点，将连接线的左边赋值0，连接线的右边赋值1。至此，哈夫曼树构建完成。哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。构建树后，让我们计算要发送的位数。1）看字符栏。A、B、C、D四个字符共4*8=32位。每个英文字母占用一个字节，即8位。2)查看频率列。A5次，B1次，C6次，D3次，共15位。3）看编码栏。A的编码为11，对应哈夫曼树上的15→9→5，也就是说从根节点到叶子节点A，需要经过11的路径；对应的B需要经过100的路径；对应的D需要经过101的路径；对应的C需要经过0的路径。4）看length栏。A的编码为11，出现5次，所以占用10位，即1111111111；B的编码为100，出现一次，所以占用3位，即100；C的编码为0，出现6次，所以占6位，即000000；D的编码为101，出现了3次，所以占用9位，即101101101。哈夫曼编码本质上就是把最有价值的资源（最短编码）给出现概率最大的数据。在上面的例子中，C出现的次数最多，它的代码是0，这样就节省了很多空间。结合生活中的一些情况想想，也是一样，我们把最常用的放在手边，这样既可以提高效率又可以节省时间。所以，我有一个大胆的猜测，这就是霍夫曼寻找编码最优解的方式。在霍夫曼编码编码之前，字符串“BCAADDDDCACACAC”的二进制是：10000100100001101000001010001010001000100010001000100011011010000010000101001001001000001010011是100001010011编码后：0000001001011011011111111111占28位。但是考虑到解码，需要传递哈夫曼树的结构，所以字符占用的32位和频率占用的15位也需要传递。总体来说，编码的比特数是32+15+28=75，比120比特少了45，效率还是很高的。关于哈夫曼编码的Java例子，我也贴在这里，供大家参考。classHuffmanNode{intitem;charc;HuffmanNodeleft;HuffmanNoderight;}classImplementComparatorImplementComparator
