数据处理方法-算数编码
一、算数编码简介
编码是信息从一种形式或格式转换为另一种形式的过程,用预先规定的方法
将文字、数字或者是其他对象编成数码,或将信息、数据转换成规定的电脉冲信
号。各种编码在电子计算机、无线通信、图像压缩等方面广泛使用。算术编码是
图像压缩的主要编码算法之一,是一种无损数据压缩方法,也是一种熵编码的方
法。和其它熵编码方法不同,算术编码是直接把输入的整个消息序列编码为一个
满足(0.0≤n<1.0)的小数 n,将该小数的二进制码作为编码输出。其解码过程是
编码过程的逆推:从编码输出的小数开始,不断地寻找小数落在了哪个概率区间,
就能将原来的消息序列一个个地复原出来。
注意:在本赛题中,只需要进行编码运算。
二、算数编码过程
算术编码的方法是将被编码的一个消息或一个符号串(序列)表示成 0 和 1
之间的一个间隔区间,即对一串符号直接编码成[0,1)区间上的一个浮点小数,
在传输任何符号串(消息)之前,设符号串的完整区间范围为[0,1)。当一个符
号被处理时,区间范围就依据当前编码的符号进行区间更新,随着编码的进行,
该区间范围逐渐变窄,符号串序列越长,区间范围的间隔也就越小,同时表示这
一区间所需的位数就越多,直到完成所有符号串的编码。算术编码的过程,实际
上就是依据信息源符号串的发生概率对码区间进行一步步的分割过程。
下面结合实例对其编码过程进行详述:
1) 假设 RFID 中读取的数据为“01ABC2BAD0DCCA31”;则需要编码的字符串
即为“ABCBADDCCA”,统计其中的字符“A-D”出现的次数。得出该符号
串的概率分布如下表所示:
符号
次数
概率
A
3
0.3
B
2
0.2
C
3
0.3
D
2
0.2
2) 按每个符号出现的概率对[0,1)区间进行划分。将区间[0,1)连续划分成
多个子区间,每个子区间代表一个上述字符,区间的大小正比于这个字
符在文中出现的概 p。概率越大,则区间越大。所有的子区间加起来正