linux上用c实现算术编码（三）--算术编码理论讲解

1、算术编码定义

它是1种非分组编码算法。它是从全序列动身，采取递推情势的连续编码。它不是将单个的信源符号映照成1个码字，而是将全部输入序列的符号根据它们的几率映照为实数轴上区间[0 1)内的1个小区间，再在该小区间内选择1个代表性的2进制小数，作为实际的编码输出。

算术编码不同于霍夫曼码，它是非分组（非块）码。它从全序列动身，斟酌符号之间的关系来进行编码。

算术编码利用了积累几率的概念。

算术码主要的编码方法是计算输入信源符号序列所对应的区间。

由于在编码进程中，每输入1个符号要进行乘法和加法运算，所以称此编码方法为算术编码。

2、算术编码的编码

设输入符号串s取自符号集S={a1,a2,a3,…,am}，p(ai)={p1,p2,p3,…,pm}，s后跟符号ai扩大成符号串sai，算术编码的迭代关系为: 

1)码字刷新：C(sai)=C(s)+P(ai)A(s)

2)区间刷新：A(sai)=p(ai)A(s) 

符号积累几率：

初始条件：

通过关于信源符号序列的积累散布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为[F(s),F(s)+P(s)) 。可取小区间内的1点来代表这序列。

编码方法：将符号序列的积累散布函数写成2进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的1个数C，并使k满足：

举例:

4、例题

[例]假定信源符号为{a,b, c, d}，这些符号的几率分别为{ 0.1, 0.4, 0.2, 0.3 }，对输入消息序列cadacdb进行算术编码。

解：根据这些几率可把间隔[0, 1)分成4个子间  隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)。信息可综合在表中：

编码时首先输入的符号是c，找到它的编码范围是[0.5, 0.7)。由于消息中第2个符号a的编码范围是[0, 0.1)，因此它的间隔就取[0.5, 0.7)的第1个10分之1作为新间隔[0.5, 0.52)。依此类推，编码第3个符号d时取新间隔为[0.514, 0.52)，… 。消息的编码输出可以是最后1个间隔中的任意数。

我们可以根据码字计算求出：K取17。

进而将终究输出的小数0.5143876转换为2进制：0.10000011101011110

进而终究的结果为：10000011101011110

具体的实现可以参考我的代码，谢谢！！！