霍夫曼编码是一种基于最小冗余编码的压缩算法。最小冗余编码是指，如果知道一组数据中符号出现的频率，就可以用一种特殊的方式来表示符号从而减少数据需要的存储空间。一种方法是使用较少的位对出现频率高的符号编码，用较多的位对出现频率低的符号编码。我们要意识到，一个符号不一定必须是文本字符，它可以是任何大小的数据，但往往它只占一个字节。
熵和最小冗余每个数据集都有一定的信息量，这就是所谓的熵。一组数据的熵是数据中每个符号熵的总和。符号z的熵S定义为：
Sz = -lg2 Pz
其中，Pz就数据集中z出现的频率。来看一个例子，如果z在有32个符号的数据集中出现了8次，也就是1/4的概率，那么z的熵就是：
-lg 2(1/4) = 2位
这意味着如果用超过两位的数来表示z将是一种浪费。如果在一般情况下用一个字节（即8位）来表示一个符号，那么在这种情况下使用压缩算法可以大幅减小数据的容量。
下表展示如何计算一个有72个数据实例熵的例子（其中有5个不同的符号）。要做到这一点，需将每个字符的熵相加。以U为例，它在数据集中出现了12次，所以每个U的实例的熵计算如下：
符号 概率 每个实例的熵 总的熵U 12/72 2.584 963 31.019 55
V 18/72 2.000 000 36.000 00
W 7/72 3.362 570 23.537 99
X 15/72 2.263 034 33.945 52
Y 20/72 1.847 997 36.959 94
-lg2(12/72) = 2.584 963 位
由于U在数据中出现了12次，因此整个数据的熵为：
2.584 963 * 12 = 31.019 55 位
为了计算数据集整体的熵，将每个字符所贡献的熵相加。每个字符的熵在表中已经计算出来了：
31.019 55 + 36.000 00 + 23.537 99 + 33.945 52 + 36.959 94 = 161.463 00 位
如果使用8位来表示每个符号，需要72 * 8 = 576位的空间，所以理论上来说，可以最多将此数据压缩：
1 - （161.463 000/576） = 72%
构造霍夫曼树霍夫曼编码展现了一种基于熵的数据近似的最佳表现形式。它首先生成一个称为霍夫曼树的数据结构，霍夫曼树本身是一棵二叉树，用它来生成霍夫曼编码。霍夫曼编码是用来表示数据集合中符号的编码，用这种编码的方式达到数据压缩的目的。然而，霍夫曼编码的压缩结果往往只能接近于数据的熵，因为符号的熵往往是有小数位的，而在实际中，霍夫曼编码所用的位数不可能有小数位，所以有些代码会超过实际最优的代码位数。
下图展示了用上表中的数据来构建一棵霍夫曼树的过程。构建的过程往往是从叶子结点向上进行。首先，将每个符号和频率放到它自身的树中（步骤1）。然后，将两个频率最小的根结点的树合并，并将其频率之和放到树的新结点中（步骤2）。这个过程反复持续下去，直到最后只剩下一棵树（这棵树就是霍夫曼树，步骤5）。霍夫曼的根结点包含数据中符号的总个数，它的叶子结点包含原始的符号和符号的频率。由于霍夫曼编码就是在不断寻找两棵最适合合并的树，因此它是贪婪算法的一个很好的例子。
建立一棵霍夫曼树是数据压缩和解压缩的一部分。
用霍夫曼树压缩数据，给定一个具体的符号，从树的根开始，然后沿着树的叶向叶子结点追踪。在向下追踪的过程中，当向左分支移动时，向当前编码的末尾追加0；当向右移动时，向当前编码的末尾追加1。在上图中，追踪“U”的霍夫曼编码，首先向右移动（1），然后向左移动（10），然后再向右（101）。图中符号的霍夫曼编码分别为：
U=101，V=01，W=100，X=00，Y=11
要解压缩用霍夫曼树编码的数据，要一位一位地读取压缩数据。从树的根开始，当在数据中遇到0时，向树的左分支移动；当遇到1时，向右分支移动。一旦到达一个叶子结点就找到了符号。接着从头开始，重复以上过程，直到所有的压缩数据都找出。用这种方法来解压缩数据是可能的，这是因为霍夫曼树是属于前缀树。前缀树是指一组代码中，任何一个编码都不是另一个编码的前缀。这就保证了编码被解码时不会有多义性。例如，“V”的编码是01，01不会是任何其他编码的前缀。因此，只要在压缩数据中碰到了01，就可以确定它表示的符号是“V”。
霍夫曼编码的效率