MATLAB/C++实现香农码、费诺码与Huffman编码效率对比

简介：这份中南大学《信息论与编码》编码部分实验报告，面向正在学习信息论与编码、需要完成课程实验的本科生与自学者，解决香农码、费诺码与Huffman编码原理理解及编程实现的问题，属于专业课实验类文档资源。压缩包内共1个docx文件，约792KB，内容涵盖实验目的与要求、课程设计指导书，以及用MATLAB、C/C++实现香农码、费诺码和Huffman编码的说明、源代码与运行结果截图，还包括应用Huffman编码完成文件压缩与解压缩的实践环节。报告以概率序列0.4、0.2、0.1、0.1、0.15、0.05为测试案例，完整呈现概率排序、累加概率计算、码字生成与编码效率分析的推导过程，并对比三种编码的效率差异。读者可据此直接参照实验结构、复用源代码框架、核对运行结果，理解带权路径长度最短的二叉树构造思路与优先队列实现方式，同时练习C/C++编程与数据压缩的实际应用，为后续信息处理与通信方向的学习打基础。目前已有102人学习下载。

1. 六个概率值撑起的一张效率对比图

信息论与编码课的编码部分实验，看着是交三份代码，真正考的是同一件事：给一组信源概率，怎么在“平均码长最短”和“前缀可译”之间取舍。素材里的测试数据 0.4、0.2、0.15、0.1、0.1、0.05 存在 gailv.txt 中，MATLAB 用 load 读进来，降序排完，三条路线就分岔了——香农码用累加概率定码长，费诺码用概率和二分定分组，Huffman 码用反复合并最小两个节点定树形。三种码的平均码长和效率最后会画进同一张 bar 图；把结果和信源熵摆在一起，损失藏在哪一步基本藏不住。要交实验、代码能跑但结果对不上的同学重点看第 2、3 章；准备把变长编码落进文件压缩、卡在位流和码表头上的开发者从第 4 章往下读。

2. 香农码的累加概率与码长取整：MATLAB 逐位展开的写法

2.1 香农第一定理给出的码长上下界

香农码的码长公式只有一行：l_i = ceil(-log2(p_i))。它直接从香农第一定理推出来——对任意前缀码，平均码长L满足H ≤ L < H + 1。取l_i = ceil(-log2 p_i)时，有-log2 p_i ≤ l_i < -log2 p_i + 1，两边同乘p_i、对i求和，就得到上面这个夹逼关系。

提示：这个上界说明香农码不保证最优，只保证不比熵差超过 1 bit/符号。概率分布越不均匀，ceil取整带来的浪费越明显。

码字怎么来的？把概率降序排好，令F_1 = 0，F_i = Σ_{j<i} p_j，第i个符号的码字就是F_i的二进制小数展开取前l_i位。前缀可译性靠的是两点：F_i随i单调递增，相邻两个累加概率之间的间隔至少是p_i；而p_i ≥ 2^{-l_i}，间隔不小于l_i位二进制小数的最小分辨率，所以取l_i位不会串码。这个论证比“看起来不会冲突”要硬，写实验报告的时候可以直接用。

2.2 从 gailv.txt 到降序概率向量

原始素材里用load gailv.txt直接读文件，这个写法只在文件是纯数字矩阵时成立。文档里写的数据用逗号分隔，而且标明“可能是全角或半角”，load遇到全角逗号会直接报错或者解析出奇怪维度。稳妥一点的做法是先读出字符串再清洗：

raw = fileread('gailv.txt'); % 整个文件读成 char 数组 raw = strrep(raw, '，', ' '); % 全角逗号 → 空格 raw = strrep(raw, ',', ' '); % 半角逗号 → 空格 A = sscanf(raw, '%f').'; % 按浮点数解析成行向量 A = A(A > 0); % 过滤 0 和空值，避免 log2(0) 得到 -Inf A = sort(A, 'descend'); % 降序排列，香农码的第一步硬性要求 n = numel(A);

逻辑说明：sscanf沿着空格切分并逐个读浮点数，比load宽容得多。A(A > 0)这一步不是洁癖，实测中最容易踩的坑就是源数据里混进 0 或者空行，-log2(0)返回Inf，后面ceil出来还是Inf，循环里取整就会崩。降序排列必须有，因为累加概率的单调性建立在p_1 ≥ p_2 ≥ ... ≥ p_n上，乱序排进去得到的是另一组码字，而且往往不是前缀码。

2.3 累加概率的二进制逐位展开

到这一步数据已经干净，接着算码长和累加概率。注意B(1)固定为 0，循环从i = 2开始写，这是最容易写错的一处：

l = ceil(-log2(A)); % 每个符号的码长，1×n B = zeros(1, n); % 累加概率 F_i for i = 2:n B(i) = A(i-1) + B(i-1); end

二进制展开没有现成函数直接输出定长位串，手写一个乘 2 取整的循环最稳：

ST = strings(1, n); for i = 1:n frac = B(i); bits = zeros(1, l(i)); % 预分配，避免动态增长 for j = 1:l(i) frac = frac * 2; % 乘 2，整数部分就是当前位 bits(j) = floor(frac); frac = frac - bits(j); % 减去整数部分，留下小数继续 end ST(i) = strjoin(string(bits), ''); % 拼成位串，比如 "011" end

参数说明：bits(j)只能是 0 或 1，floor也可以换成fix，但概率都是正数两者等价。strjoin前先转string再拼，避免把数值数组隐式转成字符时中间插空格。用测试数据实跑一遍，得到的码字如下：

对照第 2.1 节的间隔论证：F_2 = 0.40取 3 位是 011，F_3 = 0.60取 3 位是 100，两者第一位就分开了，不会出现一个码字是另一个前缀的情况。

2.4 用熵和平均码长算效率

效率就是熵除以平均码长，两行就够，但要注意log2对行向量的默认行为是逐元素运算，必须配.*：

H = -sum(A .* log2(A)); % 信源熵，单位 bit/符号 L = sum(A .* l); % 平均码长 = Σ p_i * l_i eta = H / L; % 编码效率，越接近 1 越好 fprintf('熵 = %.4f 平均码长 = %.4f 效率 = %.2f%%\n', H, L, eta*100);

这组数据跑出来H ≈ 2.2843、L = 2.9、eta ≈ 78.8%。效率偏低的原因是 0.4 这个高概率符号的码长被ceil抬到了 2 位，而理论上 1.32 位就够；0.05 的码长 5 位相对“理想值”4.32 也浪费了将近 0.7 位。香农码的问题不在原理，在于每个符号都必须向上取整到整数位，这就注定了它平均要比 Huffman 差一截。

3. 费诺码的递归分组：切割点选择与编码串拼接

3.1 费诺码与香农码的分岔点

费诺码和香农码都用降序概率，但“决定码字”的机制完全不同。香农码是自顶向下算出来的——先算码长，再取累加概率的前l_i位；费诺码是一路劈出来的——每轮把当前概率集合按“尽量等分成两半”的规则切开，一边贴 0，一边贴 1，然后对两半递归做同一件事，直到每组只剩一个符号。

两者的可译性来源也不一样。香农码依赖p_i ≥ 2^{-l_i}这个不等式；费诺码直接把码字做成了树上的一条根到叶路径，天然就是前缀码。所以费诺码不需要给每个符号单独算码长，码长是分组的副产物，是它所在叶子的深度。

3.2 一次分割点的两种判据

分割点的判定是整段代码里最需要想清楚的地方，常见做法有两种：

第一种是“不超过一半就累加”，从左往右加概率，只要累加和不越过总和的一半就继续加，一旦越界就停在上一位置。第二种是“离一半最近”，比较停在当前位置和再往前一格时哪个更接近total/2，取更近的那个。第一种实现简单、结果稳定；第二种在两边概率差很小时会更贴近 0.5，但会导致同一组概率在不同实现下切出不同码字。

注意：两种判据都是合法的费诺码构造，但换了判据之后码长会变。实验报告里要么统一用第一种并在说明里写清楚，要么在注释里标明用的是哪一种，否则复现的人和你的结果对不上。

原始素材里的费诺码代码有一段if abs(sum(B(p:k,1))-a) <= abs(sum(B(p:k+1,1))-a)，走的是第二种思路。这里选第一种给出可复现版本，因为它的边界行为更好预测。另外一个必须处理的边界是：如果第一个概率本身就已经超过总和的一半（比如p = [0.6, 0.2, 0.2]），累加和一开始就越界，切点会停在 0，左右两半其中一个变成空集，递归直接死循环。所以切点最小要强制推到 1。

3.3 用队列展开分组并拼接码字

递归在 MATLAB 里写起来容易出现作用域问题，用一个显式队列做迭代展开更省事：

function FN = fano_code(A) % A: 已降序排列的概率行向量 n = numel(A); FN = strings(1, n); % 每个符号的最终码字 queue = {{1:n, ""}}; % 队列元素：{下标集合, 前缀} while ~isempty(queue) cur = queue{1}; queue(1) = []; sub = cur{1}; pre = cur{2}; if numel(sub) == 1 FN(sub) = pre; % 组内只剩一个符号，前缀即码字 continue; end total = sum(A(sub)); % 当前组总概率 acc = 0; cut = 0; while cut < numel(sub)-1 && acc + A(sub(cut+1)) <= total/2 acc = acc + A(sub(cut+1)); % 不超过一半就继续加 cut = cut + 1; end if cut == 0, cut = 1; end % 防止首项就超过一半导致空组 queue{end+1} = {sub(1:cut), pre + "0"}; queue{end+1} = {sub(cut+1:end), pre + "1"}; end end

逻辑说明：sub保存的是原数组下标而不是概率值，这样最后FN(sub) = pre能把码字准确写回对应符号。队列用元胞数组模拟，queue{end+1}入队、queue(1) = []出队，先进先出保证分组是按层展开的。pre + "0"用的是字符串加法，pre是string类型，直接拼不会出错。

对测试数据跑一遍，分组轨迹和结果如下：

对应的码长是 1、2、3、4、5、5，平均码长L = 2.4，效率2.2843 / 2.4 ≈ 95.2%。比香农码高出一大截，核心差异就在 0.4 这个符号——香农码给它 2 位，费诺码给 1 位。

3.4 结果对不上时先查这三处

费诺码跑出来和同学不一样，九成出在下面三点。第一，概率有没有降序，没排过的话第一刀切出来的组完全变形。第二，切点判据用的是“不超过一半”还是“离一半最近”，这两种在 0.15/0.25 这种接近对半的边界上会分道扬镳。第三，传入递归的是概率值还是下标，如果是概率值，相等等概率时find会返回多个位置，码字就会重复写。第三个坑最隐蔽，用小数组手推一遍再跟程序结果比，比盯着屏幕看变量快得多。

4. C/C++ 实现 Huffman 树：小根堆、回溯码表与索引矩阵对照

4.1 节点结构体与小根堆选型

Huffman 建树的核心操作是“每次取权重最小的两棵树合并”，能高效支持这个操作的容器就是优先队列。C++ 里用std::priority_queue配自定义比较器，几行就能起一个小根堆；手写堆也行，但没必要。节点里除了权重和孩子指针，还要留一个父指针和符号下标，父指针是给回溯码表用的：

#include <queue> #include <string> #include <vector> struct Node { double w; // 叶子为概率，内部节点为子树概率和 int sym; // 叶子对应信源符号下标，内部节点为 -1 Node *l, *r, *p; // 左孩子、右孩子、父亲 Node(double w_, int s) : w(w_), sym(s), l(nullptr), r(nullptr), p(nullptr) {} }; struct Cmp { // 注意：std::priority_queue 默认是"最大"在堆顶， // 比较器返回 a->w > b->w 才能让权重最小的浮上来 bool operator()(Node* a, Node* b) const { return a->w > b->w; } };

参数说明：w用double而不是float，多轮累加之后float的舍入误差会让本来就相等的权重排错顺序，从而产生结构不同但代价相同的树，输出码表就对不上了。sym只对叶子有效，-1表示这是合并出来的内部节点。

4.2 建树：反复取最小两棵子树

建树循环本身只有六行，但每次合并都要把指针关系接好，不然回溯时会断链：

Node* buildHuffman(const std::vector<double>& p) { std::priority_queue<Node*, std::vector<Node*>, Cmp> pq; for (int i = 0; i < (int)p.size(); ++i) pq.push(new Node(p[i], i)); while (pq.size() > 1) { Node* a = pq.top(); pq.pop(); // 当前最小 Node* b = pq.top(); pq.pop(); // 当前次小 Node* c = new Node(a->w + b->w, -1); c->l = a; c->r = b; a->p = c; b->p = c; // 父指针必须回填，否则回溯不了 pq.push(c); // 合并结果回到堆里，参与下一轮 } return pq.top(); // 堆中最后的节点就是树根 }

对测试数据跑一遍，堆的变化过程是这样的：

只做了n-1 = 5次合并。带权路径长度WPL = Σ p_i · l_i在建树过程中其实等于所有内部节点权重之和，也就是 0.15 + 0.25 + 0.35 + 0.60 + 1.00 里除根之外的和，但最直观的算法还是从叶子往上累加。

4.3 回溯生成码表并算带权路径长度

码表生成有两种方向：从根往下走、边走边记 0/1；或者从叶子沿父指针爬到根。第二种更省事，代价是路径记反了必须翻转：

#include <algorithm> #include <functional> std::vector<std::string> makeCode(Node* root, int n) { std::vector<std::string> code(n); std::function<void(Node*)> dfs = [&](Node* cur) { if (!cur) return; if (cur->sym >= 0) { // 叶子节点 std::string s; for (Node* t = cur; t->p; t = t->p) s += (t->p->l == t) ? '0' : '1'; // 是左孩子记 0，右孩子记 1 std::reverse(s.begin(), s.end()); // 叶→根记出来的位是反的 code[cur->sym] = s; } dfs(cur->l); dfs(cur->r); }; dfs(root); return code; } double weightPathLength(const std::vector<double>& p, const std::vector<std::string>& code) { double wpl = 0; for (size_t i = 0; i < p.size(); ++i) wpl += p[i] * code[i].size(); return wpl; }

逻辑说明：t->p->l == t判断当前节点是父亲的左孩子还是右孩子，前者对应码元 0，后者对应 1。因为循环是从叶子往根走，先记下的位其实是码字的末位，所以最后必须std::reverse。这组数据出来的码长是 1、3、3、4、4、3，WPL = 2.35，效率2.2843 / 2.35 ≈ 97.2%，比费诺码再高两个点。

4.4 MATLAB 版 Huffman 的 Index 矩阵写法对照

原始素材里还有一版 MATLAB 的 Huffman，用Index矩阵记录每轮合并的节点位置，再用Char矩阵存每一层的位串。这种写法的好处是不用指针，全程用数组下标索引，适合教学演示；坏处是长度固定的二维字符矩阵要开n × n，稍微大一点的信源就吃内存。它和 C++ 版在逻辑上一一对应：Index第k行记录第k轮合并的两个节点在原始序列中的位置，Char的第k行记录往回走时是往左还是往右。生成结果时从Char的第 1 行按Index(1,:)的对应关系映射回原符号——这一步是最容易出错的地方，索引错一位，整个码表就整体错位，解压出来的全是乱码。

提示：无论指针版还是数组版，验证手段都一样——把Σ p_i · l_i和第 4.2 节内部节点权重之和对比，两者相等；再把码表逐条检查是否满足前缀关系，这比盯着树看图快。

5. 把 Huffman 码表写进文件：位流拼接与解压校验

5.1 位写入器与不足 8 位的补齐

有了码表就能做文件压缩，麻烦出在“码字是变长的、文件读写是 8 位对齐”这个错位上。需要一个写位缓冲区，攒够 8 位才真正落盘：

struct BitWriter { std::ofstream& out; unsigned char buf = 0; int bitcnt = 0; // 当前缓冲区里已经有几位 explicit BitWriter(std::ofstream& o) : out(o) {} void put(int bit) { buf = (buf << 1) | (bit & 1); if (++bitcnt == 8) { out.put((char)buf); buf = 0; bitcnt = 0; } } void flush() { if (bitcnt) { // 尾部不足 8 位，左移补 0 后写出 buf <<= (8 - bitcnt); out.put((char)buf); } } };

参数说明：bitcnt既是“已有几位”的计数器，也是flush判断尾部有没有残余位的依据。buf <<= (8 - bitcnt)把剩余位顶到高位，低位的 0 是填充位，解压时靠文件头里记录的有效位数把它们丢掉。少写这一步，尾部字节直接丢失，解压出来最后一个符号就没了，而且这种错误只在压缩数据不是 8 的整数倍时出现，很容易被忽略。

5.2 文件头协议决定了解压能不能对上

解压端要重建同一棵树，必须能从文件里读回码表。常见做法是在位流前面加一段明文头部：

[符号数 n: 2 字节] [重复 n 次: 符号下标 1 字节 | 码长 1 字节 | 码字字节序列 (码长+7)/8 字节] [有效位数 valid_bits: 1 字节] [压缩位流]

顺序必须和写入时严格一致，符号下标写大端还是小端也要两边统一。字段长度用固定宽度而不是变长整数，是为了一边读一边就地重建码表，不需要把整个文件先加载到内存。头部里记的是码长而不是码字本身也够用——读出码长就能重建树的形状，码字顺着读位流就行，但那样实现更绕，用固定长度的码字描述换实现简单更划算。

5.3 解压时逐位走树与一个验证技巧

解压不需要查表，从根开始逐位走树最直观：

while (true) { int bit = reader.get(); // 逐位从位流取，末尾按 valid_bits 截断 if (bit < 0) break; cur = bit ? cur->r : cur->l; if (cur->sym >= 0) { // 走到叶子，输出一个符号并回到根 out.put((char)cur->sym); cur = root; } }

校验环节有个偷懒但有效的办法：把压缩再解压的结果和原文件做一次二进制比对，同时统计压缩后字节数和原文件字节数。用infosource.txt这类文本文件实测，压缩比通常在 55% 到 65% 之间，低于这个区间说明码表头部开得太大或者码字没生效；解压结果和原文不一致，先检查flush里的补零和valid_bits是不是配套，再看码表头部的字节对齐——这两处出问题的概率远高于树建错。

本文还有配套的精品资源，点击获取