深入理解与实战：基于 MATLAB 的算术编码与解码

2026-02-16 00:57:27 0条评论 3次阅读 0人点赞

在数据压缩的广阔天地中，我们经常寻找一种能接近“香农极限”的编码方式。算术编码正是这样一种强大的无损数据压缩技术。不同于赫夫曼编码为每个符号分配固定长度的码字，算术编码的核心思想是将整个输入消息映射为 $[0, 1)$ 区间内的一个单一浮点数。消息越长，这个数所需的精度就越高。

在这篇文章中，我们将深入探讨算术编码的原理，并一起编写 MATLAB 代码来实现它。你将学到如何构建概率模型，如何通过递归区间更新来压缩数据，以及如何从最终的数值中精确还原原始信息。这不仅是理论练习，更是掌握高阶数据压缩技术的必经之路。

什么是算术编码？

让我们先从一个简单的场景开始。假设我们要传输单词 "hey"。传统的 ASCII 编码会为每个字符分配 8 位，总共需要 24 位。但这显然不是最优的，因为字母出现的频率并不均匀。

算术编码的魔力在于，它不是单独处理每个字符，而是根据字符出现的概率，将整个消息作为一个整体来处理。想象一下区间 $[0, 1)$。我们首先根据符号的概率将这个区间划分成若干个子区间。每当我们读入一个新符号，我们就将当前关注的区间缩小到该符号对应的子区间。随着符号序列的增加，我们关注的区间会变得越来越窄。

最终，任何一个落在这个极小区间内的数字，都可以唯一地代表这个符号序列。这意味着，我们只需要传输这个数字（以及必要的精度信息），接收方就能还原出原始消息。这种方法在处理高概率符号时极其高效，能够非常接近理想的熵极限 $-\log_2 P$。

核心原理：概率与区间

要实现算术编码，我们需要关注三个核心要素：符号集、概率分布和区间更新。

符号集与概率：首先，我们需要统计输入字符串中每个字符出现的频率。例如，在字符串 "banana" 中，‘a‘ 出现了 3 次，‘n‘ 出现了 2 次，‘b‘ 出现了 1 次。这些频率决定了我们在划分区间时的权重。
初始区间：编码开始时，我们的区间总是 $[0, 1)$。
区间递归：这是算法的心脏。对于输入序列中的每一个符号，我们将当前的 $[low, high)$ 区间根据符号的概率进行划分。新的区间将变为当前符号对应的子区间。

在 MATLAB 中实现算术编码

让我们动手编写代码。我们将使用 MATLAB 强大的矩阵处理能力来简化我们的逻辑。为了演示，我们将字符串 "GeeksforGeeks" 作为输入（你完全可以将其替换为你想要压缩的任何文本）。

#### 第一步：统计与模型构建

首先，我们需要分析输入字符串，找出所有唯一的字符以及它们出现的概率。这相当于建立了一个静态的统计模型。

% 清除工作区，确保环境干净
clc; clear; close all;

% 定义输入字符串
% 提示：你可以修改这里的字符串来测试不同的数据集
str = ‘GeeksforGeeks‘;
fprintf(‘输入的字符串是 : %s
‘, str);

% 获取字符串长度
len = length(str);
fprintf(‘字符串的长度是 : %d
‘, len);

% 获取唯一字符集
% unique 函数会返回去重并排序后的字符
u = unique(str);
fprintf(‘唯一字符是 : %s
‘, u);

% 获取唯一字符的数量
len_unique = length(u);
fprintf(‘唯一字符的数量是 : %d
‘, len_unique);

% 初始化计数和概率数组
z = zeros(1, len_unique); % 用于存储每个字符的计数
p = zeros(1, len_unique); % 用于存储每个字符的概率

% 遍历唯一字符集进行统计
for i = 1 : len_unique
   % 统计当前字符 u(i) 在字符串 str 中出现的次数
   z(i) = length(findstr(str, u(i)));

   % 计算概率：出现次数 / 总长度
   p(i) = z(i) / len;
end

% 显示统计结果
disp(‘字符计数; 
display(z);
disp(‘字符概率; 
display(p);

#### 第二步：构建累积概率表

在算术编码中，我们关注的是累积概率。这将把 $[0, 1)$ 区间分割成若干个子区间。例如，如果符号 ‘A‘ 的概率是 0.2，‘B‘ 是 0.3，那么 ‘A‘ 对应的区间是 $[0, 0.2)$，‘B‘ 对应的区间是 $[0.2, 0.5)$。

% 计算累积概率
% cumsum 函数计算向量的累积和
% 例如：如果 p = [0.1, 0.2, 0.7], cpr 将是 [0.1, 0.3, 1.0]
cpr = cumsum(p);

% 为了方便计算区间边界，我们在前面补一个 0
% newcpr 现在的长度是 len_unique + 1
% newcpr(i) 代表第 i 个符号的区间下界
% cpr(i) 代表第 i 个符号的区间上界
newcpr = [0 cpr];

disp(‘累积概率 (上界); 
display(cpr);
disp(‘区间边界 (补0后):‘); 
display(newcpr);

% 构建查找表 (Lookup Table)
% 这个矩阵将存储每个字符对应的区间 [low, high)
interval = zeros(len_unique, 2);
for i = 1 : len_unique
   interval(i, 1) = newcpr(i);   % 下界
   interval(i, 2) = cpr(i);       % 上界
end

% 显示最终的查找表
% 每一行代表一个字符的区间范围
disp(‘查找表 (字符区间):‘); 
display(interval);

#### 第三步：编码过程—— 区间的舞蹈

这是最激动人心的部分。我们将遍历输入字符串中的每一个字符，并根据上述查找表不断缩小我们的目标区间。

% 初始化编码区间为 [0, 1)
current_low = 0;
current_high = 1;

% 遍历输入字符串中的每一个字符
for i = 1 : len
   % 在唯一字符集中查找当前字符对应的索引
   % 这将告诉我们应该使用哪一行数据来更新区间
   for j = 1 : len_unique
       if str(i) == u(j)
           pos = j; % 找到匹配位置
           break;  % 停止搜索
       end
   end

   % 获取当前符号在总区间中的范围 [p_low, p_high)
   % 注意：这里 newcpr 的索引对应区间下界，cpr 对应上界
   p_low = newcpr(pos);
   p_high = cpr(pos);

   % 计算当前区间的宽度
   range_width = current_high - current_low;

   % 更新区间：
   % 新的下界 = 当前下界 + (当前宽度 * 符号概率下界)
   % 新的上界 = 当前下界 + (当前宽度 * 符号概率上界)
   current_high = current_low + range_width * p_high;
   current_low  = current_low + range_width * p_low;
   
   % 为了防止精度溢出并观察中间过程，可以打印当前区间
   % fprintf(‘处理字符: %c, 新区间: [%.10f, %.10f)
‘, str(i), current_low, current_high);
end

% 最终输出：编码后的数值
% 理论上，区间 [current_low, current_high) 内的任意数都可以代表整个字符串
% 这里我们选择区间的中点作为最终的编码值
tag = (current_low + current_high) / 2;
fprintf(‘
编码完成！最终的编码数值为: %.10f
‘, tag);
fprintf(‘最终区间宽度: %.10f
‘, current_high - current_low);

深入理解代码逻辑

让我们停下来思考一下刚才发生了什么。在循环的每一次迭代中，我们都根据当前字符的概率，把之前的“大区间”变成了“小区间”。

你会发现，随着字符串变长，range_width 会急剧变小。这就解释了为什么算术编码需要高精度的浮点数。在实际的硬件实现中，我们通常使用定点数或整数运算来模拟这个过程，以避免浮点精度带来的误差。在 MATLAB 中，由于默认使用双精度浮点数，对于较短的文本我们通常不用担心这个问题，但如果你想压缩整本书，就需要更高级的实现技巧。

解码：逆序还原消息

既然我们已经把一串字符变成了一个数字 INLINECODEbf84d66d，现在让我们看看如何把这个数字还原回 "GeeksforGeeks"。解码的过程其实就是编码的逆操作：我们拿着 INLINECODEbfecacfe 这个数字，看它落在哪个字符的区间里，就把那个字符解出来，然后减去该区间的偏移量，再做归一化，重复直到所有字符处理完毕。

% --- 解码部分 ---

% 重置输入参数（模拟接收端只知道 tag 和长度）
% 注意：在实际传输中，我们还需要发送字符串的长度，否则解码端不知道何时停止
decoded_str = ‘‘; 
reconstructed_tag = tag;

% 重新构建相同的查找表（解码端必须拥有相同的模型）
% 实际应用中，概率表通常也包含在压缩数据的头部
for i = 1 : len
   % 遍历查找表，寻找 tag 落在哪个区间
   for j = 1 : len_unique
       % 检查 tag 是否在 interval(j) 定义的范围之内
       % 注意：tag 应该 >= interval(j,1) 且 = interval(j, 1)) && (reconstructed_tag < interval(j, 2))
           % 找到了对应的字符
           ch = u(j);
           decoded_str = [decoded_str ch]; % 拼接到结果字符串
           
           % 计算该字符区间在当前区间内的相对位置（去归一化）
           % 这是关键步骤：我们如何从当前的 tag 值中减去已知的区间偏移
           range_prev = interval(j, 2) - interval(j, 1);
           offset = reconstructed_tag - interval(j, 1);
           
           % 为下一次迭代更新 tag
           % 相当于把当前的子区间重新映射回 [0, 1) 进行下一轮匹配
           reconstructed_tag = offset / range_prev;
           
           break; % 找到后立即跳出内层循环
       end
   end
end

fprintf('
解码完成！还原的字符串是 : %s
', decoded_str);

% 验证结果
if strcmp(str, decoded_str)
    disp('验证成功：解码字符串与原始字符串完全一致。');
else
    disp('验证失败：请检查代码逻辑。');
end

性能优化与实战建议

通过上面的代码，你已经掌握了算术编码的核心逻辑。但在实际工程应用中，我们还需要考虑更多细节：

避免浮点数陷阱：我们在例子中使用了 double 类型，但在处理极长的序列或低概率符号时，区间宽度可能小于计算机的最小精度，导致区间变为 0。这就是为什么工业级的算术编码器（如 JPEG 2000 中的 MQ 编码器）通常使用整数运算和按位移位来代替乘除法。

自适应模型：目前的代码是基于静态概率的（即先扫描一遍字符串统计概率）。这意味着我们需要传输两遍数据（一遍统计，一遍编码）。更高效的方案是自适应算术编码，即在编码的过程中动态更新每个符号的概率。这样，编码器和解码器只需要一遍扫描即可同步。

算术编码 vs 赫夫曼编码：

* 赫夫曼：简单，快速，但必须为每个符号分配整数位长度。对于概率为 0.9 的符号，赫夫曼至少也要分配 1 位，这在理论上是浪费的（理想长度应约为 0.15 位）。

* 算术：复杂，计算量大，但能够突破“整数位”的限制，实现真正的分数比特编码。在符号概率分布极不均匀的情况下，算术编码通常能获得更好的压缩率。

总结

在这篇文章中，我们一起探索了算术编码这一精妙的技术。从最初的概念理解，到 MATLAB 代码的逐步实现，再到编码与解码的完整闭环，我们看到了如何利用数学区间将信息压缩到极致。

虽然我们编写的脚本主要用于教学目的，但它揭示了现代压缩软件背后的核心逻辑。你可以尝试修改代码，处理二进制文件，或者实现自适应模型，来进一步加深理解。希望这次探索能帮助你在数据处理的道路上更进一步。如果你有任何问题或想要分享你的实现成果，欢迎随时交流！

#### 关键要点回顾：

算术编码通过将消息映射到 $[0, 1)$ 区间的一个数值来实现压缩。
概率模型决定了区间的划分方式，符号概率越高，占据的区间越宽。
MATLAB 的向量化操作和逻辑索引非常适合构建此类算法原型。
解码是编码的逆过程，依赖于同步的概率模型和区间查找。

感谢阅读，祝你在编码与压缩的世界里玩得开心！

投稿给我们	如何建站？
vps是什么？	如何安装宝塔？
如何通过博客赚钱？	便宜wordpress托管方案
免费wordpress主题	这些都是免费方案

豆丁博客