1. StackOverflow 文档
  2. algorithm 教程
  3. 贪心算法
  4. 霍夫曼编码

霍夫曼编码

Created: November-22, 2018

霍夫曼代码是一种特殊类型的最佳前缀代码，通常用于无损数据压缩。它可以非常有效地压缩数据，从 20％到 90％的内存，具体取决于被压缩数据的特性。我们认为数据是一系列字符。Huffman 的贪婪算法使用一个表来说明每个字符出现的频率（即其频率），以建立将每个字符表示为二进制字符串的最佳方式。霍夫曼代码由 David A. Huffman于 1951 年提出。

假设我们有一个 100,000 字符的数据文件，我们希望紧凑地存储。我们假设该文件中只有 6 个不同的字符。字符的频率由下式给出：

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

我们有很多选择来表示这样的信息文件。在这里，我们考虑设计二进制字符代码的问题，其中每个字符由唯一的二进制字符串表示，我们称之为代码字。

https://i.stack.imgur.com/VP5UP.jpg

构建的树将为我们提供：

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

如果我们使用固定长度的代码，我们需要三位代表 6 个字符。此方法需要 300,000 位来编码整个文件。现在的问题是，我们能做得更好吗？

一个可变长度代码可以做得比固定长度的代码相当好，通过给频繁字符短的码字和偶发字符长码字。此代码需要：（45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4）X 1000 = 224000 位表示文件，可节省大约 25％的内存。

需要记住的一点是，我们在此仅考虑其中没有代码字也是某些其他代码字的前缀的代码。这些被称为*前缀代码。*对于可变长度编码，我们将 3 字符文件 abc 编码为 0.101.100 = 0101100，其中“。” 表示连接。

前缀代码是理想的，因为它们简化了解码。由于没有代码字是任何其他代码字的前缀，因此开始编码文件的代码字是明确的。我们可以简单地识别初始码字，将其转换回原始字符，并对编码文件的其余部分重复解码过程。例如，001011101 唯一地解析为 0.0.101.1101，其解码为 aabe 。简而言之，二进制表示的所有组合都是唯一的。例如，如果一个字母用 110 表示，则 1101 或 1100 不会表示其他字母。这是因为你可能会在选择 110 或继续连接下一位并选择该位时遇到困惑。

压缩技术：

该技术通过创建节点的二叉树来工作。这些可以存储在常规数组中，其大小取决于符号数 n 。节点可以是叶节点或内部节点。最初所有节点都是叶节点，它包含符号本身，其频率以及可选的链接到其子节点。作为惯例，位'0’表示左子，位'1’表示右子。优先级队列用于存储节点，在弹出时为节点提供最低频率。该过程描述如下：

  1. 为每个符号创建一个叶节点，并将其添加到优先级队列。
  2. 虽然队列中有多个节点：
    1. 从队列中删除具有最高优先级的两个节点。
    2. 创建一个新的内部节点，将这两个节点作为子节点，频率等于两个节点频率的总和。
    3. 将新节点添加到队列中。
  3. 其余节点是根节点，霍夫曼树已完成。

对于我们的例子： https://i.stack.imgur.com/mOobp.jpg

伪代码看起来像：

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

虽然线性时间给定排序输入，但在一般情况下任意输入，使用此算法需要预先排序。因此，由于在一般情况下排序需要 O(nlogn) 时间，因此两种方法具有相同的复杂性。

由于这里的 n 是字母表中的符号数，通常是非常小的数字（与要编码的消息的长度相比），因此在选择该算法时时间复杂度不是很重要。

减压技术：

解压缩的过程简单地是将前缀码流转换为单个字节值的问题，通常通过在从输入流中读取每个比特时逐节点地遍历霍夫曼树。到达叶节点必然终止对该特定字节值的搜索。叶值表示所需的字符。通常，霍夫曼树是使用每个压缩周期的统计调整数据构建的，因此重建非常简单。否则，重建树的信息必须单独发送。伪代码：

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

贪婪说明：
霍夫曼编码查看每个字符的出现并以最佳方式将其存储为二进制字符串。其思想是为输入字符分配可变长度代码，分配代码的长度基于相应字符的频率。我们创建一个二叉树并以自下而上的方式对其进行操作，以便至少两个频繁字符尽可能地从根目录开始。通过这种方式，最常见的字符获得最小的代码，而最不频繁的字符获得最大的代码。

参考文献：

  • 算法简介 - Charles E. Leiserson，Clifford Stein，Ronald Rivest 和 Thomas H. Cormen
  • 霍夫曼编码 - 维基百科
  • 离散数学及其应用 - Kenneth H. Rosen