算术编码
（个人感觉dip大概率要考）
「算术编码」是一种变长编码，从整个符号序列出发进行编码，不是对单个符号进行编码，没有源符号与码字的一一对应关系，需要每个符号出现的概率和整个符号的排列顺序
编码过程按照符号序列顺序递推进行，随符号序列中符号数量增加
- 用来代表它的区间变小
- 用来表达区间所需的信息单位的数量变大
算术编码是对符号串整体的编码，理论上可达到无失真编码定理给出的编码极限
过程
- 编码器在开始时将「当前间隔」
- 对每个事件，编码器按照下面两个步骤进行处理
- 编码器将“当前间隔”分为子间隔，每一个事件一个
- 一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下 一个确切发生的事件相对应，并使它成为新的 “当前间隔”
- 最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码
例题
假设信源符号为
| 符号 | ||||
|---|---|---|---|---|
| 概率 | 0.1 | 0.4 | 0.2 | 0.3 |
若消息序列的输入为 cadacdb，则进行算术编码的过程如下
取一个 1000001。此时这段码就表示了原始序列 cadacdb
实际在计算的过程中，其实不太好确定选取区间内的具体哪一个数字，即使确定小数后，也不确定在转换为二进制小数的过程中该保留几位小数。此时可以将上界和下界一起进行十进制到二进制转换，然后看看在多少位时，二者出现不同时，保留一个处于上界和下界之间的二进制小数即可。