当前课程知识点：计算思维导论 > 第九单元 > 9.20 哈夫曼编码 > Video
大家好
这一节我们讲哈夫曼编码
哈夫曼编码是如此著名
以至于连编码的发明过程
也成了人们津津乐道的话题
据说1952年时
哈夫曼还是麻省理工学院的一个学生
他为了向老师证明自己
可以不参加某门功课的期末考试
设计了这个看似简单
但却影响深远的编码方法
要理解哈夫曼编码及其压缩思想
先要了解计算机存储
或传输消息的方式
为了存储和传输
美国在1967年就制定并颁布了
美国标准信息交换码
也就是ASCII码
根据这个标准
字母a用27代替
字母b用28代替
c用29代替等等
其他字符
大家可以查看这个表
尽管计算机内部
使用的是二进制系统
但不影响我们
以十进制方式来讨论问题
这样做更容易让大家理解编码
及其压缩思想和方法
那么计算机
该如何利用ASCII表存储
Meet your fiancé there
这句话呢
很简单
只要将每个字符翻译成
对应的数字编码
并串联在一起可以了
就像这样
在计算机里边
数字编码之间可是没有空隔的
在这里加上空格
只是为了我们阅读方便
实际上这条消息
被存储为一个连续的46位的一个数
当然人类解读这一串数字
是有点困难的
但对计算机来说却轻而易举
因为我们采取了等长编码
也就是说
每个英文字母
都是用两个数字来表示的
只要每两个数字一分割
然后查ASCII表
就知道对应的字母了
这也就是为什么
大写字母A用“01”
而不是“1”表示的原因
否则就会产生歧义
比如数字串“1123”
就可以拆成“1 1 23”（AAW）
“11 2 3”（KBC）
“1 1 2 3”（AABC）
以及“11 23”（KW）
大家知道
不管用五笔字形
还是拼音输入汉字
使用频率最高的字
敲一个键就出来了
而使用频率不高的字
则要敲多个键才出来
计算机出现之前
著名的Morse电码
也采用了类似的做法
以有效缩短最终的电码长度
那么可否把这一思想用于压缩
答案是肯定的
事实上人们做过统计
发现英文字母在日常的工作
学习和生活中
使用的频率相互差异很大
统计结果可以用这么一个图来表示
不难看出
字母e和字母t使用的频率很高
字母j q z等使用的频率很低
让我们尝试缩短高频字母的编码
比如假设字母e用8表示
字母t用9表示
还是以这么一句话
Meet your fiancé there
为例看看结果怎么样
前面我们一共用了46个数字
现在呢
您看 看到了吧
编码变成了40个数字
但是解码时“Meet”所对应的编码
“13889”既可以解压成
“13 8 8 9”
也可以解压成“13 88 9”
或者“13 8 89”
要解决这个问题
必须有所牺牲
也就是
让一些字母的编码更长一些
比如让原来
以8或9开头的两位数编码
变成三位数编码
就像这样
这样一来
以7开头的数字都是三位数编码
以8或9开始的都是一位数编码
以0 1 2 3 4 5或6开头的
都是两位数编码
这样来解码“13889”
就没有歧义了
对于前面出现的例子
可以得到这样的编码结果
编码长度就
由46个数字变成了41个数字
看起来压缩效率好像不高
但如果压缩整本书的话
效果就很明显了
从理论上来说
上面的思想和方法确实不错
但我们注意到
一 上述思想和方法都是以
十进制为例进行说明的
尽管思路一样
但计算机毕竟是基于二进制的
二 根据频率统计方法的
变长编码思想
如何更加有效地进行编码呢
哈夫曼编码就完整地回答了
这个问题
为了便于理解
我们还是以实例进行说明
假设要压缩的字符串是
EAEBAECDEA
符号串中总共只有5个字母
现在我们不妨假定
这5个字母的使用频率
如这个表所示
首先以每个字符的使用频率
作为权值来构造一颗哈夫曼树
哈夫曼树的构造并不难
至少比玩好些游戏简单
方法如下
第一步
把每个字符作为一个节点
标注它的权值
现在它们都是哈夫曼树的
最底层节点
第二步找出权值最小的两个节点
把它们合并成一个新的节点
新节点的权值是
合成它的两个节点的权值的和
第三步我们进一步
重复上面所做的工作
直到所有节点结合成一颗二叉树
最后我们就可以得到
这么一颗二叉树来
其次我们利用哈夫曼树进行编码
方法是
给哈夫曼树的
每个分支分配一个二进制位
我们从根节点开始
给左分支分配0
给右分支分配1
直到整棵二叉树分配完毕
从根节点开始
沿着各分支
到达该字母所经过的路径上的
各分支的二进制位值的顺序排列
编码结果就像这个图所表示的一样
下面是实例
EAEBAECDEA的
哈夫曼编码与译码
编码长度22位译码
十分容易
不存在二义性
就像这个图所表示的
哈夫曼编码的效率很高
运算速度快
从20世纪60年代至今
在数据压缩领域得到了
广泛的应用
好这一节我们就介绍到这
谢谢大家
-1.1 计算思维及其教育
--Video
-2.1 计算是什么
--Video
-2.2 计算与自动计算
--Video
-2.3 计算机及其计算本质特征（I）
--Video
-2.4 计算机及计算的本质特征（II）
--Video
-3.1 数的表示与模拟计算
--Video
-3.2 数的表示与数字计算
--Video
-3.3 二进制加法运算的机器化
--Video
-3.4 “九九归一”的加法运算
--Video
-3.5 二进制之优越性及问题与代价
--Video
-4.1 从数学危机到图灵机
--Video
-4.2 图灵机的计算能力
--Video
-4.3 什么问题都能计算吗？
--Video
-4.4 冯•诺依曼机及其发展与演化
--Video
-4.5 从算盘到图灵机——机械计算的本质
--Video
-4.6 电子计算机——透过现象看本质
--Video
-5.1 思维可机械计算吗（I）
--Video
-5.2 思维可机械计算吗（II）
--Video
-6.1 量子理论
--Video
-6.2 量子计算机
--Video
-7.1 人类求解问题之过程
--Video
-7.2 基于计算（机）的问题求解过程
--Video
-7.3 面向过程的结构化设计方法学
--Video
-7.4 面向对象之方法学
--Video
-7.5 面向对象技术
--Video
-7.6 抽象
--Video
-7.7 计算学科中的抽象
--Video
-7.8 时间与空间及其相互转换
--Video
-7.9 技术层面的其他方法学
--Video
-7.10 认知层面的其他方法学
--Video
-8.1 算法与程序
--Video
-8.2 算法设计方法——枚举
--Video
-8.3 算法设计方法——递推
--Video
-8.4 算法设计方法——递归
--Video
-8.5 算法设计方法——分治
--Video
-8.6 算法设计方法——仿生
--Video
-9.1 机器间的通信方式
--Video
-9.2 数据转发方法
--Video
-9.3 网络分层体系结构
--Video
-9.4 有趣的对称加密技术
--Video
-9.5 难解的非对称加密技术
--Video
-9.6 数字签名及其应用
--Video
-9.7 从自然智能到人工智能
--Video
-9.8 符号主义的基本思想
--Video
-9.9 连接主义Ⅰ
--Video
-9.10 连接主义Ⅱ
--Video
-9.11 行为主义的基本思想
--Video
-9.12 机器翻译的愿景与困难
--Video
-9.13 峰回路转的自然语言处理
--Video
-9.14 信息传输中的问题与挑战
--Video
-9.15 重复传输与冗余编码
--Video
-9.16 校验与校验和
--Video
-9.18 自纠错技术及应用
--Video
-9.19 两种简单的数据压缩方法
--Video
-9.20 哈夫曼编码
--Video
-9.21 数据压缩极限与LZ压缩方法
--Video
-9.22 大海捞针的搜索引擎
--Video
-9.23 网页排序方法（PageRank）
--Video
-10.1 计算文化
--Video
-期末考试--作业
