哈夫曼编码 Huffman Codes

• 广泛使用的数据压缩技术

• 假设数据是一个字符序列

• 寻找存储数据的有效方法

• 想法：

–使用字符出现的频率来建立表示每个字符的最佳方式

• 二进制字符代码

–用二进制字符串唯一地表示一个字符

定长码 Fixed-Length Codes

例如：包含100000个字符的数据文件

• 需要3位

• a=000，b=001，c=010，d=011，e=100，f=101

• 需要：100000·3=300000位

可变长度码 Variable-Length Codes

例如：包含100000个字符的数据文件

• 将短码字分配给频繁字符，将长码字分配给不频繁字符

• a=0，b=101，c=100，d=111，e=1101，f=1100

• (45 · 1 + 13 · 3 + 12 · 3 + 16 · 3 + 9 · 4 + 5 · 4) · 1,000=224000位

前缀码 Prefix Codes

• 前缀码：

-没有码字的代码也是其他码字的前缀

-更好的名字是“前缀免费代码”

• 我们可以使用前缀码实现最佳数据压缩

-我们将把注意力限制在前缀码上。

用二进制字符编码 Encoding with Binary Character Codes

• 编码

–连接表示文件中每个字符的码字

• 例如：-a=0，b=101，c=100，d=111，E=1101，f=1100

–abc=0·101·100=0101100

• 前缀码简化了解码

–没有任何码字是另一个码字的前缀→ 码字

一个编码文件的开头是明确的

• 方法

–识别初始码字

–将其翻译回原始字符

–对文件的其余部分重复此过程

• 例如：-a=0，b=101，c=100，d=111，E=1101，f=1100

–001011101=0·0·101·1101=aabe

前缀码表示法 Prefix Code Representation

• 叶为给定字符的二叉树

• 二进制码字

–从根到字符的路径，其中0表示“转到

“左孩子”和1表示“转到右孩子”

• 码字的长度

–从根到字符叶的路径长度（节点深度）

最优码 Optimal Codes

• 最佳代码始终由完整的二叉树表示

–每个非叶子都有两个孩子

–固定长度代码不是最佳的，可变长度代码是最佳的

• 编码一个文件需要多少位？

–设C为字符的字母表

–设f（c）为字符c的频率–设 为对应于前缀代码的树T中c的叶的深度

树T的成本

构造哈夫曼码 Constructing a Huffman Code

• 贪婪算法，构造称为哈夫曼码的最佳前缀码

• 假设：

–C是一组n个字符

–每个字符都有一个频率f（c）

–树T以自下而上的方式构建

• 想法：

–从一组“C”形叶子开始

–在每个步骤中，合并两个频率最低的对象：新节点的频率=两个频率的总和

–使用最小优先级队列Q，键入f以识别两个最不频繁的对象

实例 Example

构建哈夫曼代码 Building a Huffman Code

9. return EXTRACT-MIN(Q)

贪婪选择性质 Greedy Choice Property

引理：设C是一个字母表，其中每个字符都是C∈ C具有频率f[C]。设x和y是C中频率最低的两个字符。

然后，存在一个C的最优前缀码，其中x和y的码字具有相同的长度，并且仅在最后一位不同。

贪婪选择的证明 Proof of the Greedy Choice

• 想法：

-考虑树T表示任意最优前缀码

–修改T，使树表示另一个最佳前缀代码，其中x和y将显示为最大深度的同级叶→ x和y的代码长度相同，仅在最后一位不同

•a，b–两个字符，T中最大深度的兄弟叶片

•假设：f[a]≤f[b]和f[x]≤f[y]

•f[x]和f[y]依次为两个最低的叶频→ f[x]≤f[a]和f[y]≤f[b]

•交换a和x（T’）以及b和y（T’）的位置

讨论 Discussion

• 贪婪选择财产：

–通过合并构建最优树可以从贪婪的选择开始：合并频率最低的两个字符

–每次合并的成本是合并的两个项目的频率之和

–在所有可能的合并中，哈夫曼选择成本最低的合并