C++实现算术编码（从零开始掌握C++算术编码算法与无损压缩原理）

图：算术编码通过不断缩小区间来表示符号序列

准备工作：理解概率模型

在实现前，我们需要一个简单的概率模型。假设我们要压缩字符串 "ABAC"，其中：

• A 出现概率 = 0.5
• B 出现概率 = 0.25
• C 出现概率 = 0.25

我们将使用这些概率来划分区间。

C++实现步骤详解

1. 定义符号概率表

#include <iostream>#include <map>#include <string>#include <vector>#include <iomanip>// 符号到累积概率的映射（左边界）std::map<char, double> buildCumulativeProb(const std::map<char, double>& prob) {    std::map<char, double> cumProb;    double sum = 0.0;    for (const auto& p : prob) {        cumProb[p.first] = sum;        sum += p.second;    }    return cumProb;}

2. 编码函数实现

double arithmeticEncode(const std::string& message,                       const std::map<char, double>& prob,                       const std::map<char, double>& cumProb) {    double low = 0.0;    double high = 1.0;    for (char c : message) {        if (prob.find(c) == prob.end()) {            std::cerr << "Unknown symbol: " << c << std::endl;            return -1;        }        double range = high - low;        double symbolLow = cumProb.at(c);        double symbolHigh = symbolLow + prob.at(c);        high = low + range * symbolHigh;        low = low + range * symbolLow;        std::cout << "Symbol '" << c << "': ["                   << std::setprecision(6) << low                   << ", " << high << ")\n";    }    // 返回区间中点作为编码结果    return (low + high) / 2.0;}

3. 解码函数（可选，用于验证）

std::string arithmeticDecode(double encodedValue,                            int length,                            const std::map<char, double>& prob,                            const std::map<char, double>& cumProb) {    std::string result;    double value = encodedValue;    for (int i = 0; i < length; ++i) {        for (const auto& p : prob) {            char symbol = p.first;            double lowBound = cumProb.at(symbol);            double highBound = lowBound + p.second;            if (value >= lowBound && value < highBound) {                result += symbol;                // 将值归一化到当前符号区间内                value = (value - lowBound) / p.second;                break;            }        }    }    return result;}

4. 主函数测试

int main() {    // 定义符号概率    std::map<char, double> prob = {{'A', 0.5}, {'B', 0.25}, {'C', 0.25}};    auto cumProb = buildCumulativeProb(prob);    std::string message = "ABAC";    std::cout << "Original message: " << message << "\n\n";    // 编码    double encoded = arithmeticEncode(message, prob, cumProb);    std::cout << "\nEncoded value: " << std::setprecision(10) << encoded << "\n\n";    // 解码    std::string decoded = arithmeticDecode(encoded, message.length(), prob, cumProb);    std::cout << "Decoded message: " << decoded << "\n";    if (message == decoded) {        std::cout << "✅ Success! Compression and decompression work correctly.\n";    } else {        std::cout << "❌ Error! Decoded message does not match original.\n";    }    return 0;}

运行结果示例

程序输出如下：

Original message: ABACSymbol 'A': [0, 0.5)Symbol 'B': [0.25, 0.375)Symbol 'A': [0.25, 0.3125)Symbol 'C': [0.296875, 0.3125)Encoded value: 0.3046875Decoded message: ABAC✅ Success! Compression and decompression work correctly.

注意事项与优化方向

• 精度问题：实际应用中不能使用 double，因为长消息会导致精度溢出。工业级实现通常使用整数运算和位操作（如基于 32 位寄存器的自适应缩放）。
• 动态概率模型：本例使用静态概率。真实场景中常用自适应模型（如 PPM 或上下文建模）。
• 结束符处理：需添加特殊结束符（如 EOF）或提前告知消息长度。

总结

通过本教程，你已经掌握了如何用 C++算术编码 实现基础的 无损压缩算法。虽然这是一个简化版本，但它完整展示了 算术编码算法 的核心逻辑。理解这一过程，为你深入学习 C++数据压缩 技术打下了坚实基础。

下一步建议：尝试将浮点运算改为整数运算，或集成到文件压缩工具中！