| 符号 | 次数 | 编码 | 比特 | 总比特数 |
|---|
霍夫曼编码构建器
为什么英文中像 e 这样常见的字母要和像 z 这样罕见的字母占用同样多的比特?霍夫曼编码给常见的符号分配短码,给罕见的符号分配长码,而且做到了最优。输入一段文本或选择一个示例,一步一步构建它的霍夫曼树:最轻的两棵树合并到一个新节点下,一次又一次,直到只剩一棵树。然后从顶部出发的每条路径都拼出一个编码,你可以在编码后的比特中跟踪每个符号。 输入一段文本或选择一个示例。每个符号一开始都是一片叶子,带着它出现的次数。逐步观看构建过程:每一步都把最轻的两棵树挂到一个新节点下,新节点的权重是它们之和,直到只剩一棵树。然后从顶部到某片叶子的路径就给出它的编码,向左为 0,向右为 1。点击一片叶子、表格中的一行或比特中的一段,即可跟踪一个符号,并把总数与定长编码和熵进行比较。
它是如何运作的
- 输入或粘贴一段文本,或选择一个示例,例如 ABRACADABRA 或 MISSISSIPPI RIVER。
- 用“下一步”逐步观看构建过程,或点击“播放”:每一步都把最轻的两棵树挂到一个新节点下,节点的权重是它们之和。
- 树完成后,点击一片叶子、表格中的一行或比特中的一段来跟踪一个符号,并比较磁贴中的总数。
树是怎样构建的
统计每个符号出现的次数,把每个符号都做成一棵只有一片叶子的树,权重为它的次数。然后重复一个简单的步骤:取出权重最小的两棵树,把它们挂到一个新节点下,新节点的权重是它们之和。每一步都会让树少一棵,所以对于 n 个符号,经过 n − 1 步后只剩下一棵树。罕见的符号最先被合并,位于深处;常见的符号很晚才被合并,靠近顶部。
读出编码
从顶部往下走:向左走一步加一个 0,向右走一步加一个 1。通往一片叶子的路径就是该符号的编码。因为符号只位于叶子上,所以没有哪个编码是另一个编码的开头,因此一串比特无需任何分隔符就能解码:沿着比特在树中往下走,每到达一片叶子,就写下它的符号,再从顶部重新开始。对于 ABRACADABRA,霍夫曼编码需要 23 比特,而每个字母 3 比特的定长编码需要 33 比特。
常见问题
为什么霍夫曼编码是最优的?
在所有为每个符号分配一串整数比特的编码中,对于给定的次数,没有哪种编码的总长度更短。证明沿着构造过程进行:在最优编码中,总可以让两个最罕见的符号成为最深层的兄弟节点,把它们合并后,剩下的是一个同类的、更小的问题。总比特数等于树中所有内部节点的权重之和。
什么是前缀码?
一种没有哪个码字是另一个码字开头的编码,例如 0、10、110 和 111。这个性质让解码器无需分隔符就能读取比特流,因为它总是知道一个码字在哪里结束。每个霍夫曼编码都是前缀码:符号只位于树的叶子上。
霍夫曼树是唯一的吗?
不完全是:当两棵树权重相同时,先取哪一棵都可以,左右也可以交换。不同的选择会得到不同的编码,但总比特数总是相同。本构建器总是以同样的方式处理权重相同的情况,所以同一段文本总是得到同一棵树。
霍夫曼编码离熵有多近?
平均码长至少等于熵,且比熵高出不到 1 比特。当每个概率都是二分之一的幂时,它恰好等于熵,例如“次数逐个减半”这个示例。算术编码和现代的区间编码器避开了整数比特的限制,能更加接近熵。
我的文本会被发送到任何地方吗?
不会。树和编码都在你的浏览器中计算,你的文本保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器