霍夫曼编码

• 可以使用哈夫曼编码有效地编码数据。
• 这是一种广泛使用且有益于压缩数据的技术。
• 哈夫曼的贪心算法使用每个字符出现频率的表来构建一种最佳方式，将每个字符表示为二进制字符串。

假设我们在一个数据文件中包含 10⁵ 个字符。正常存储：每个字符 8 位 (ASCII) - 文件中 8 x 10⁵ 位。但我们希望压缩文件并使其紧凑地保存。假设文件中只出现了六个字符

我们如何以紧凑的方式表示数据？

(i) 定长编码： 每个字母用相同数量的位表示。使用定长编码，每个字符至少 3 位

例如

a			000

b			001

c			010

d			011

e			100

f			101

对于一个包含 10⁵ 个字符的文件，我们需要 3 x 10⁵ 位。

(ii) 变长编码： 通过为许多字符提供短码字和不常用字符提供长码字，它可以比定长编码做得更好。

例如

  a       0

  b      101

  c      100

  d      111

  e      1101

  f      1100
Number of bits = (45 x 1 + 13 x 3 + 12 x 3 + 16 x 3 + 9 x 4 + 5 x 4) x 1000
= 2.24 x 105bits

因此，用 224,000 位表示文件，节省了大约 25%。这是该文件的最佳字符编码。

前缀码

一个字符的编码的前缀不能等于另一个字符的完整编码，例如，1100 和 11001 不是有效的代码，因为 1100 是某个其他码字的 前缀， 这被称为前缀码。

前缀码是可取的，因为它们阐明了编码和解码。 对于任何二进制字符码，编码总是很简单； 我们连接描述文件的每个字符的码字。 使用前缀码，解码也很舒服。 由于没有码字是任何其他码字的前缀，因此以编码数据开头的码字是明确的。

构造哈夫曼码的贪心算法

哈夫曼发明了一种贪心算法，该算法创建了一种称为哈夫曼码的最佳前缀码。

该算法以自底向上的方式构建类似于最优代码的树 T。它从一组 |C| 个叶子（C 是字符数）开始，并执行 |C| - 1 个“合并”操作以创建最终的树。在哈夫曼算法中，'n' 表示一组字符的数量，z 表示父节点，x & y 分别是 z 的左子节点和右子节点。