算术编码

算术编码•用算术编码方法是将被编码的一个消息或一个符号串（序列）表示成0和1之间的一个间隔，即对一串符号直接编码成[0，1)区间上的一个浮点小数，在传输任何符号串（消息）之前，设符号串的完整范围为[0，1)。当一个符号被处理时，这一范围就依据分配给这一符号的那一范围变窄，间隔变小，当符号串序列越长，则编码表示它的间隔越小，同时表示这一间隔所需的位数就越多，直到完成对所有符号串的编码。算术编码的过程，实际上就是依据信息源符号串的发生概率对码区间分割的过程。1编码过程•假如要对有10个符号的信息源发出的字符串“statetree”进行编码，符号串具有如下的概率分布如图3-7所示。1编码过程•按每个符号出现的概率对[0，1)区间进行划分，显然每个符号都有一对应的子区间，这里所用的10个字符被分配的范围如图3-8所示。1编码过程•按对‘statestree”’的算术编码过程为：（1）初始化时，被分割的范围range＝high－low＝[0，1)＝1－0＝1，下一个范围的低、高端分别由下式计算：low＝low＋range×rangelowhigh＝low＋range×rangehigh其中等号右边的low为上一个被编码字符的范围低值；rangelow和rangehigh分别为本次被编符号已给定出现的概率范围的low和high。1编码过程•（2）对消息第1字符s编码：s的rangelow＝0.60，s的rangehigh＝0.70，因此下一个区间的low和high为：low＝low＋range×rangelow＝0＋1×0.6＝0.6high＝low＋range×rangehigh＝0＋1×0.7＝0.7range＝high一low＝0.7一0.6＝0.1S将区间［0，1）［0.6，0.7）注意：字符“”表示“分割为”字符。1编码过程•（3）对第2个字符t编码，使用的新生成范围为［0.6，0.7)，因为t的rangelow＝0.70，rangehigh＝1.00，因此下一个low，high分别为：low＝low＋range×rangelow＝0.6＋0.1×0.7＝0.67high＝low＋range×rangehigh＝0.6＋0.1×1.0＝0.70range＝high一low＝0.7一0.67＝0.03t将区间［0.6，0.7)［0.67，0.70)1编码过程•（4）对第3个字符a编码，在新生成的［0.67，0.70)中进行分割。因为a的rangelow＝0.10，rangehigh＝0.2，因此下一个low，high分别为：low＝low＋range×rangelow＝0.67＋0.03×0.1＝0.673high＝low＋range×rangehigh＝0.67＋0.03×0.2＝0.676range＝high一low＝0.676一0.673＝0.003a将区间［0.67，0.7)［0.673，0.676)1编码过程•（5）对第4个字符t编码，在新生成的［0.673，0.676)上进行分割。因为t的rangelow＝0.70，rangehigh＝1.00，因此下一个low，high分别为：low＝low＋range×rangelow＝0.673＋0.003×0.7＝0.6751high＝low＋range×rangehigh＝0.673＋0.003×1.0＝0.676range＝high一low＝0.676一0.6751＝0.0009t将区间［0.673，0.676)［0.6751，0.676)1编码过程•同理得到下面各字符e，，t，r，e，e编码所得到的范围分别为:[0.67528，0.67555），［0.67528，0.675307），［0.6752989，0.675307），［0.67530295，0.67530376），［0.675303112，0.675303355）［0.6753031606，0.6753032335)。1编码过程•将编码后的区间范围综合如图3-9所示：我们用0.6753031606代表字符串“statetree”，从而达到高效编码的目的，这就是算术编码的基本思想。1编码过程•上述算术编码区间分割过程可用图3-10表示。2解码过程•通过编码，最后一个子区间的的下界值0.6753031606就是字符串“statetree”的惟一编码。然后在解码时，通过判断哪一个字符能拥有我们已编码的消息落在的空间来找出消息中的第一个字符。由于0.6753031606落在[0.6，0.7]之问，因此马上就可解得第1个符号是S。s060.6753031610-060.675303162解码过程•在解出S后，由于我们知道S的范围的上界和下界，利用编码的逆作用，首先除掉S的下界值0.6，得0.075303606，然后用s的范围range＝0.1去除所得到的0.0753031606，得到0.753031606，接着找出0.753031606所落在的区间［0.7，1.0）。就可解得第2个符号是t。t60.753031600.10.6-060.675303162解码过程•去掉t的下界值0.67，得0.0053031606，然后用t的range＝0.03除0.0053031606，得到0.17677202，找出0.17677202所属范围的字符a，a0.176772020.030.67-060.675303162解码过程•如此继续解码操作，就可以获得字符串“statetree”的准确译码。分析以上所述的解码操作过程，我们得到其解码公式为注意：Number为字符串的编码。Numberrangelowrange-Number