霍夫曼编码和贪婪算法

本文概述

• 前缀代码
• 构造霍夫曼码的贪婪算法

• （i）可以使用霍夫曼码对数据进行有效编码。
• （ii）它是一种广泛使用的有益数据压缩技术。
• （iii）霍夫曼的贪婪算法使用每个字符出现频率的表来建立将每个字符表示为二进制字符串的最佳方式。

假设我们在一个数据文件中有105个字符。普通存储：每个字符8位（ASCII）-文件中8 x 105位。但是我们要压缩文件并紧凑地保存它。假设文件中仅出现六个字符：

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

（i）固定长度代码：每个字母由相等位数表示。使用固定长度的代码, 每个字符至少3位：

例如：

a			000

b			001

c			010

d			011

e			100

f			101

对于具有105个字符的文件, 我们需要3 x 105位。

（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是某些其他代码字的前缀, 称为前缀代码。

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

构造霍夫曼码的贪婪算法

霍夫曼（Huffman）发明了一种贪心算法, 该算法可创建称为霍夫曼码（Huffman Code）的最佳前缀代码。

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