算术编码实验报告

计63 陈晟祺 2016010981

编译

本程序使用 libgmp 进行高精度运算，编译前请确认已经安装 libgmp-dev。

可使用 CMake 编译：

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release .. && make

或者直接编译：

g++ -O3 main.cpp -lgmp -o arithmetic_coding

如果在 CMake 中指定编译类型为 Debug 或者向 g++ 传递 -DDEBUG 参数，则运行过程中会打印调试信息（包括编码区间结果、压缩率、信息熵、理想编码长度等）。这可能会影响程序的运行速度。

运行

./arithmetic_coding enc/dec INPUT OUTPUT

enc/dec 指定编解码模式，INPUT 和 OUTPUT 为输入/输出文件名，如果为 - 则使用标准输入输出。编解码均以行为单位进行。

原理

所有的数值计算均使用 GMP 提供的高精度有理数运算库，因此本程序不受浮点数精度的限制，支持对任意长的01串进行编码和解码。事实上，不使用高精度库也可实现此功能。因为区间足够小时其较高位不会变化，所以可以直接输出后扩大区间。因此，可以直接使用定点数来代替浮点运算。

编码

在编码时，首先读入01字符串，并统计其中 0 的频数，计算频率 Qe。此后使用课件中的自适应算术编码算法（在此略去）寻找编码区间 [A, B)。

在得到区间后，需要找到区间中二进制长度最短的数作为原串的编码。很容易知道，分母为 2 的幂的第一个不小于 A 的分数符合这一要求。因此从 1 开始不断倍增分母进行尝试即可。

在输出编码串前，首先需要输出原串长度和 0 的频数，以便解码使用。

解码

在解码时，读入原串长度、0 的频数和编码后的串，构建出编码值。根据课件中的解码算法，逆向进行编码过程即可恢复原串。

总结

算术编码是一种数学上比较优越的信息编码方式，能够较好地逼近信息的压缩极限；并且对内存的要求较少。但是与其他编码（如 Huffman）相比，它的编解码速度较慢，并且不支持部分解码，只能从头开始。因此，它比较适合对图像等高冗余顺序信息进行编码压缩，实测也能取得较好的效果。