实现算术编码及其译码
一、 实验内容
借助C++编程来实现对算术编码的编码及其译码算法的实现
二、实验环境
1. 计算机
2. VC++6.0
三、实验目的
1. 进一步熟悉算术编码的原理，及其基本的算法；
2. 通过编译，充分对于算术编码有进一步的了解和掌握；
3. 掌握C++语言编程（尤其是数值的进制转换，数值与字符串之间的转换等）
四、实验原理
算术编码
算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。
算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。
给定事件序列的算术编码步骤如下：
（1）编码器在开始时将“当前间隔”设置为[0，1)。
（2）对每一事件，编码器按步骤（a）和（b）进行处理
（a）编码器将“当前间隔”分为子间隔，每一个事件一个。
（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。
（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。
编码过程
假设信源符号为{A， B， C， D}，这些符号的概率分别为{ 0.1， 0.4， 0.2，0.3 }，根据这些概率可把间隔[0， 1]分成4个子间隔：[0， 0.1]， [0.1， 0.5]， [0.5， 0.7]， [0.7， 1]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。
下表为信源符号，概率和初始编码间隔
符号
A
B
C
D
概率
0.1
0.4
0.2
0.3
初始编码间隔
[0， 0.1)
[0.1， 0.5)
[0.5， 0.7)
[0.7， 1]
如果二进制消息序列的输入为：C A D A C D B。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号A的编码范围是[0， 0.1]，因此它的间隔就取[0.5， 0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号D时取新间隔为[0.514， 0.52]，编码第4个符号A时，取新间隔为[0.514， 0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。
编码和译码的全过程分别表示在下表。
编码过程
步骤
输入符号
编码间隔
编码判决
1
C
[0.5， 0.7]
符号的间隔范围[0.5， 0.7]
2
A
[0.5， 0.52]
[0.5， 0.7]间隔的第一个1/10
3
D
[0.514，0.52]
[0.5， 0.52]间隔的最后一个1/10
4
A
[0.514，0.5146]
[0.514， 0.52]间隔的第一个1/10
5
C
[0.5143， 0.51442]
[0.514， 0.5146]间隔的第五个1/10开始，二个1/10
6
D
[0.514384， 0.51442]
[0.5143， 0.51442]间隔的最后3个1/10
7
B
[0.5143836， 0.514402]
[0.514384，0.51442]间隔的4个1/10，从第1个1/10开始
8
从[0.5143876， 0.514402]中选择一个数作为输出：0.5143876
译码过程
步骤
间隔
译码符号
译码判决
1
[0.5， 0.7]
C
0.51439在间隔 [0.5， 0.7)
2
[0.5， 0.52]
A
0.51439在间隔 [0.5， 0.7)的第1个1/10
3
[0.514， 0.52]
D
0.51439在间隔[0.5， 0.52)的第7个1/10
4
[0.514， 0.5146]
A
0.51439在间隔[0.514， 0.52]的第1个1/10
5
[0.5143， 0.51442]
C
0.51439在间隔[0.514， 0.5146]的第5个1/10
6
[0.514384， 0.51442]
D
0.51439在间隔[0.5143， 0.51442]的第7个1/10
7
[0.51439， 0.5143948]
B
0.51439在间隔[0.51439，0.5143948]的第1个1/10
8
译码的消息：C A D A C D B
五、实验
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
：
算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码。而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0 ≤ n < 1.0)的小数n。所以用两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。
算术编码的算法思想如下：
（1）对一组信源符号按照符号的概率从大到小排序，将[0,1)设为当前
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
区间。按信源符号的概率序列在当前分析区间划分比例间隔。
（2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。
（3）仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第二步。直到“输入消息序列”检索完毕为止。
（4）最后的编码输出数就是编码好的数据。
六、实验程序：
#include
#include"math.h"
//定义所需要用到的变量及数组
char S[100], A[10];
float P[10],f[10],gFs;
//编码程序
void bianma(int a,int h)
{
int i,j;
float fr;
float ps=1;
float Fs=0;
float Sp[100],b[100],F[100];
//以待编码的个数和字符个数为循环周期，将待编码的字符所对应的概率存入到Fs中
for(i=0;i>a;
cout<<"请输入符号及其相对应的概率值，并按回车跳转："<>x;
A[i]=x;//将字符依次存入数组A中
cin>>y;
P[i]=y;//将字符所对应的概率依次存入到数组P中
}
for(i=1;i>ss;
if(ss=='*')break;//在以“*”为结尾的时候结束存储
S[h++]=ss;
}
cout<<"输入的字符经过算术编码之后为："<
本文档为【算术编码】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483