霍夫曼编码

什么是霍夫曼编码？

霍夫曼编码（Huffman Coding）是一种可变长度前缀编码。它会让出现频率高的字符使用更短的编码，让出现频率低的字符使用更长的编码，从而达到压缩数据的目的。

它不是加密，而是一种压缩编码。CTF 中常见形式是给出字符频率、霍夫曼树或编码表，然后要求还原明文。

核心特点

• 高频字符编码短，低频字符编码长。
• 每个字符的编码都不是另一个字符编码的前缀。
• 解码必须知道霍夫曼树或编码表。
• 同一组频率可能构造出不同但等价的霍夫曼编码表。

构造流程

以字符频率为例：

字符	频率
A	5
B	2
C	1
D	1

构造步骤：

1. 每个字符作为一个节点。
2. 每次取频率最小的两个节点合并。
3. 新节点频率等于两个子节点频率之和。
4. 重复直到只剩一棵树。
5. 从根节点到叶子节点的路径就是字符编码，通常左边记 0，右边记 1。

可能得到的编码表：

字符	编码
A	1
B	01
C	000
D	001

解码示例

已知编码表：

字符	编码
A	1
B	01
C	000
D	001

密文：

101000001

从左到右匹配前缀：

1    -> A
01   -> B
000  -> C
001  -> D

所以：

101000001 -> ABCD

为什么能直接解码？

霍夫曼编码是前缀码。也就是说，一个字符的编码不会是另一个字符编码的开头。

例如 A = 1 时，其它字符编码不能以 1 开头。这样从左到右读到某个完整编码时，就可以立即确定字符，不需要回溯。

CTF 识别要点

• 题目给出字符频率表、权重表或二叉树。
• 密文通常是很长的 0/1 串。
• 需要编码表或树才能稳定解码。
• 如果构造出的明文不对，检查左右分支的 0/1 是否反了。