C++ 算術編碼實現詳解：原理、區間更新與完整代碼實戰

算術編碼核心原理

將整個訊息序列編碼為 [0, 1) 區間內單一浮點數。核心參數：

• 符號機率： 決定壓縮效率與初始區間劃分。
• 編碼區間： 當前區間 [Low, High)，隨符號處理持續縮小。

區間更新演算法

設 d = High - Low 為當前區間長度。第 i+1 個符號區間更新：

high = Low + d * 符號上限;
low  = Low + d * 符號下限;
High = high;
Low  = low;
d   *= 符號機率;

最終輸出 [Low, High) 區間內任一數值的二進位表示即為壓縮碼流。

完整 VC6.0 可編譯實現

#include <iostream>
#include <iomanip>
#define M 100  // 最大編碼長度
#define N 4    // 符號種類數

class ArithmeticCoder {
    int count, length;
    char symbol[N];
    long double prob[N];
    char code[M];
    long double High, Low, high, low, d;

public:
    ArithmeticCoder() : High(1.0), Low(0.0), d(1.0) {}

    void inputSymbols() {
        std::cout << "Input symbol and probability (e.g. a 0.5):\n";
        for (int i = 0; i < N; ++i) {
            std::cin >> symbol[i] >> prob[i];
        }
        count = N;
    }

    void inputCode() {
        std::cout << "Input code sequence: ";
        std::cin >> code;
        length = strlen(code);
    }

    void encode() {
        // 建立初始區間邊界
        long double cum = 0.0;
        long double upper[N], lower[N];
        for (int i = 0; i < count; ++i) {
            lower[i] = cum;
            cum += prob[i];
            upper[i] = cum;
        }

        // 逐符號編碼
        for (int k = 0; k < length; ++k) {
            int idx = -1;
            for (int i = 0; i < count; ++i)
                if (code[k] == symbol[i]) { idx = i; break; }
            if (idx == -1) { std::cerr << "Unknown symbol: " << code[k] << std::endl; return; }

            high = Low + d * upper[idx];
            low  = Low + d * lower[idx];
            High = high;
            Low  = low;
            d   *= prob[idx];

            std::cout << "Step " << k+1 << ": [" 
                      << std::setprecision(20) << Low << ", " << High << ")\n";
        }
        std::cout << "Final interval: [" << Low << ", " << High << ")\n";
        std::cout << "Compressed value (mid): " << (Low + High) / 2 << std::endl;
    }
};

int main() {
    ArithmeticCoder ac;
    ac.inputSymbols();
    ac.inputCode();
    ac.encode();
    return 0;
}

工程化關鍵點

現代 C++ 改良建議

• 使用 std::vector, std::map 替代固定陣列。
• 採用 uint64_t 整數算術編碼 (參考 range-v3 或 FastAC 實現)。
• 模板化支援任意符號型別。
• 加入單元測試驗證編解碼往返一致性。

1. 上一篇文章： C++ 監控 Windows 事件日誌實戰：.NET 互操作與即時通知機制
2. 下一篇文章： C++ 動態記憶體傳遞核心難題：指標、引用與 RAII 的正確姿勢

C++ 入門

二叉樹非遞歸遍歷完全指南：前序、中序、後序三種實現 (京東 2015 筆試真題)

背景 京東 2015 校招筆試編程題：二叉樹前序遍歷非遞歸實

C++ 虛函數表深度解析（三）：多重繼承內存佈局、虛表打印與覆蓋規則

系列回顧 第一篇：靜態/動態綁定、虛函數表指針 vptr

HDU Toy Storage：幾何分割與玩具計數問題解析

問題背景 Reza 的父母為了整理兒子亂丟的玩具，在長方形盒

C++ D&A 5 實戰：基於虛繼承的 Collection 框架實現詳解

項目背景 實現一個基於繼承體系的容器框架，核心類包括抽象基類