霍夫曼(Huffman)压缩编码算法

2020年11月17日 / 19次阅读 / Last Modified 2020年11月23日
算法

霍夫曼编码(Huffman Coding),又译为哈夫曼编码赫夫曼编码,是一种用于无损数据压缩的熵编码(权编码)算法,由大卫·霍夫曼在1952年发明。

霍夫曼编码算法的思想:通过不定长编码的方式,使出现频率越高的字符对应短码,出现频率低的字符对应长码,以此来达到无损压缩的效果(用较少的比特表示出现频率高的字符,用较多的比特表示出现频率低的字符)。而且,任一字符编码都不是其它字符编码的前缀,编码后的bit stream不需要分隔符。

霍夫曼(Huffman)压缩编码算法
霍夫曼(Huffman)压缩编码算法

所有的字符都是叶子结点。

霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和。

如何构造Huffman Tree?

  • 统计所有字符出现的频率,从小到大排序;
  • 拿出两个出现频率最小的字符来作为两个叶子结点,并将这两个叶子结点的根节点加入排序队列的前端,这个根节点的“频率”为两个叶子结点频率的和;
  • 重复上诉步骤,直到排序队列空。

Huffman Tree是从底向上构造的。

相同的排序队列,构造的Huffman Tree不唯一,但不影响编码压缩效率。比如当将那个节点合并成一个根节点的时候,哪个在左,哪个在右,虽然影响某个字符的编码,但是不影响编码长度,也不影响编码压缩效率。

获得Huffman编码

通过遍历Huffman Tree,就可以得到每一个叶子结点的code。对于根节点,规定左边的路径是0,右边的路径是1,这样得到的code,就是一组01序列。(当然也可以规定左边路径为1,右边路径为0,这也是为什么Huffman编码不唯一,但长度唯一)

由于构建Huffman Tree是从底向上进行的,出现频率越大的叶子结点,越靠近root。因此,出现频率越高的叶子结点,其code越短。

每一个叶子结点,其code唯一,而且不与任何其它code的前缀重复!

-- EOF --

本文链接:https://www.pynote.net/archives/2803

留言区

《霍夫曼(Huffman)压缩编码算法》有5条留言

电子邮件地址不会被公开。 必填项已用*标注

  • 麦新杰

    Huffman, David A. "A method for the construction of minimum-redundancy codes." Proceedings of the IRE 40.9 (1952): 1098-1101. [回复]

  • 麦新杰

    codeword table是与压缩后的信息绑定的,没有这个table,无法解压缩。 [回复]

  • 麦新杰

    最经典的统计无损压缩算法 [回复]

  • 麦新杰

    If at any point there is more than one way to choose the two trees of smallest weight, the algorithm chooses arbitrarily. [回复]

  • 麦新杰

    其实,从实践上考虑,有的时候可以直接使用一个预定义的Huffman coding table,在无法预先统计的情况下。虽然不能得到最佳压缩率,但还是有效的。 [回复]


前一篇:
后一篇:

More


©Copyright 麦新杰 Since 2019 Python笔记

go to top