简介算术编码的C语言实现详解文档面向学习数据压缩、信息论与编码技术的读者也适合需要完成课程设计或实验的计算机专业学生。文档从 source1.dat 中读取 100 个 0/1 数据按 0 出现概率 1/8、1 出现概率 7/8 的设定完整演示了初始化编码区间、逐步更新上下界、计算香农熵与最少编码位数、取区间中点转为二进制编码以及解码验证的全部流程。包内仅含 1 个 docx 文件大小约 109KB以程序代码和文字注释结合方式呈现资源已有 131 人浏览学习。读者可获得可直接运行的 C 语言算术编码程序框架其中针对熵值计算、边界更新和中点取码等关键环节均有明确说明并说明浮点精度可能带来的实现限制特别适合在概率分布不均匀场景中快速上手算术编码。文档步骤完整、注释清晰可作为数据压缩课程的项目参考资料。1. 算术编码用C语言实现到底在解决什么问题当数据里某个符号出现概率是 0.9、另一个是 0.1 时霍夫曼编码对低频符号最少也要分配 1 个 bit而算术编码把整段序列映射到一个不断收缩的小数区间上理论上可以让每个符号的平均位数低于 1 bit。这个特性正是算术编码能逼近信息论中熵极限的原因。用 C 语言实现它绕不开三件事区间精度、位操作、内存边界。很多从 Python 或 MATLAB 转过来的实现习惯直接用 double 累乘区间短序列看不出问题编码几百个符号后就开始解码错位。这篇文章提供的是适合 C 语言的定点数实现先讲清区间划分和重归一化的原理再给出编码器、解码器可运行的核心代码最后把 TOTAL_FREQ、EOF 标记、位缓冲这些容易写错的位置单独拿出来核对。适合正在做课程设计、嵌入式压缩模块或者想用 C 语言把熵编码工具链完整重写一遍的工程师阅读。2. 算术编码的区间划分与C语言数据结构设计2.1 区间划分原理为什么算术编码能逼近熵算术编码不是为单个字符编号而是始终维护一个概率区间[low, high)。编码开始时 low 0、high 1每读入一个符号就按照符号概率把当前区间切成若干子区间符号落在哪一段整个区间就收缩到哪一段。高频符号对应宽子区间被选中的概率大区间收缩得慢最终输出的位数少低频符号对应窄子区间区间快速收紧占用的位数多。全部符号处理完后从最终区间里取一个实数输出这个数的二进制小数长度近似等于-log2(区间宽度)也就是该序列的信息熵。霍夫曼编码只能分配合法整数位算术编码则天然支持“分数位”所以更贴近熵。实际代码里符号概率不用小数而是用整数频次生成累积频率表。设cum[i]表示前 i 个符号的累积频次符号 s 的子区间就是[cum[s], cum[s1])。对只有 A、B 两种符号、P(A)0.9 的二元序列霍夫曼每符号至少 1 bit算术编码期望平均只需约 0.47 bit。用整数频率表而非浮点概率是为了让编码器和解码器在完全相同的整数除法规则下得到一致区间浮点四舍五入在两端稍有差别就会导致整个流解不出来。2.2 浮点 double 的两个坑与定点化思路直接拿 double 做区间乘法会遇到两个明显问题一是每一步乘法都有尾数误差长序列下误差累积会让区间越偏越多二是 double 只有 53 位尾数窗口缩到机器精度以下后就无法继续用乘法收缩区间。所以正式的 C 实现要走“定点化 重归一化”路线用一个 uint32_t 宽度的窗口表示当前区间窗口覆盖的值域固定每编码一个符号后观察 low 和 high 的高位状态若高位已经确定就输出再把窗口左移扩展。这个逻辑在 C 语言里只需要移位和按位比较不需要引入任何浮点库也避免不同平台浮点实现差异带来的兼容问题。重归一化处理三种典型状态high 的最高位为 0 时当前区间整体落在 0.x 范围输出 0low 的最高位为 1 时整体落在 0.1xx 范围输出 1区间跨在 0.01xx 到 0.10xx 之间时高位暂时不确定需要把输出位挂起等待后续确定挂起的位数用 pending 计数跟踪。这个 pending 机制是算术编码 C 实现里最容易出错的点后面第 3 章的代码会体现它。2.3 编码器与解码器共用同一张频率表算术编码能正确解码的前提是编码端和解码端使用的概率模型完全一致。常见做法是只在编码前调用一次模型初始化函数解码器直接复用同一张累积频率表而不是拿到数据后重新统计。如果解码端自行统计频率符号顺序和累积边界稍有不同解出来的就是乱码。另外一个容易忽略的点是要把文件结束标志也当成一个符号加入频率表。EOF 符号参与区间划分后解码器读到 EOF 就可以终止循环不需要依赖文件长度来判断结束。由于 EOF 参与建模累积表的维度要比普通 256 字节多两格cum[256]是前 256 个符号的累积上界cum[257]是包含 EOF 的总频次。这样编码 EOF 时也能用同一个区间切分公式计算不用为结束符单独写一堆 if 分支。2.4 C语言数据结构的最小定义与模型初始化下面这份结构体定义可以直接作为实现基础。涉及三个核心对象概率模型、位流、编码器和解码器状态。#include stdio.h #include stdint.h #include string.h #define CODE_BITS 32u #define HALF (1u (CODE_BITS - 1)) #define FIRST_QTR (1u (CODE_BITS - 2)) #define THIRD_QTR (3u (CODE_BITS - 2)) #define EOF_SYMBOL 256 typedef struct { uint32_t cum[258]; uint32_t total; } freq_model; typedef struct { FILE *fp; unsigned char byte; int bit_cnt; } bit_stream; typedef struct { bit_stream *bs; uint32_t low, high, pending; } encoder; typedef struct { bit_stream bs; uint32_t low, high; } decoder;cum[258]这里多出来的两个下标是关键cum[256]保存普通字节符号的累计上界cum[257]保存加入 EOF 后的总频次EOF 符号的区间就是[cum[256], cum[257])。bit_stream负责把 bit 打包成字节byte累积 8 位后写入文件bit_cnt记录当前字节已经使用了多少位。编码器里的pending用来暂存跨中点的待定输出位解码器不需要 pending因为待定位已经体现在输入码值里。模型初始化代码如下从未出现的字节也分配一个最小频次 1避免符号概率为零时出现区间不收缩或除零问题。void model_init(freq_model *m, const unsigned char *data, size_t len) { uint32_t freq[257]; memset(freq, 0, sizeof(freq)); for (size_t i 0; i len; i) { freq[data[i]]; } freq[EOF_SYMBOL]; m-cum[0] 0; for (int i 0; i EOF_SYMBOL; i) { m-cum[i 1] m-cum[i] (freq[i] ? freq[i] : 1); } m-total m-cum[EOF_SYMBOL 1]; }cum[0]0是区间起点循环从 0 到 256逐个把符号频次累加进累积表。freq[i] ? freq[i] : 1保证所有 257 个符号都有最小概率空间这样编码范围永远被完整覆盖。如果输入文件很大频次累加可能溢出 uint32_t这个限制到第 4 章会专门讨论。3. 算术编码C语言最小实现位流、编码器、解码器与主函数3.1 位流操作把 bit 写进文件和从文件读出来算术编码输出的是一串 bit不能直接按字节写否则文件体积会被放大 8 倍。这块代码把 bit 按 MSB first 的顺序打包成字节。编码端用bs_put_bit解码端用bs_get_bit两端必须保持一致否则所有位都错位。void bit_stream_init(bit_stream *bs, FILE *fp) { bs-fp fp; bs-byte 0; bs-bit_cnt 0; } void bs_put_bit(bit_stream *bs, int bit) { bs-byte (unsigned char)((bs-byte 1) | (bit 1)); bs-bit_cnt; if (bs-bit_cnt 8) { fputc(bs-byte, bs-fp); bs-byte 0; bs-bit_cnt 0; } } void bs_flush(bit_stream *bs) { while (bs-bit_cnt 0) { bs_put_bit(bs, 0); } } int bs_get_bit(bit_stream *bs) { if (bs-bit_cnt 0) { bs-byte (unsigned char)fgetc(bs-fp); bs-bit_cnt 8; } bs-bit_cnt--; return (bs-byte bs-bit_cnt) 1; }bs_put_bit先把当前字节左移一位再放入新 bit当bit_cnt到 8 时把整个字节写入文件并清零。bs_flush用 0 补齐最后一个字节这部分填充位在解码端会被当作正常输入读取但不会影响符号判断因为 EOF 符号会先被解出来。bs_get_bit从缓冲字节的最高位开始取取到空字节时再读下一个文件字节。注意文件要以二进制模式打开避免 Windows 下换行符转换造成字节错乱。3.2 encode_symbol 与重归一化的C实现编码器的核心函数不长但三个分支的顺序不能调换调换后区间状态会不一致。range用 uint64_t 承接乘法结果避免 32 位乘法溢出。void encoder_init(encoder *e, bit_stream *bs) { e-bs bs; e-low 0; e-high 0xFFFFFFFFu; e-pending 0; } static void output_bit(encoder *e, int bit) { bs_put_bit(e-bs, bit); while (e-pending 0) { bs_put_bit(e-bs, bit ^ 1); e-pending--; } } void encode_symbol(encoder *e, uint32_t cum_lo, uint32_t cum_hi, uint32_t total) { uint64_t range (uint64_t)e-high - e-low 1; e-high (uint32_t)(e-low (range * cum_hi) / total - 1); e-low (uint32_t)(e-low (range * cum_lo) / total); for (;;) { if (e-high HALF) { output_bit(e, 0); } else if (e-low HALF) { output_bit(e, 1); e-low - HALF; e-high - HALF; } else if (e-low FIRST_QTR e-high THIRD_QTR) { e-pending; e-low - FIRST_QTR; e-high - FIRST_QTR; } else { break; } e-low 1; e-high 1; e-high | 1; } } void encoder_flush(encoder *e) { e-pending; output_bit(e, e-low FIRST_QTR ? 0 : 1); }high low (range * cum_hi) / total - 1计算的是当前符号子区间的上界low low (range * cum_lo) / total计算下界。区间更新后进入重归一化循环high HALF表示整个区间都在 0 到 0.5 之间最高位确定为 0low HALF表示区间在 0.5 到 1 之间输出 1 后把窗口整体减去 HALF第三种情况是最难理解的 E3 处理区间已经落到四分之一到四分之三之间但还没有完全确定同侧这时不能直接输出只能增加 pending 计数等下一轮看它偏向 0 还是 1再在 output_bit 里补发取反的位。encoder_flush在最后一个符号编码完成后调用把剩余无法通过重归一化输出的位强制清理出去。这里的 pending1 和low FIRST_QTR判断是经典实现的标准做法保证解码端能读到足够的位来完成最后一次区间对齐。3.3 decode_symbol 与回读同步解码器初始化时要预先读入 CODE_BITS 位作为当前的码值窗口。这是因为算术编码输出的是一个二进制小数解码端必须先拿到足够多的位才能判断第一个符号落在哪个子区间。void decoder_init(decoder *d, FILE *fp, uint32_t *code) { bit_stream_init(d-bs, fp); d-low 0; d-high 0xFFFFFFFFu; *code 0; for (int i 0; i (int)CODE_BITS; i) { *code (*code 1) | bs_get_bit(d-bs); } } int decode_symbol(decoder *d, freq_model *m, uint32_t *code) { uint64_t range (uint64_t)d-high - d-low 1; uint32_t value (uint32_t)((((uint64_t)(*code - d-low) 1) * m-total - 1) / range); int s 0; while (s EOF_SYMBOL m-cum[s 1] value) { s; } uint32_t cum_lo m-cum[s]; uint32_t cum_hi m-cum[s 1]; d-high (uint32_t)(d-low (range * cum_hi) / m-total - 1); d-low (uint32_t)(d-low (range * cum_lo) / m-total); for (;;) { if (d-high HALF) { /* 高位同为0不需要调整 */ } else if (d-low HALF) { d-low - HALF; d-high - HALF; *code - HALF; } else if (d-low FIRST_QTR d-high THIRD_QTR) { d-low - FIRST_QTR; d-high - FIRST_QTR; *code - FIRST_QTR; } else { break; } d-low 1; d-high 1; d-high | 1; *code (*code 1) | bs_get_bit(d-bs); } return s; }value的计算把当前码值投影到 0 到 total 的概率空间里随后在累积表中查找它所属的符号段。查找完成后解码器执行与编码器完全相同的区间收缩和重归一化唯一的区别是每轮左移后要从输入码值的最低位补入一位新 bit用输入位流替代编码端的待定位输出。这样经过多次收缩后码值窗口始终和编码时的区间保持同步这是算术编码能无损还原的根本原因。3.4 一个往返主函数先编码字符串再解码恢复下面这个 main 函数把前面所有代码串起来先编码固定字符串到arith.bin再打开文件解码并打印到标准输出。字符串长度要控制在 255 字节以内因为示例里的data缓冲区大小是 256。int main(void) { const char *text arithmetic coding in C; size_t len strlen(text); unsigned char data[256]; memcpy(data, text, len); freq_model model; model_init(model, data, len); FILE *fp fopen(arith.bin, wb); bit_stream bs; bit_stream_init(bs, fp); encoder enc; encoder_init(enc, bs); for (size_t i 0; i len; i) { encode_symbol(enc, model.cum[data[i]], model.cum[data[i] 1], model.total); } encode_symbol(enc, model.cum[EOF_SYMBOL], model.cum[EOF_SYMBOL 1], model.total); encoder_flush(enc); bs_flush(bs); fclose(fp); fp fopen(arith.bin, rb); decoder dec; uint32_t code; decoder_init(dec, fp, code); for (;;) { int s decode_symbol(dec, model, code); if (s EOF_SYMBOL) { break; } fputc(s, stdout); } fputc(\n, stdout); fclose(fp); return 0; }编码时对每个字节符号传入cum[data[i]]和cum[data[i] 1]对应符号区间上下界EOF 符号传入cum[256]和cum[257]。如果文件末尾忘记编码 EOF解码器会一直等码值更新最终读到无意义的符号。解码循环以返回 EOF_SYMBOL 为终止条件不依赖文件的物理大小这也是把 EOF 纳入频率模型的最大好处解码端只需要负责维护好区间结束条件由模型自己判断。4. 算术编码关键参数与边界处理从能跑到能压4.1 影响正确性和压缩率的四个参数实现算数编码时有四个参数直接决定程序能不能跑通、压缩效果好不好。下面这张表可以作为设置基准参数作用建议取值注意事项CODE_BITS重归一化窗口位宽32range 乘法用 uint64_t窗口再宽需要换 __uint128累积频率 total概率划分精度小于 2^24total 太大会导致 range*total 接近 uint64 上限EOF_SYMBOL流结束标记256必须计入模型解码端才能判断终止位序约定编码解码同步MSB first编码器和解码器必须一致否则逐位错开CODE_BITS 越大单次能表达的区间精度越高长序列下压缩率更接近熵但每次重归一化前 low 和 high 的差不能超过 2^CODE_BITS所以乘法需要一个更宽的整数类型承接。对普通数据压到 2^32 窗口加 uint64_t 中间量已经是很多成熟实现的标配。若把 CODE_BITS 改成 40 或 48就必须用unsigned __int128或者拆成多次乘法代码复杂度会明显上升。total 的建议值是 2^24是因为每次区间更新都要计算range * cum_hi / total其中 range 最大为 2^32若 total 为 2^24乘积最大 2^56距离 uint64_t 上界 2^64 还有充足余量。实际使用时若输入文件很长所有符号频次加起来会超过这个值必须在 model_init 里做一次按比例缩放把 total 归一化到 2^24 附近同时保证每个符号的频次至少为 1。4.2 EOF、刷新位和文件尾的边界处理EOF 符号必须像普通符号一样参与区间划分否则解码循环无法判断何时停止。具体做法是在频率表里给 EOF 分配一个独立频次编码完所有数据后立刻编码一次 EOF。encoder_flush和bs_flush的调用顺序不能颠倒必须先把编码器内部挂起的 pending 位全部输出再补齐最后一个字节的剩余位。如果先bs_flush后补的编码位会排到已经填充的字节之后解码端读到的位序整体错乱。另一个常见边界问题是解码端读取的最后一个字节可能只有几位有效数据bs_get_bit用 fgetc 读到文件末尾时会返回 EOF此时把 EOF 的字节值 0xFF 当作 8 个 1 使用解码器可能多解出几个符号。这类问题比较隐蔽通常表现为解码结果比原数据多几个字符。解决办法是把编码器输出的文件大小一并记录下来或者用独立的容器格式保存符号个数。如果只想保持简单让 EOF 符号作终止符是够用的但测试要覆盖到不同对齐长度的数据。4.3 与霍夫曼编码的实测对比算术编码的优势体现在符号概率分布明显偏斜的场景。下表是三种典型场景的理论对比实际程序会因为频率表归一化和填充位多出少量开销。场景Huffman 平均码长算术编码平均码长差距原因8 个等概率符号3 bit约 3 bit整数码长已经逼近熵0.9/0.1 二元序列1 bit约 0.47 bitHuffman 无法给高频符号分配 0 位30 个非均匀符号受树结构约束可逼近实测熵码树的整数位限制了最优性如果数据分布接近均匀Huffman 和算术编码差距很小而 Huffman 实现简单、速度更快这类场景里没必要用算术编码。但在大量自然文本、日志、传感器数据中符号分布通常偏斜明显算术编码的压缩收益可以高出 5% 到 15%。C语言实现算术编码的代价是要处理位级读写和频率表归一化工程上会更复杂但内存占用仍然可控只有几个结构体和两个缓冲区。4.4 常见误用与排查最容易犯的错误是直接用e-high - e-low 1不转型到 uint64_t 就参与乘法。low 初始为 0high 初始为 0xFFFFFFFFhigh - low 1在 32 位无符号数里直接溢出为 0导致后面所有区间更新都失效。一定要写成(uint64_t)e-high - e-low 1让减法在 64 位环境中计算。第二个高发错误是解码端重新统计频率。如果把 model_init 放在解码函数里调用而输入数据和编码端不完全一致累积表的下标对应关系就会漂移。正确做法是编码前构建一次模型编码和解码都持同一个模型的指针或者把模型的初始化数据先写入压缩文件头部解码端读取后重建完全相同的频率表。第三个问题是符号概率为零。如果某个符号从未出现且没有给它分配最小频次range * cum_hi和range * cum_lo可能计算出完全相同的值导致 low 和 high 不再收缩重归一化陷入死循环。前面 model_init 里的freq[i] ? freq[i] : 1就是为了堵住这个漏洞。最后要注意位流的读写顺序编码端用 MSB first 写入解码端也必须是 MSB first 读取哪怕是一处 bit_cnt和 (8 - bit_cnt)写反都会让所有符号错位。5. 算术编码C实现的验证方法与调试技巧5.1 用随机数据做往返一致性测试把 main 函数改造为从文件读入、再写回文件后可以用下面的命令批量验证编码器和解码器重点检查不同长度、不同分布的数据能否全部无损还原for i in $(seq 1 200); do head -c $((RANDOM % 500 1)) /dev/urandom /tmp/test.bin ./arith /tmp/test.bin out.bin cmp -s /tmp/test.bin out.bin || echo case $i failed done echo round-trip check finished往返测试不只是为了证明“能解出来”更重要的是覆盖长度不是 8 的倍数、符号分布极不均匀、文件首尾字符相同这些边界情况。只要有一处 cmp 失败就用二分法缩小测试输入找到触发问题的具体数据。随机数据测试通过后再换真实文本测试因为文本的符号分布集中在 ASCII 码区间能验证频率表下标的边界。5.2 打印 low/high 窗口定位偏差点算术编码的排错思路和霍夫曼很不一样输出流里没有符号边界无法直接定位第几个符号出错唯一可靠的手段是观察 low、high 和 value 三个值的变化。在 decode_symbol 的重归一化循环里插入一行调试代码能快速判断区间是否在某一轮完全错开printf(round%lu low%08X high%08X code%08X value%u\n, round, d-low, d-high, *code, value);如果前几个符号一致、到某个符号开始 low 和 high 与手推结果不匹配就去检查编码器对应轮次的 pending 和输出位。最常见的现象是编码端输出了正确的高位但解码端因为 bit_order 约定不同读进来的 value 整体右移了一位导致所有符号向后错位。打印 code 值能直接看出输入位流是否和编码输出一致。5.3 把调试打印做成条件编译开关逐轮打印非常干扰性能测试只应该在排错时打开。用宏包一层正常编译时完全无开销需要调试时加一个宏即可#ifdef ARITH_DEBUG #define DEBUG_LOG(...) printf(__VA_ARGS__) #else #define DEBUG_LOG(...) do {} while (0) #endif编译命令是gcc -DARITH_DEBUG -o arith arith.c不写宏则直接编译。这样做的好处是测试随机数据时不用反复删除打印语句避免改代码时意外引入语法错误。所有打印集中在重归一化和符号查找两个位置因为其他地方的变量基本一眼就能看出对错。5.4 一个最容易藏 bug 的细节flush 顺序跑通 200 组随机测试也不代表所有边界都对倒数第二个字节的对齐就是典型盲区。编码器最后输出时encoder_flush会把 pending 位补到一个字节里随后bs_flush又用零填充到整字节。如果两个 flush 顺序反过来解码端读到的是编码器最终区间的低半部分而不是已经确定的输出位。调试时打印bit_stream.bit_cnt的变化正确流程是 pending 位全部清空后 bit_cnt 严格落在 0 到 7 之间再补零到 0。只要这里对齐无误整条算术编码的编码端和解码端就被完全同步了。本文还有配套的精品资源点击获取