霍夫曼编码
定长编码
节省
熵

符号 次数 编码 比特 总比特数

关于霍夫曼编码的更多信息

霍夫曼编码构建器

为什么英文中像 e 这样常见的字母要和像 z 这样罕见的字母占用同样多的比特?霍夫曼编码给常见的符号分配短码,给罕见的符号分配长码,而且做到了最优。输入一段文本或选择一个示例,一步一步构建它的霍夫曼树:最轻的两棵树合并到一个新节点下,一次又一次,直到只剩一棵树。然后从顶部出发的每条路径都拼出一个编码,你可以在编码后的比特中跟踪每个符号。 输入一段文本或选择一个示例。每个符号一开始都是一片叶子,带着它出现的次数。逐步观看构建过程:每一步都把最轻的两棵树挂到一个新节点下,新节点的权重是它们之和,直到只剩一棵树。然后从顶部到某片叶子的路径就给出它的编码,向左为 0,向右为 1。点击一片叶子、表格中的一行或比特中的一段,即可跟踪一个符号,并把总数与定长编码和熵进行比较。

它是如何运作的

  1. 输入或粘贴一段文本,或选择一个示例,例如 ABRACADABRA 或 MISSISSIPPI RIVER。
  2. 用“下一步”逐步观看构建过程,或点击“播放”:每一步都把最轻的两棵树挂到一个新节点下,节点的权重是它们之和。
  3. 树完成后,点击一片叶子、表格中的一行或比特中的一段来跟踪一个符号,并比较磁贴中的总数。

树是怎样构建的

统计每个符号出现的次数,把每个符号都做成一棵只有一片叶子的树,权重为它的次数。然后重复一个简单的步骤:取出权重最小的两棵树,把它们挂到一个新节点下,新节点的权重是它们之和。每一步都会让树少一棵,所以对于 n 个符号,经过 n − 1 步后只剩下一棵树。罕见的符号最先被合并,位于深处;常见的符号很晚才被合并,靠近顶部。

读出编码

从顶部往下走:向左走一步加一个 0,向右走一步加一个 1。通往一片叶子的路径就是该符号的编码。因为符号只位于叶子上,所以没有哪个编码是另一个编码的开头,因此一串比特无需任何分隔符就能解码:沿着比特在树中往下走,每到达一片叶子,就写下它的符号,再从顶部重新开始。对于 ABRACADABRA,霍夫曼编码需要 23 比特,而每个字母 3 比特的定长编码需要 33 比特。

常见问题

为什么霍夫曼编码是最优的?

在所有为每个符号分配一串整数比特的编码中,对于给定的次数,没有哪种编码的总长度更短。证明沿着构造过程进行:在最优编码中,总可以让两个最罕见的符号成为最深层的兄弟节点,把它们合并后,剩下的是一个同类的、更小的问题。总比特数等于树中所有内部节点的权重之和。

什么是前缀码?

一种没有哪个码字是另一个码字开头的编码,例如 0、10、110 和 111。这个性质让解码器无需分隔符就能读取比特流,因为它总是知道一个码字在哪里结束。每个霍夫曼编码都是前缀码:符号只位于树的叶子上。

霍夫曼树是唯一的吗?

不完全是:当两棵树权重相同时,先取哪一棵都可以,左右也可以交换。不同的选择会得到不同的编码,但总比特数总是相同。本构建器总是以同样的方式处理权重相同的情况,所以同一段文本总是得到同一棵树。

霍夫曼编码离熵有多近?

平均码长至少等于熵,且比熵高出不到 1 比特。当每个概率都是二分之一的幂时,它恰好等于熵,例如“次数逐个减半”这个示例。算术编码和现代的区间编码器避开了整数比特的限制,能更加接近熵。

我的文本会被发送到任何地方吗?

不会。树和编码都在你的浏览器中计算,你的文本保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器