简单短序列的算术编码的MATLAB实现

1、简单短序列的算术编码的MATLAB实现正确实现的算术编码算法压缩能力Shannond定理描述的理论极限，是目前已知的压缩能力最强的无损压缩算法。不过，由于算术编码算法的实现比较复杂，使用它作为默认压缩算法的应用程序还相当少。在Unix平台上非常流行的bzip2(这个工具有命令行模式的Windows版本)使用的就是经过修改的算术编码算法。目前为止还没有使用算术编码作为默认压缩算法的Windows应用程序，WinRAR和WinIMP能够支持bzip2的解压。除此之外，在最新的JPEG标准中也用到了经过修改的算术编码压缩算法，但JPEG所用的那种算法受专利保护，因此使用时必须获得授权。在之后的文章会

2、很好的研究这个算法的实现：现在给出一个简单的实例：% 算术编码过程实例ssbm.m%about=.本实例说明：字符串不能太长，程序不加判断，请注意溢出；本实例只限定少数字符串 a b c d e；实例只是说明一下算术编码过程。;disp(about);str=input(请输入编码的字符串(本程序仅仅是一个实例，请仅输入a b c d e）:);l=0;r=1;d=1;%初始间隔 %程序限定字符为：a、b、c、d、ep=0.2 0.3 0.1 0.15 0.25;%字符的概率分布，sum(p)=1n=length(str);disp(a b c d e)disp(num2str(p)for i

3、=1:nswitch str(i)case am=1;case bm=2;case cm=3;case dm=4;case em=5;otherwiseerror(请不要输入其它字符！);end%判断字符pl=0;pr=0;for j=1:m-1pl=pl+p(j);endfor j=1:mpr=pr+p(j);end%概率统计l=l+d*pl;r=l+d*(pr-pl);strl=strcat(输入第,int2str(i),符号的间隔左右边界：);disp(strl);format longdisp(l);disp(r);d=r-l;end运行过程如下：本实例说明：字符串不能太长，程序不加判

4、断，请注意溢出；本实例只限定少数字符串 a b c d e；实例只是说明一下算术编码过程。请输入编码的字符串(本程序仅仅是一个实例，请仅输入a b c d e）:aaabdeda b c d e0.2 0.3 0.1 0.15 0.25输入第1符号的间隔左右边界：00.2000输入第2符号的间隔左右边界：00.0000输入第3符号的间隔左右边界：00.0000输入第4符号的间隔左右边界：0.00000.0000输入第5符号的间隔左右边界：0.00000.0000输入第6符号的间隔左右边界：0.00000.0000输入第7符号的间隔左右边界：0.00000.0000%I=imread(001.b

5、mp) %imshow(I); clear I=3 3 1 1 3 3 1 2;2 3 3 1 3 2 3 2;1 2 3 3 3 3 1 2; %I=1 1 1 1 0 0 1 0 1 1 1 0; m,n=size(I); % 第一列为灰度值,第二列为个数,第三列为概率百分数，应该也可以用imhist table = tabulate(I(); % 注意的是，tabulate要求I的元素必须为非负整数 % 否则，以采用如下方法求解 % 如1 2 3；1 2 2，则统计出结果1是2个，2是3个，3是1个 % sortM=sort(M(); % uniqueM=(diff(sortM);10)

6、; % count = sortM(uniqueM) diff(find(1;uniqueM) % 即color,p如下所示 color = table(:,1); p = table(:,3)/100; % 计算上下限 csump = cumsum(table(:,3); allLow =0,csump(1:end-1)/100; allHigh = csump/100; numberlow = 0; numberhigh = 1; for k = 1:m for kk = 1:n data = I(k,kk); low = allLow(data=color); high = allHig

7、h(data=color); range = numberhigh-numberlow; tmp = numberlow; numberlow = tmp+range*low; numberhigh = tmp+range*high; end end % the result range fprintf(算术编码范围下限为%16.15fnn,numberlow); fprintf(算术编码范围上限为%16.15fnn,numberhigh); % decoding Mat = zeros(m,n); for k = 1:m for kk = 1:n indx = numberlowallLow

8、; indx = indx 1; ind = diff(indx); ind = logical(ind); Mat(k,kk) = color(ind); low = allLow(ind); high = allHigh(ind); range = high - low; numberlow = numberlow-low; numberlow = numberlow/range; end end fprintf(原矩阵为:n) disp(I); fprintf(n); fprintf(解码矩阵:n); disp(Mat); 附 算术编码与译码原理： 1、 编码过程 算术编码方法是将被编码

9、的一则消息或符号串（序列）表示成0和1之间的一个间隔（Interval），即对一串符号直接编码成0,1区间上的一个浮点小数。符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。信源中的符号序列仍然要根据某种模式生成概率的大小来减少间隔。可能出现的符号概率要比不太可能出现的符号减少范围小，因此，只正加较少的比特位。 在传输任何符号串之前，0符号串的完整范围设为0,1。当一个符号被处理时，这一范围就依据分配给这一符号的那一范围变窄。算术编码的过程，实际上就是依据信源符号的发生概率对码区间分割的过程。 举例说明如下： 假设一则消息“static_tree”具有如下的概率分布： 字符 概

10、率 - （space） 0.1 a 0.1 e 0.3 r 0.1 s 0.1 t 0.3 下面用算术编码方法给该消息编码。 一旦字符的概率已知，就沿着“概率线”为每一个单独的符号设定一个范围，哪一个被设定到哪一段范围并不重要，只要编码和解码都以同样方式进行就可以，这里所用的6个字符被分配的范围（range）如下： 字符 概率 范围 (space) 0.1 0r0.1 a 0.1 0.1r0.2 e 0.3 0.2r0.5 r 0.1 0.5r0.6 s 0.1 0.6r0.7 t 0.3 0.7r0.6,0.7） (3)对第二个字符t编码，使用的新生范围为0.6,0.7），因为t的range

11、 low=0.7,range high=1.0,因此下一个low,high分别为 Low=0.6+0.10.70.67 High=0.6+0.11.00.70 Range=0.7-0.67=0.03 t将0.6,0.7）=0.67,0.70） (4)对第三个字符a编码，在新生成的0.67,0.70）中进行分割，因为a的range low=0.10,range high=0.2,因此下一个low,high分别为 Low=0.67+0.030.10.673 High=0.67+0.030.20.676 Range=0.676-0.673=0.003 a将0.67,0.70）=0.673,0.676

12、） (5)对第四个字符t编码，在新生成的0.673,0.676）上进行分割。因为t的range low=0.70,range high=1.0,则下一个low,high分别为 Low=0.673+0.0030.70.6751 High=0.673+0.0031.00.676 Range=0.0009 t将0.673,0.676）=0.6751,0.676） 同理得到下面各字符e,s,t,r,e,e编码所得到的范围分别为0.67528,0.67555），0.67528,0.675307），0.675 298 9,0.675 307），0.675 302 95,0.675 303 76），0.67

13、5 303 112,0.675 303 355），0.675 303 160 6,0.675 303 233 5） 将编码后的区间范围综合如下： 上述编码过程可以用下面的区间分割过程表示： 2、 解码过程 解码是编码的逆过程，了解了编码过程后，理解解码过程的操作就相对容易了。通过编码，最后的下界值0.675 303 160 6就是消息“state_tree”的唯一编码。然后解码时，通过判断哪一个符号能拥有我们已编码的消息落在的空间来找出消息中的第一个符号。由于0.675 303 160 6落在0.6,0.7）之间，因此可解得第一个符号是s。 在解出s后，由于我们知道s的范围的上界和下界，利用编码的逆作用，首先去掉s的下界值0.6，得0.075 303 160 6，然后用s的范围range=0.1去除所得到的0.0