linux上用c实现算术编码（三）--算术编码理论讲解
一、算术编码定义
它是一种非分组编码算法。它是从全序列出发，采用递推形式的连续编码。它不是将单个的信源符号映射成一个码字，而是将整个输入序列的符号依据它们的概率映射为实数轴上区间[0 1)内的一个小区间，再在该小区间内选择一个代表性的二进制小数，作为实际的编码输出。
算术编码不同于霍夫曼码，它是非分组（非块）码。它从全序列出发，考虑符号之间的关系来进行编码。算术编码利用了累积概率的概念。算术码主要的编码方法是计算输入信源符号序列所对应的区间。因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。
二、算术编码的编码
设输入符号串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)) 。可取小区间内的一点来代表这序列。
编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足：
举例:
四、例题
[例]假设信源符号为{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)。由于消息中第二个符号a的编码范围是[0, 0.1)，因此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52)。依此类推，编码第3个符号d时取新间隔为[0.514, 0.52)，… 。消息的编码输出可以是最后一个间隔中的任意数。
我们可以根据码字计算求出：K取17。
进而将最终输出的小数0.5143876转换为二进制：0.10000011101011110
进而最终的结果为：10000011101011110
具体的实现可以参考我的代码，谢谢！！！
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
