算术编码实验

一、实验目的

理解算术编码的原理，掌握区间划分与概率累加方法。
实现算术编码的编码与解码过程，并生成最短二进制码字。
验证编码的正确性，确保解码后能完全恢复原字符串

二、实验环境

编程语言：Python
关键库：decimal（高精度十进制运算）
输入参数：
- 字符集：['W', 'X', 'Y', 'Z']
- 概率分布：[0.2, 0.3, 0.1, 0.4]
- 待编码字符串：'YWXZWYX'

三、实验原理

算术编码将整个输入序列映射为实数区间 $[0, 1)$ 中的一个子区间，并用该区间内的一个二进制小数表示。其核心是区间递归划分

初始区间： $[0, 1)$ 。
根据符号概率，将当前区间按符号的概率比例划分为子区间。
读入一个符号，将当前区间更新为该符号对应的子区间。
重复直到所有符号处理完毕。
输出编码：从最终区间内选择一个二进制小数，使得该小数能够唯一标识该区间，且位数尽可能少。
解码时，根据二进制码字还原出小数，再根据相同的概率模型逐步确定符号。

四、关键函数

4.1 区间构建函数 `build_intervals`

将给定的频率列表转换为归一化概率，并计算每个符号对应的 $[low, high)$ 区间。例如：

W: [0.0, 0.2)
X: [0.2, 0.5)
Y: [0.5, 0.6)
Z: [0.6, 1.0)

4.2 编码函数 `arithmetic_encode`

使用 decimal.Decimal 保证高精度，避免浮点误差。
初始化 low = 0，high = 1。
对输入字符串的每个字符，计算当前区间宽度 range_width = high - low，然后更新：
- high = low + range_width * high_symbol
- low = low + range_width * low_symbol
最后调用 value_to_bits(low, high) 生成二进制码字。

4.3 最短二进制码字生成 `value_to_bits`

这是生成最短二进制编码的关键。函数通过逐位试探的方式，构造一个二进制小数 $0.b_1b_2...$ ，使其落入区间 $[low, high)$ ：

初始化 value = 0，当前位数 bits = []。
每次循环，尝试在末尾添加 1（即加上 $2^{-k}$ ），得到 test_value。
根据 test_value 与区间的关系决定当前位：
- 若 test_value < low：必须加 1，否则永远无法进入区间。
- 若 test_value >= high：不能加 1，只能加 0。
- 若 test_value 落在区间内，则优先尝试加 0（若当前 value 已在区间内，则直接返回，得到最短码字）；否则加 1 并返回。
该策略保证了返回的二进制串是能唯一确定区间的最短表示（即不存在更短的二进制串也落在同一区间内）

4.4 解码函数 `arithmetic_decode`

将二进制码字转换为十进制小数 encoded_value。
初始化区间 [low, high) = [0, 1)。
对每个待解码的符号（已知长度），计算当前区间宽度，依次检查每个字符的子区间 [char_low, char_high)，若 encoded_value 落在其中，则输出该字符，并更新 low, high 为该子区间，同时将 encoded_value 映射到新的相对位置

五、实验数据与计算过程

5.1 符号区间（归一化后）

符号	概率	左边界	右边界
W	0.2	0.0	0.2
X	0.3	0.2	0.5
Y	0.1	0.5	0.6
Z	0.4	0.6	1.0

5.2 编码过程

初始区间 $[0, 1)$ ，处理字符串 YWXZWYX：

步骤	符号	区间 [low, high)	区间长度
1	Y	[0.5, 0.6)	0.1
2	W	[0.5, 0.52)	0.02
3	X	[0.504, 0.51)	0.006
4	Z	[0.5076, 0.51)	0.0024
5	W	[0.5076, 0.50808)	0.00048
6	Y	[0.50784, 0.507888)	0.000048
7	X	[0.5078496, 0.507864)	0.0000144
最终区间 $[0.5078496, 0.507864)$ ，区间长度 $1.44 \times 10^{-5}$ 。

5.3 最短二进制码字生成（`value_to_bits` 模拟）

使用 value_to_bits 算法，逐位构造：

初始 value = 0，bits = []
第1位：test_value = 0.5，与区间比较：test_value = 0.5 小于 low？low=0.5078496，0.5 < low，故必须加1 → bits=['1']，value=0.5
第2位：test_value = 0.5 + 0.25 = 0.75，0.75 >= high → 加0 → bits=['1','0']，value 不变。
继续直到满足条件。最终生成 bits='1000001000000011'，其对应的数值为 $0.5078582763671875$ $0.5078582763671875$ ，恰好落在区间内，且没有更短的二进制串能落在该区间
- 验证：去掉最后一位 '100000100000001' 对应的数值为 $0.5078582763671875 - 2^{-16} = 0.5078582763671875 - 0.0000152587890625 = 0.507843017578125$ ，小于 low，故不能去掉最后一位。

六、实验结果

6.1 编码输出

运行源码后输出：

bits= 1000001000000011
Decoded string: YWXZWYX
Original string: YWXZWYX
Match: True

比特流：1000001000000011
长度：16 bits

6.2 解码验证

将 1000001000000011 转换为十进制小数 $0.5078582763671875$ ，根据上述解码步骤，依次输出字符：

落在 Y 区间 → Y
更新区间后，判断新的子区间，得到 W → W
继续得到 X、Z、W、Y、X
最终解码结果为 YWXZWYX，与原始字符串完全一致。

6.3 压缩效果分析

原始字符串长度 7 字符，若采用 ASCII 编码（8 bits/字符），共 56 bits。
算术编码输出 16 bits，压缩比约为 3.5:1。
信息熵： $H = -\sum p_i \log_2 p_i \approx 1.846$ bits/symbol，理论最小长度为 $7 \times 1.846 \approx 12.92$ bits。实际 16 bits 略高于熵极限，这是由于有限长序列及二进制截断的微小冗余，但仍在合理范围内。

七、结论

正确性验证：通过手工区间计算与源码解码结果的对比，证明 1000001000000011 能够唯一且正确地解码回原字符串，算法实现正确。
最短性验证：value_to_bits 函数生成的二进制串是落在最终区间内的最短二进制表示，满足题目要求。
算法特点：使用 decimal.Decimal 避免了浮点精度问题，保证了编解码的一致性；逐位试探生成最短码字的策略是算术编码中常用的高效方法。

八、源码核心片段

def value_to_bits(low, high):
    value = Decimal(0)
    bits = []
    scale = Decimal(1)
    for _ in range(1000):  # 足够大的循环
        scale /= 2
        test_value = value + scale
        if test_value < low:
            value = test_value
            bits.append('1')
            continue
        if test_value >= high:
            bits.append('0')
            continue
        # test_value 在区间内，优先尝试加0
        if value >= low and value < high:
            bits.append('0')
            return ''.join(bits)
        # 否则加1
        value = test_value
        bits.append('1')
        return ''.join(bits)
    return ''.join(bits)  # 理论不会执行到这里

九、实验总结

本次实验完整实现了算术编码的编解码过程，并成功对字符串 YWXZWYX 进行了压缩与恢复。通过分析，验证了算术编码能够有效利用符号概率分布，获得接近熵极限的压缩效果。实验过程中，高精度运算保证了编解码的准确性，为后续更复杂的数据压缩应用打下了基础。