簡單短序列的算術(shù)編碼的MATLAB實現(xiàn)

簡單短序列的算術(shù)編碼的MATLAB實現(xiàn)簡單短序列的算術(shù)編碼的MATLAB實現(xiàn)簡單短序列的算術(shù)編碼的MATLAB實現(xiàn)資料僅供參考文件編號：2022年4月簡單短序列的算術(shù)編碼的MATLAB實現(xiàn)版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：簡單短序列的算術(shù)編碼的MATLAB實現(xiàn)正確實現(xiàn)的算術(shù)編碼算法壓縮能力Shannond定理描述的理論極限，是目前已知的壓縮能力最強的無損壓縮算法。

不過，由于算術(shù)編碼算法的實現(xiàn)比較復(fù)雜，使用它作為默認(rèn)壓縮算法的應(yīng)用程序還相當(dāng)少。在Unix平臺上非常流行的bzip2(這個工具有命令行模式的Windows版本)使用的就是經(jīng)過修改的算術(shù)編碼算法。

目前為止還沒有使用算術(shù)編碼作為默認(rèn)壓縮算法的Windows應(yīng)用程序，WinRAR和WinIMP能夠支持bzip2的解壓。除此之外，在最新的JPEG標(biāo)準(zhǔn)中也用到了經(jīng)過修改的算術(shù)編碼壓縮算法，但JPEG所用的那種算法受專利保護，因此使用時必須獲得授權(quán)。

在之后的文章會很好的研究這個算法的實現(xiàn)：現(xiàn)在給出一個簡單的實例：%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%算術(shù)編碼過程實例

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

about={...

'本實例說明：'

'字符串不能太長，程序不加判斷，請注意溢出；'

'本實例只限定少數(shù)字符串a(chǎn)bcde；'

'實例只是說明一下算術(shù)編碼過程。'};

disp(about);

str=input('請輸入編碼的字符串(本程序僅僅是一個實例，請僅輸入abcde）:');

l=0;r=1;d=1;

%初始間隔%程序限定字符為：a、b、c、d、ep=[];%字符的概率分布，sum(p)=1n=length(str);disp('abcde')disp(num2str(p))fori=1:n

switchstr(i)

case'a'

m=1;

case'b'

m=2;

case'c'

m=3;

case'd'

m=4;

case'e'

m=5;

otherwise

error('請不要輸入其它字符！');

end

%判斷字符

pl=0;pr=0;

forj=1:m-1

pl=pl+p(j);

end

forj=1:m

pr=pr+p(j);

end

%概率統(tǒng)計

l=l+d*pl;

r=l+d*(pr-pl);

strl=strcat('輸入第',int2str(i),'符號的間隔左右邊界：');

disp(strl);

formatlong

disp(l);disp(r);

d=r-l;end運行過程如下：'本實例說明：''字符串不能太長，程序不加判斷，請注意溢出；''本實例只限定少數(shù)字符串a(chǎn)bcde；''實例只是說明一下算術(shù)編碼過程。'請輸入編碼的字符串(本程序僅僅是一個實例，請僅輸入abcde）:'aaabded'abcde輸入第1符號的間隔左右邊界：0輸入第2符號的間隔左右邊界：0輸入第3符號的間隔左右邊界：0輸入第4符號的間隔左右邊界：輸入第5符號的間隔左右邊界：輸入第6符號的間隔左右邊界：輸入第7符號的間隔左右邊界：

%I=imread('')

%imshow(I);

clear

I=[33113312;23313232;12333312];

%I=[111100101110];

[m,n]=size(I);

%第一列為灰度值,第二列為個數(shù),第三列為概率百分?jǐn)?shù)，應(yīng)該也可以用imhist

table=tabulate(I();

%注意的是，tabulate要求I的元素必須為非負(fù)整數(shù)

%否則，以采用如下方法求解

%如[123；122]，則統(tǒng)計出結(jié)果1是2個，2是3個，3是1個

%sortM=sort(M();

%uniqueM=([diff(sortM);1]>0);

%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;fork=1:m

forkk=1:n

data=I(k,kk);

low=allLow(data==color);

high=allHigh(data==color);

range=numberhigh-numberlow;

tmp=numberlow;

numberlow=tmp+range*low;

numberhigh=tmp+range*high;

endend%theresultrangefprintf('算術(shù)編碼范圍下限為%\n\n',numberlow);fprintf('算術(shù)編碼范圍上限為%\n\n',numberhigh);%decodingMat=zeros(m,n);fork=1:m

forkk=1:n

indx=numberlow<allLow;

indx=[indx1];

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;

endendfprintf('原矩陣為:\n')disp(I);fprintf('\n');fprintf('解碼矩陣:\n');disp(Mat);

附算術(shù)編碼與譯碼原理：1、編碼過程算術(shù)編碼方法是將被編碼的一則消息或符號串（序列）表示成0和1之間的一個間隔（Interval），即對一串符號直接編碼成[0,1]區(qū)間上的一個浮點小數(shù)。符號序列越長，編碼表示它的間隔越小，表示這一間隔所需的位數(shù)就越多。信源中的符號序列仍然要根據(jù)某種模式生成概率的大小來減少間隔?？赡艹霈F(xiàn)的符號概率要比不太可能出現(xiàn)的符號減少范圍小，因此，只正加較少的比特位。在傳輸任何符號串之前，0符號串的完整范圍設(shè)為[0,1]。當(dāng)一個符號被處理時，這一范圍就依據(jù)分配給這一符號的那一范圍變窄。算術(shù)編碼的過程，實際上就是依據(jù)信源符號的發(fā)生概率對碼區(qū)間分割的過程。舉例說明如下：假設(shè)一則消息“static_tree”具有如下的概率分布：

字符

概率

---------------------------------------------------------------

＿（space）

a

e

r

s

t

下面用算術(shù)編碼方法給該消息編碼。一旦字符的概率已知，就沿著“概率線”為每一個單獨的符號設(shè)定一個范圍，哪一個被設(shè)定到哪一段范圍并不重要，只要編碼和解碼都以同樣方式進行就可以，這里所用的6個字符被分配的范圍（range）如下：

字符

概率

范圍

＿(space)

0≤r<

a

≤r<

e

≤r<

r

≤r<

s

≤r<

t

≤r<

----------------------------------------------------------------

對“state_tree”的算術(shù)編碼過程為：（1）初始化時，被分割的范圍range=high-low=[0,1）,下一個范圍的低、高端分別由下式計算：

Low=low+range×rangelow

High=low+range×rangehigh其中等號右邊的low為上一個被編碼字符的范圍低；rangelow和rangehigh分別為被編碼符號已給定的字符出現(xiàn)概率范圍的low和high。（2）對消息第一字符s編碼：s的rangelow=，

s的rangehigh=因此，下一個區(qū)間的low和high為：

Low=low+range×rangelow=0+1×=

High=low+range×rangehigh=0+1×=

Range=high-low=

S將區(qū)間[0,1）=>[,）

(3)對第二個字符t編碼，使用的新生范圍為[,），因為t的rangelow=,rangehigh=,因此下一個low,high分別為

Low=+×＝

High=+×＝

Range=

t將[,）=>[,）

(4)對第三個字符a編碼，在新生成的[,）中進行分割，因為a的rangelow=,rangehigh=,因此下一個low,high分別為

Low=+×＝

High=+×＝

Range=

a將[,）=>[,）

(5)對第四個字符t編碼，在新生成的[,）上進行分割。因為t的rangelow=,rangehigh=,則下一個low,high分別為

Low=+×＝

High=+×＝

Range=

t將[,）=>[,）

同理得到下面各字符e,＿,s,t,r,e,e編碼所得到的范圍分別為[,），[,），[2989,307），[30295,30376），[303112,303355），[3031606,3032335）

將編碼后的區(qū)間范圍綜合如下：

上述編碼過程可以用下面的區(qū)間分割過程表示：

2、解碼過程

解碼是編碼的逆過程，了解了編碼過程后，理解解碼過程的操作就相對容易了。通過編碼，最后的下界值3031606就是消息“state_tree”的唯一編碼。然后解碼時，通過判斷哪一個符號能擁有我們已編碼的消息落在的空間來找出消息中的第一個符號。由于303160