[参与有奖]给你一串编码，你有什么办法把他压到最短？【哈夫曼编码】
本帖最后由 高山 于 2026-10-3 17:03 编辑>>>如果你看不懂，推荐视频
https://www.bilibili.com/video/BV1wf421q7b8/?spm_id_from=333.1391.0.0&vd_source=4cfbfe21af0fd1db1e7483eee38d3aab
*仅做优秀视频推荐，本版与该作者无任何利益关系。
给你一串编码
现在你要开始压缩它了磁盘就那么点大，带宽就那么点贵
问：你要把它压到最短为止
你有多少种编码的方案呢？具体怎么编呢？在评论区回复本问题可获得鱼币+5 荣誉+5 数量有限
（强烈建议所有鱼油先自己拿纸笔编一编，再看答案）
【图 1】01 比特流穿过 Huffman 漏斗
各位鱼油大家好，今天这帖不灌水，咱们聊一个学数据结构的人谁都绕不开的东西——哈夫曼编码。
先别急着翻教材，咱们玩个游戏。
有一句话，ABRACADABRA（就是魔术师念的那句咒语），一共 11 个字母。要把它塞进计算机里：
最笨的办法，每个字母 8 个比特，11 × 8 = 88 个比特，这谁都知道是浪费；好一点的，这句话只用到 5 种字母，3 个比特就能区分 8 种符号，11 × 3 = 33 个比特。
还能再少吗？能，而且能压到 23 个比特。
更狠的是，有人从数学上证明了：这 11 个字母最少也得要 22.44 个比特（这个值叫熵，后面会讲）。也就是说 23 个比特几乎是贴着天花板走的，再压就是违反物理定律了。
这中间的魔法，是一个 1952 年、25 岁的博士生，在一篇只有四页纸的论文里给出的。
在讲算法之前
先认识一下造出它的人
因为这个名字背后的故事比算法本身还带劲
【图 2】哈夫曼生平时间线
一、神童开局
1925 年 8 月 9 日，戴维·艾伯特·哈夫曼（David Albert Huffman）出生在美国俄亥俄州的 Alliance。这孩子上学早得离谱——15 岁高中毕业，16 岁生日刚过就进了俄亥俄州立大学读电气工程，1944 年拿到学士学位时年仅 18 岁。
二、在驱逐舰上修雷达
毕业即入伍。他在美国海军服役两年，被派到太平洋战场的一艘驱逐舰上当雷达维护官，19 岁就成了所在海军区最年轻的军官，战后还跟着舰队在日本和中国海域扫雷。
这段经历其实很关键：一个天天跟雷达波形、声呐、电子对抗打交道的人，后来去琢磨"怎么用最少的比特表示一个信号"，一点也不奇怪。
三、MIT 与那篇四页论文
1949 年他回俄亥俄州立拿了硕士，1950 年北上 MIT 读博士。1952 年 9 月，他把自己的想法写成论文，发表在《IRE 会刊》（Proceedings of the IRE，也就是今天的 IEEE 会刊）上：
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, September 1952.
四页纸，引用量至今超过 5000 次。而这篇论文甚至不是他的博士学位论文——他 1953 年的博士论文叫《时序开关电路的综合》（The Synthesis of Sequential Switching Circuits），同样是块里程碑，还给他挣来了富兰克林学会的 Louis E. Levy 奖章。
四、那个被讲烂的段子，咱就不展开了
流传最广的版本是"他不想考期末考，于是去做了那个学期报告"。这里只说一件事：他后来回忆，如果当时知道那是连他老师和香农都啃不动的开放问题，他大概根本不敢去碰。无知者无畏，有时候是褒义。
五、后半生：从开关电路到折纸
1953 年他留校任教，1962 年成为 MIT 正教授。1967 年他南下加州，成为加州大学圣克鲁斯分校（UCSC）计算机科学系的创始元老，1970–1973 年当系主任，1994 年退休。
退休前后，他迷上了一件看起来跟编码毫无关系的事：折纸。更准确地说，是研究"零曲率曲面"的数学性质——一张纸怎样才能弯出复杂曲面又不产生拉伸。他因此成了数学折纸（mathematical origami）领域的先驱之一，那些带曲线折痕的纸雕塑，至今还在被人研究。
1999 年 10 月 7 日，哈夫曼因癌症去世，享年 74 岁。就在同年，他获得了 IEEE 的理查德·汉明奖章（Richard W. Hamming Medal）——这是他生前得到的最后一项荣誉。
他一生从未为哈夫曼编码申请过任何专利。有人问他为什么，他说了句特别漂亮的话：
My products are my students.（我的产品，是我的学生。）
哈夫曼编码不是从石头里蹦出来的
在它前面站着三位前辈
第一位：摩尔斯电码（1830s–1840s）
这是"变长编码"真正的祖师爷，比计算机早了一百多年。它的设计原则朴素得可爱：越常用的字母，代码越短。
字母出现频率摩尔斯电码码长
E最高·1
T很高—1
S较高···3
Q极低--·-4
【图 3】摩尔斯电码：越常用越短
英文里 E 出现得最频繁，所以它就一个点；Q 罕见得要命，那就四个符号伺候。这已经是哈夫曼思想的灵魂了，只不过它是靠经验拍脑袋定出来的，没人能证明它最优。
第二位：香农（1948）
1948 年，克劳德·香农发表《通信的数学理论》，创立信息论。他给出了一个公式，直接给所有压缩算法划了一条不可逾越的底线：
H = - Σ p(i) · log₂ p(i) （单位：bit / 符号）
这个 H 叫信息熵。它的意思是：不管你多聪明，平均下来每个符号至少要 H 个比特，再少就要丢信息了。对 ABRACADABRA 来说，H ≈ 2.04 bit/符号，所以 11 个字母最少 22.44 比特——这就是前面那个"物理定律"的来历。
第三位：香农-范诺编码（1949）
有意思的是，香农提出了熵，却没给出最优的编码方法。真正落地的是 MIT 的罗伯特·范诺（Robert M. Fano）——也就是哈夫曼那门课的老师。他和香农各自独立提出了一种做法，后来合称香农-范诺编码：
① 把符号按出现概率从大到小排队；② 从中间"切一刀"，把队伍分成概率和尽量接近的两组，上面那组前缀加 0，下面那组前缀加 1；③ 对每组重复第二步，直到每组只剩一个符号。
看出来了吗？它是自顶向下的——先有根，再一层层往下劈。问题恰恰出在这儿："这一刀切在哪里"没有任何最优性保证。
举个数：概率分布为 0.35、0.17、0.17、0.16、0.15 时，香农-范诺的平均码长是 2.31 bit，而最优前缀码只要 2.30 bit。差距不大，但它确实是"次优"的——工程上这一点点就是钱。
【图 4】自顶向下 vs 自底向上
到这里
似乎一切都挺顺利
但是
变长编码有个致命的坑
——你怎么知道一个码字到哪儿结束？
假设你很不走心地定了这么一套码：A=0，B=01，C=1。现在对方收到 01，请问你说的是"AB"还是"C"？两个都对，那就是两个都错。这种编码有歧义，压完了根本解不回来。
【图 5】有歧义 vs 前缀码
解决办法是加一条铁律：任何一个码字，都不能是另一个码字的前缀。满足这条的编码叫前缀码（prefix-free code）。比如 A=0，B=10，C=11，"01"只能读成 A+C，唯一解。
而这条铁律有一个极其漂亮的等价物：把每个符号都放在二叉树的"叶子"上，从根走到叶子的 0/1 路径就是它的码字。因为叶子下面不会再挂东西，所以天然不可能成为别人的前缀。
于是，"设计一套最短的前缀码"这个听上去很抽象的问题，被翻译成了一个画图问题：
找一棵二叉树，让 Σ (叶子权值 × 该叶子的深度) 最小
—— 也就是「带权路径长度 WPL」最小
哈夫曼那天的灵光一闪，就是在这个问题上换了个方向：范诺是从根往下劈，他改成从最底下往上长。
为什么从底下往上就对了？关键在于一个可以严谨证明的性质：在一棵最优树里，权值最小的那两个节点，一定是最深的一对兄弟节点。既然它俩必定是兄弟，那就先把它们合并成一个新节点，问题规模减一，剩下的子问题照样最优——这就是贪心。每一步都取当下最小的两个，局部最优竟然就是全局最优。
光说不练假把式
现在掏出纸笔
咱们全程手动建一棵哈夫曼树
第 0 步：数数，排队。
先统计 ABRACADABRA 里每个字母出现的次数，这个次数就是"权值"。
字符ABRCD
次数52211
原串：A B R A C A D A B R A，共 11 个字符。接下来按权值从小到大排好队：C(1)、D(1)、B(2)、R(2)、A(5)。
【图 6】第 0 步：按权值从小到大排队
第 1 步：揪出最小的两个，合并。
C(1) 和 D(1) 最小，把它俩合成一个新节点 N1，权值为 1+1=2。注意：新节点要放回队列里重新参与排序，不是扔在一边不管。
【图 7】第 1 步：C(1) + D(1) → N1(2)
第 2 步：再来一次。
现在队列里是 N1(2)、B(2)、R(2)、A(5)。最小的两个是 B(2) 和 R(2)，合并成 N2(4)。
【图 8】第 2 步：B(2) + R(2) → N2(4)
第 3 步：森林里只剩三棵树。
队列变成 N1(2)、N2(4)、A(5)。最小的两个是 N1(2) 和 N2(4)，合并成 N3(6)。
【图 9】第 3 步：N1(2) + N2(4) → N3(6)
第 4 步：最后一步，树成了。
只剩 A(5) 和 N3(6)，合并成根节点 11——正好等于字符总数，说明你没算错。一共合并了 4 次，也就是字符种类数 − 1。
【图 10】第 4 步：最终哈夫曼树与编码
用纯文本画出来长这样，约定走左边记 0、走右边记 1：
(11)
/ \
A(5) (6)
/ \
(2) (4)
/ \ / \
C(1) D(1) B(2) R(2)
于是得到编码表：
字符次数哈夫曼编码码长
A501
B21103
R21113
C11003
D11013
把原串逐字替换：
A B R A C A D A B R A
0110111 0100 0101 0110111 0
压缩结果：01101110100010101101110 共 23 个比特
总比特数：5×1 + 2×3 + 2×3 + 1×3 + 1×3 = 23，平均 23 ÷ 11 ≈ 2.09 bit/字符。
三种方案摆在一起看：
方案总比特数平均每字符
定长 8 bit888.00
定长 3 bit333.00
哈夫曼232.09
香农熵（理论下界）22.442.04
【图 11】三种方案对比
看到没有——哈夫曼离理论极限只差 0.05 bit/字符。这就是为什么它配得上"最优"两个字。
补一句：哈夫曼编码不是唯一的。
① 每次合并时谁挂左边谁挂右边完全随意，得到的码字整体 0/1 互换，码长不变，压缩率完全一样；② 出现权值相同的节点时，选哪两个合并也随意，这种时候码长可能变，但总比特数一定相同。所以别跟同学对答案对不上就怀疑人生。
手动建树会了
就该让计算机替我们干这活了
回头看那 4 步操作，你会发现真正在做的事只有一件：反复"取最小的两个 → 合并 → 放回去"。
这个动作有个现成的工具：STL 的 priority_queue，配上一个"小的优先"的比较器，就是一个最小堆。取最小 O(log n)，插入 O(log n)，总共 n−1 次合并，整体复杂度 O(n log n)；如果权值本来就有序，还能做到 O(n)。
【图 12】priority_queue 建树示意
第一块：节点结构
struct Node {
charch; // 叶子存字符，内部节点为 0
int freq; // 权值
Node* left;
Node* right;
Node(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
Node(int f, Node* l, Node* r) : ch(0), freq(f), left(l), right(r) {}
};
第二块：比较器（坑点预警）
priority_queue 默认是大顶堆，我们要的是小顶堆，所以比较器要反过来写。很多鱼油在这里栽跟头：
struct Cmp {
bool operator()(const Node* a, const Node* b) const {
if (a->freq != b->freq) return a->freq > b->freq;// 频率小的先出堆
return a->ch > b->ch; // 频率相同时给个稳定顺序
}
};
记不住就记口诀：priority_queue 里 return 的是"谁该排在后面"。
第三块：建树（核心就这几行）
Node* buildTree(const map<char, int>& freq) {
priority_queue<Node*, vector<Node*>, Cmp> pq;
for (map<char,int>::const_iterator it = freq.begin(); it != freq.end(); ++it)
pq.push(new Node(it->first, it->second)); // 每个字符先当一棵单节点树
while (pq.size() > 1) {
Node* a = pq.top(); pq.pop(); // 最小的
Node* b = pq.top(); pq.pop(); // 第二小的
pq.push(new Node(a->freq + b->freq, a, b)); // 合并，放回堆里
}
return pq.top(); // 剩下那个就是根
}
第四块：递归走一遍树，抄下编码表
void genCode(Node* root, string path, map<char, string>& table) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) { // 到叶子了
table = (path == "" ? "0" : path); // 只有一种字符时的特例
return;
}
genCode(root->left,path + '0', table);
genCode(root->right, path + '1', table);
}
几个面试常问的小问题
① 一共会创建多少个节点？ n 个叶子，每次合并新增 1 个，合并 n−1 次，所以是 2n−1 个。用数组实现时直接开 2n−1 的空间就行。
② 解码怎么解？不用查表，拿着比特流从根往下走，撞到叶子就吐一个字符并回到根，比编码还简单。
③ 解码器怎么知道码表？真实场景里要么把频率表一起写进文件头，要么用"自适应哈夫曼编码"（收发双方同步更新树）。所以压缩后的文件其实包含"码表 + 比特流"两部分，这就是为什么哈夫曼压缩小文件时有可能越压越大。
最后
说点不那么完美的事
哈夫曼编码很牛，但它有两个绕不开的短板：
一、每个符号至少要 1 个比特。如果某个符号的概率高达 0.9，熵算下来只需要 0.15 bit，可哈夫曼最少也得给 1 bit，这时候差距就被拉开了。
二、它只能给符号"逐个"编码。想突破这个限制，就得请出算术编码和后来的 ANS（非对称数系）——它们能把一整串符号压成一个小数，逼近熵的能力更强。今天的很多新格式已经换成它们了。
但这丝毫不妨碍哈夫曼编码活得很好：你打交道的 ZIP、PNG、JPEG、MP3、PDF、传真机、早期的调制解调器……背后都有这棵小树的影子。一个 25 岁的博士生四页纸的作业，七十多年后还在替全世界省钱。
故事的结尾，再念一遍他那句话吧：
My products are my students.
鱼油们，写代码也是一样的——你留下的不是那几行代码，是你自己。
下面是一份可直接编译运行的完整源码，回复可见 ↓
**** Hidden Message *****
三道思考题，不用回复也能看，欢迎在回帖里讨论：
回答思考题将获得鱼币奖励
① 如果待压缩的文本里只有一种字符（比如 "AAAAAA"），上面的 genCode 会给出什么？为什么我在代码里写了那个 path == "" 的特判？
② 哈夫曼树里所有字符的码长之和有没有可能比定长编码更差？试着构造一个例子，或者证明它不会。
③ 压缩后的文件必须带上码表才能解码。设想你要压缩一段只有 10 个字符的短文本，码表的开销会不会让文件反而变大？真实工程里怎么解决？
—— 全文完，感谢各位鱼油看到这里，有错漏欢迎回帖拍砖 ———— 部分内容由AI生成 ——
结果康这个↑ @小甲鱼 @小甲鱼的二师兄 来康康我滴帖子！ 每个字符是一个叶子，顺着树杈找到叶子对吧{:10_275:} 丫丫的雅雅 发表于 2026-10-2 20:59
每个字符是一个叶子，顺着树杈找到叶子对吧
是滴，例如左0右1，就能对应唯一的子叶节点啦~ 这个排版真的绝了！
我要好好向你学习！！ 小甲鱼的二师兄 发表于 2026-10-2 22:53
这个排版真的绝了！
我要好好向你学习！！
哈哈哈谢谢，可以让AI给你一个排版规划，甚至直接生成discuz代码，会简单一些~ {:7_145:} 不会 {:7_116:} 删掉 厉害了我的哥有学到 不会 学到了学习啦 这是论文啊我嘞个豆 哇，太棒了，本来看课看的都看不懂了，现在还得看这个然后还让答题！？我不会 顺着树杈 我表示看不懂唉 学习数据结构，确实绕不开哈夫曼编码 哈夫曼编码，哈夫曼树，数据结构学过