图解霍夫曼编码
给大家普及一下霍夫曼编码(Huffman Coding),一种用于无损数据压缩的熵编码算法,由美国计算机科学家大卫·霍夫曼在 1952 年提出——这么专业的解释,不用问,来自维基百科了。 说实话,很早之前我就听说过霍夫曼编码,除了知道它通常用于 GZIP、BZIP2、PKZIP 这些常规的压缩格式中,我还知道它通常用于压缩重复率比较高的字符数据。 大家想啊,英文就 26 个字母进行的无限组合,重复率高得一逼啊!常用的汉字也不多,2500 个左右,别问我怎么知道的,我有问过搜索引擎的。 字符重复的频率越高,霍夫曼编码的工作效率就越高! 是时候,和大家一起来了解一下霍夫曼编码的工作原理啦,毕竟一名优秀的程序员要能做到知其然知其所以然——请允许我又用了一次这应该知道,每个字符占 8 个比特,上面这串字符总共有 15 个字符,所以一共要占用 15*8=120 个比特。没有疑问吧?有疑问的同学请不好意思下。 如果我们使用霍夫曼编码的话,就可以将这串字符压缩到一个更小的尺寸。怎么做到的呢? 霍夫曼编码首先会使用字符的频率创建一棵树,然后通过这个树的结构为每个字符生成一个特定的编码,出现频率高的字符使用较短的编码,出现频率低的则使用较长的编码,这样就会使编码之后的字符串平均长度降低,从而达到数据无损压缩的目的。 拿上面这串初始字符来一步步的说明下霍夫曼编码的工作步骤。 第一步,计算字符串中每个字符的频率。率这一列。A 5 次,B 1 次,C 6 次,D 3 次,一共 15 比特。 3)来看编码这一列。A 的编码为 11,对应霍夫曼树上的 15→9→5,也就是说,从根节点走到叶子节点 A,需要经过 11 这条路径;对应的 B 需要走过 100 这条路径;对应的 D 需要走过 101 这条路径;对应的 C 需要走过 0 这条路径。 4)来看长度这一列。A 的编码为 11,出现了 5 次,因此占用 10 个比特,即 1111111111;B 的编码为 100,出现了 1 次,因此占用 3 个比特,即 100;C 的编码为 0,出现了 6 次,因此占用 6 个比特,即 000000;D 的编码为 101,出现了 3 次,因此占用 9 个比特,即 101101101。 哈夫曼编码从本质上讲,是将最宝贵的资源(最短的编码)给出现概率最多的数据。在上面的例子中,C 出现的频率最高,它的编码为 0,就省下了不少空间。 结合生活中的一些情况想一下,也是这样,我们把最常用的放在手边,这样就能提高效率,节约时间。所以,我有一个大胆的猜想,霍夫曼就是这样发现编码的最优解的。
在没有经过霍夫曼编码之前,字符串“BCAADDDCCACACAC”的二进制 (编辑:东莞站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |