Huffman编码算法详解 | 您所在的位置:网站首页 › 哈组成的词 › Huffman编码算法详解 |
哈夫曼(Huffman)编码算法是基于二叉树构建编码压缩结构的,它是数据压缩中经典的一种算法。算法根据文本字符出现的频率,重新对字符进行编码。因为为了缩短编码的长度,我们自然希望频率越高的词,编码越短,这样最终才能最大化压缩存储文本数据的空间。 假设现在我们要对下面这句歌词“we will we will r u”进行压缩。我们可以想象,如果是使用ASCII码对这句话编码结果则为:119 101 32 119 105 108 108 32 119 101 32 119 105 108 108 32 114 32 117(十进制表示)。我们可以看出需要19个字节,也就是至少需要152位的内存空间去存储这些数据。 很显然直接ASCII码编码是很浪费空间的,Unicode就更不用说了,下面我们先来统计一下这句话中每个字符出现的频率。如下表,按频率高低已排序: 那么我们按出现频率高低将其放入一个优先级队列中,从左到右依次为频率逐渐增加。 首先我们从左到右进行合并,依次构建二叉树。第一步取前两个字符u和r来构造初始二叉树,第一个字符作为左节点,第二个元素作为右节点,然后两个元素相加作为新空元素,并且两者权重相加作为新元素的权重。 上图新元素权重相加后结果是变大了,需要对权重进行重新排序。 有了上面带权重的二叉树之后,我们就可以进行编码了。我们把二叉树分支中左边的支路编码为0,右边分支表示为1,如下图: 有了上面的编码表之后,”we will we will r u”这句重新进行编码就可以得到很大的压缩,编码表示为:01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100。这样最终我们只需50位内存,比原ASCII码表示节约了2/3空间,效果还是很理想的。当然现实中不是简单这样表示的,还需要考虑很多问题。 3 补充我们需要弄明白哈夫曼二叉树概念,它是带权路径达到最小的二叉树,也叫最优二叉树。它不一定是完全二叉树,也不一定是平衡二叉树,它们描述的完全不是一件事情,完全没有概念上的重叠关系。 |
CopyRight 2018-2019 实验室设备网 版权所有 |