信息的压缩与解压

把消息重新打包。

点一枚,加入纸带

+ 盖章
原来24bit
打包后 · 含说明卡33bit

多出 9 bit

你的消息

12 / 64 枚
换一条

这次怎样编码

点一格,沿纸带找它

每一小格,都是 1 bit

同样大小

定长编码

每枚 2 bit 24 bit

哈夫曼编码

码字有长有短 18 bit
+ 编码说明卡15 bit
还原时,也要知道这次的编码规则。
18 + 15 = 33 bit

还原口

正在读—把纸带放进来0 / 0 bit

先带上说明卡,再从第一个 0 或 1 开始。

展开这次的编码树 0 向左 · 1 向右

每次合并频次最小的两组;从根走到图章,沿路的 0 和 1 就是码字。

说明卡怎样数?按根、左、右的顺序写:分叉为 0;图章为 1,再跟 2 bit 编号(圆 00、三角 01、方 10、星 11)。

消息可以完整回来,包却不一定更小。比较教学位数;两种方式都不计公共封装与字节补齐。

信息的压缩与解压

把常见的符号,写得短一点

四种图章代表四个离散符号。定长编码始终用 00、01、10、11,每个符号 2 bit。哈夫曼编码根据本条消息的实际频次,把频次最小的两组反复合并,形成一棵树;左分支记 0,右分支记 1,走到图章就得到它的码字。同频时按圆、三角、方、星的最小编号决定次序。

一个完整码字不会是另一个码字的开头,因此不必另加分隔符。还原口从编码数据逐位走树,每抵达一个图章就输出它,再回到树根。页面里的空隙和颜色只是帮助你观察,不占用编码数据。

为什么有时更长?

接收端还要知道本次采用哪棵树。本页把整棵树序列化为说明卡:每个内部节点 1 bit,每个叶子 3 bit(叶子标志 1 bit 加图章编号 2 bit)。出现四种图章时,共 3 个内部节点和 4 个叶子,即 15 bit。包长为数据加说明卡;短消息或均匀分布未必省空间。

两种方法都使用事先约定的四符号字母表,都不计公共消息边界、长度字段、文件格式开销与字节补齐;这里比较的是教学模型中的位数,不等于某种真实文件的字节大小。说明卡本身可以完整解析出树,数据段结束位置由共同的外层消息边界给出。

模型范围

只出现一种图章时约定码字为 0,说明卡仍为 3 bit;空消息不生成树或数据。每条消息最多 64 枚。重做编码会改变整条消息的码字,不是只给新图章追加一个固定码字。

本页展示无损符号编码,不是通用图片压缩。无损意味着正常传输后可以精确恢复,不能保证受到比特错误破坏后仍能还原。本页的打包与解码均在浏览器中计算。

对应馆内展项

深圳科学技术馆 · F3 通信科技专馆
信息的压缩与解压 · M1-03/17
馆内展项通过字母输入、构建哈夫曼树和编码对照展示压缩;本页把输入变为可点按的图章,并显现说明卡的成本。

馆方展项页面 ↗MIT · 哈夫曼编码课程资料 ↗

展项依据来自本地资料库,不代表现场开放状态。全部操作均支持点击与键盘;减少动态效果时,还原口默认逐位点按。