算術編碼壓縮
⑴ 算術編碼的相關介紹
上面對算術編碼的解釋進行了一些簡化。尤其是，這種寫法看起來好像算術編碼首先使用無限精度精度的數值計算總體上表示最後節點的分數，然後在編碼結束的時候將這個分數轉換成最終的形式。許多算術編碼器使用優先精度的數值計算，而不是盡量去模擬無限精度，因為它們知道解碼器能夠匹配、並且將所計算的分數在那個精度四捨五入到對應值。一個例子能夠說明一個模型要將間隔[0,1]分成三份並且使用8位的精度來實現。注意既然精度已經知道，我們能用的二進制數值的范圍也已經知道。
一個稱為再歸一化的過程使有限精度不再是能夠編碼的字元數目的限制。當范圍減小到范圍內的所有數值共享特定的數字時，那些數字就送到輸出數據中。盡管計算機能夠處理許多位數的精度，編碼所用位數少於它們的精度，這樣現存的數據進行左移，在右面添加新的數據位以盡量擴展能用的數據范圍。注意這樣的結果出現在前面三個例子中的兩個裡面。 許多算術編碼所用的不同方法受美國專利的保護。其中一些專利對於實現一些國際標准中定義的算術編碼演算法是很關鍵的。在這種情況下，這些專利通常按照一種合理和非歧視（RAND）授權協議使用（至少是作為標准委員會的一種策略）。在一些著名的案例中（包括一些涉及 IBM的專利）這些授權是免費的，而在另外一些案例中，則收取一定的授權費用。RAND條款的授權協議不一定能夠滿足所有打算使用這項技術的用戶，因為對於一個打算生產擁有所有權軟體的公司來說這項費用是「合理的」，而對於自由軟體和開源軟體項目來說它是不合理的。
在算術編碼領域做了很多開創性工作並擁有很多專利的一個著名公司是IBM。一些分析人士感到那種認為沒有一種實用並且有效的算術編碼能夠在不觸犯IBM和其它公司擁有的專利條件下實現只是數據壓縮界中的一種持續的urban legend（尤其是當看到有效的算術編碼已經使用了很長時間最初的專利開始到期）。然而，由於專利法沒有提供「明確界線」測試所以一種威懾心理總讓人擔憂法庭將會找到觸犯專利的特殊應用，並且隨著對於專利范圍的詳細審查將會發現一個不好的裁決將帶來很大的損失，這些技術的專利保護然而對它們的應用產生了一種阻止的效果。至少一種重要的壓縮軟體bzip2，出於對於專利狀況的擔心，故意停止了算術編碼的使用而轉向Huffman編碼。
關於算術編碼的美國專利列在下面。
Patent 4,122,440 — (IBM) 提交日期 March 4, 1977, 批准日期 Oct 24, 1978 （現在已經到期）
Patent 4,286,256 — (IBM) 批准日期 Aug 25, 1981 （大概已經到期）
Patent 4,467,317 — (IBM) 批准日期 Aug 21, 1984 （大概已經到期）
Patent 4,652,856 — (IBM) 批准日期 Feb 4, 1986 （大概已經到期）
Patent 4,891,643 — (IBM) 提交時間 1986/09/15, 批准日期 1990/01/02
Patent 4,905,297 — (IBM) 批准日期 Feb 27, 1990
Patent 4,933,883 — (IBM) 批准日期 Jun 12, 1990
Patent 4,935,882 — (IBM) 批准日期 Jun 19, 1990
Patent 4,989,000 — (???) 提交時間 1989/06/19, 批准日期 1991/01/29
Patent 5,099,440
Patent 5,272,478 — (Ricoh)
注意：這個列表沒有囊括所有的專利。關於更多的專利信息請參見後面的鏈接。
算術編碼的專利可能在其它國家司法領域存在，參見軟體專利中關於軟體在世界各地專利性的討論。
⑵ 求教算術編碼壓縮編程
——字元太多的話在編碼的時候會不會比較麻煩？
壓縮編碼難道不是根據一個文本自動統計出來的嗎？這個概率表每個文本不一樣吧，比如這個文本a字元多，另一個文本b字元多
⑶ 算術編碼的介紹
算術編碼，是圖像壓縮的主要演算法之一。 是一種無損數據壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在於，其他的熵編碼方法通常是把輸入的消息分割為符號，然後對每個符號進行編碼，而算術編碼是直接把整個輸入的消息編碼為一個數，一個滿足(0.0 ≤ n < 1.0)的小數n。
⑷ 數字圖像處理及算術編碼（或DCT壓縮編碼）模擬實現
1）數字圖像的變換：普通傅里葉變換(ft)與逆變換（ift）、快速傅里葉變換（fft）與逆變換(ifft)、離散餘弦變換（DCT），小波變換。
2) 數字圖像直方圖的統計及繪制等；
clc;
Y=imread('C:\zheng.jpg');
length(size(Y))==3
s=rgb2gray(Y);
imshow(Y);
title('原圖'); %figure1
Y=rgb2gray(Y);
figure;imshow(Y);title('原始圖像'); % figue2
[J,T] = histeq(Y);
figure;imshow(J);title('增強圖像'); % figue3
figure ;imhist(Y,64);title('原始圖像直方圖'); % figue4
figure ;imhist(J,64);title('均衡化圖像直方圖');% figue5
clear all;
Y=imread('C:\zheng.jpg');%導入圖片%傅里葉變換
Y=rgb2gray(Y);
figure(1);
imshow(Y);
title('灰度化後的圖像');
Y1=fftshift(fft2(Y));
figure(2);
Y2=abs(Y1);
imshow(Y2,[]);
title('傅里葉變換的圖像');
figure(3);
Y2=abs(ifft2(Y1))/255;
imshow(Y2);
title('傅里葉逆變換的圖像');
J=fft2(double(s));%快速傅里葉變換
K=fftshift(fft2(double(s)));
F=ifft2(K);%快速傅里葉變換
figure; %figure6
imshow(J);
title('FFT變換結果');
figure; %figure7
imshow(log(abs(K)+1),[]);
title('零點平移');
figure; %figure8
imshow(abs(F),[]);
title('IFFT變換結果');
% 圖象的DCT變換
RGB=imread('C:\zheng.jpg');
figure;%figure9
subplot(1,2,1)
imshow(RGB);
title('彩色原圖');
a=rgb2gray(RGB);
subplot(1,2,2)
imshow(a);
title('灰度圖');
figure;%figure10
b=dct2(a);
imshow(log(abs(b)),[]),colormap(jet(64)),colorbar;
title('DCT變換結果');
figure;%figure11
b(abs(b)<10)=0;
% idct
c=idct2(b)/255;
imshow(c);
title('IDCT變換結果')
小波變換
clear
I= imread('C:\zheng.jpg');
X=rgb2gray(I);
subplot (121) ;
imshow(X);
title ('原始圖像') ;%畫出原圖像
[c,s] =wavedec2 (X, 2, 'sym4') ;
%進行二層小波分解
len = length ( c) ;%處理分解系數,突出輪廓,弱化細節
for I = 1: len
if (c( I )>350)
c( I ) = 2*c (I ) ;
else
c( I ) = 0.5*c( I ) ;
end
end
nx =waverec2 ( c, s, 'sym4') ;
%分解系數重構
subplot(122) ;
image( nx) ;
title('增強圖像')
%畫出增強圖像
⑸ 基於算術編碼的數據壓縮演算法及其實現
基於算術編碼的數據壓縮演算法及其實現
http://www.noreal.com.cn/2007/08/%E5%9F%BA%E4%BA%8E%E7%AE%97%E6%9C%AF%E7%BC%96%E7%A0%81%E7%9A%84%E6%95%B0%E6%8D%AE%E5%8E%8B%E7%BC%A9%E7%AE%97%E6%B3%95%E7%A0%94%E7%A9%B6%E4%B8%8E%E5%AE%9E%E7%8E%B0.html
以助人為快樂之本。
⑹ 算術編碼壓縮解壓縮文本文件的源程序，最好有說明文檔，用C或C++語言，要能運行啊！
LZW演算法
//build : cl -O2 lzw.cpp
/********************************************************************
**
** Copyright (c) 1989 Mark R. Nelson
**
** LZW data compression/expansion demonstration program.
**
** April 13, 1989
**
*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BITS 12 /* Setting the number of bits to 12, 13*/
#define HASHING_SHIFT BITS-8 /* or 14 affects several constants. */
#define MAX_VALUE (1 << BITS) - 1 /* Note that MS-DOS machines need to */
#define MAX_CODE MAX_VALUE - 1 /* compile their code in large model if*/
/* 14 bits are selected. */
#if BITS == 14
#define TABLE_SIZE 18041 /* The string table size needs to be a */
#endif /* prime number that is somewhat larger*/
#if BITS == 13 /* than 2**BITS. */
#define TABLE_SIZE 9029
#endif
#if BITS <= 12
#define TABLE_SIZE 5021
#endif
//void *malloc();
int *code_value; /* This is the code value array */
unsigned int *prefix_code; /* This array holds the prefix codes */
unsigned char *append_character; /* This array holds the appended chars */
unsigned char decode_stack[4000]; /* This array holds the decoded string */
/********************************************************************
**
** This program gets a file name from the command line. It compresses the
** file, placing its output in a file named test.lzw. It then expands
** test.lzw into test.out. Test.out should then be an exact plicate of
** the input file.
**
*************************************************************************/
void compress(FILE *input,FILE *output);
void expand(FILE *input,FILE *output);
unsigned int find_match(int hash_prefix,unsigned int hash_character);
unsigned int input_code(FILE *input);
void output_code(FILE *output,unsigned int code);
int main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];
/*
** The three buffers are needed for the compression phase.
*/
code_value=(int*)malloc(TABLE_SIZE*sizeof(unsigned int));
prefix_code=(unsigned int*)malloc(TABLE_SIZE*sizeof(unsigned int));
append_character=(unsigned char *)malloc(TABLE_SIZE*sizeof(unsigned char));
if (code_value==NULL || prefix_code==NULL || append_character==NULL)
{
printf("Fatal error allocating table space!\n");
return 1;
}
/*
** Get the file name, open it up, and open up the lzw output file.
*/
if (argc>1)
strcpy(input_file_name,argv[1]);
else
{
printf("Input file name? ");
scanf("%s",input_file_name);
}
input_file=fopen(input_file_name,"rb");
lzw_file=fopen("test.lzw","wb");
if (input_file==NULL || lzw_file==NULL)
{
printf("Fatal error opening files.\n");
return 1;
};
/*
** Compress the file.
*/
compress(input_file,lzw_file);
fclose(input_file);
fclose(lzw_file);
free(code_value);
/*
** Now open the files for the expansion.
*/
lzw_file=fopen("test.lzw","rb");
output_file=fopen("test.out","wb");
if (lzw_file==NULL || output_file==NULL)
{
printf("Fatal error opening files.\n");
return 1;
};
/*
** Expand the file.
*/
expand(lzw_file,output_file);
fclose(lzw_file);
fclose(output_file);
free(prefix_code);
free(append_character);
return 1;
}
/*
** This is the compression routine. The code should be a fairly close
** match to the algorithm accompanying the article.
**
*/
void compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
next_code=256; /* Next code is the next available string code*/
for (i=0;i<TABLE_SIZE;i++) /* Clear out the string table before starting */
code_value[i]=-1;
i=0;
printf("Compressing...\n");
string_code=getc(input); /* Get the first code */
/*
** This is the main loop where it all happens. This loop runs util all of
** the input has been exhausted. Note that it stops adding codes to the
** table after all of the possible codes have been defined.
*/
while ((character=getc(input)) != (unsigned)EOF)
{
if (++i==1000) /* Print a * every 1000 */
{ /* input characters. This */
i=0; /* is just a pacifier. */
printf("*");
}
index=find_match(string_code,character);/* See if the string is in */
if (code_value[index] != -1) /* the table. If it is, */
string_code=code_value[index]; /* get the code value. If */
else /* the string is not in the*/
{ /* table, try to add it. */
if (next_code <= MAX_CODE)
{
code_value[index]=next_code++;
prefix_code[index]=string_code;
append_character[index]=character;
}
output_code(output,string_code); /* When a string is found */
string_code=character; /* that is not in the table*/
} /* I output the last string*/
} /* after adding the new one*/
/*
** End of the main loop.
*/
output_code(output,string_code); /* Output the last code */
output_code(output,MAX_VALUE); /* Output the end of buffer code */
output_code(output,0); /* This code flushes the output buffer*/
printf("\n");
}
/*
** This is the hashing routine. It tries to find a match for the prefix+char
** string in the string table. If it finds it, the index is returned. If
** the string is not found, the first available index in the string table is
** returned instead.
*/
unsigned int find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;
index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
if (index == 0)
offset = 1;
else
offset = TABLE_SIZE - index;
while (1)
{
if (code_value[index] == -1)
return(index);
if (prefix_code[index] == hash_prefix &&
append_character[index] == hash_character)
return(index);
index -= offset;
if (index < 0)
index += TABLE_SIZE;
}
}
/*
** This is the expansion routine. It takes an LZW format file, and expands
** it to an output file. The code here should be a fairly close match to
** the algorithm in the accompanying article.
*/
void expand(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
unsigned char *decode_string(unsigned char *buffer,unsigned int code);
next_code=256; /* This is the next available code to define */
counter=0; /* Counter is used as a pacifier. */
printf("Expanding...\n");
old_code=input_code(input); /* Read in the first code, initialize the */
character=old_code; /* character variable, and send the first */
putc(old_code,output); /* code to the output file */
/*
** This is the main expansion loop. It reads in characters from the LZW file
** until it sees the special code used to inidicate the end of the data.
*/
while ((new_code=input_code(input)) != (MAX_VALUE))
{
if (++counter==1000) /* This section of code prints out */
{ /* an asterisk every 1000 characters */
counter=0; /* It is just a pacifier. */
printf("*");
}
/*
** This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
** case which generates an undefined code. It handles it by decoding
** the last code, and adding a single character to the end of the decode string.
*/
if (new_code>=next_code)
{
*decode_stack=character;
string=decode_string(decode_stack+1,old_code);
}
/*
** Otherwise we do a straight decode of the new code.
*/
else
string=decode_string(decode_stack,new_code);
/*
** Now we output the decoded string in reverse order.
*/
character=*string;
while (string >= decode_stack)
putc(*string--,output);
/*
** Finally, if possible, add a new code to the string table.
*/
if (next_code <= MAX_CODE)
{
prefix_code[next_code]=old_code;
append_character[next_code]=character;
next_code++;
}
old_code=new_code;
}
printf("\n");
}
/*
** This routine simply decodes a string from the string table, storing
** it in a buffer. The buffer can then be output in reverse order by
** the expansion program.
*/
unsigned char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;
i=0;
while (code > 255)
{
*buffer++ = append_character[code];
code=prefix_code[code];
if (i++>=4094)
{
printf("Fatal error ring code expansion.\n");
return NULL;
}
}
*buffer=code;
return(buffer);
}
/*
** The following two routines are used to output variable length
** codes. They are written strictly for clarity, and are not
** particularyl efficient.
*/
unsigned int input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
while (input_bit_count <= 24)
{
input_bit_buffer |=
(unsigned long) getc(input) << (24-input_bit_count);
input_bit_count += 8;
}
return_value=input_bit_buffer >> (32-BITS);
input_bit_buffer <<= BITS;
input_bit_count -= BITS;
return(return_value);
}
void output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
output_bit_count += BITS;
while (output_bit_count >= 8)
{
putc(output_bit_buffer >> 24,output);
output_bit_buffer <<= 8;
output_bit_count -= 8;
}
}
⑺ 算術編碼的解碼問題
給你幾點思路：
1：所謂的編碼解碼可以約看於壓縮和解壓縮，無論是哪種編碼方式，都不可能是對所有字串或者關鍵串全部通過一組運算來得到key的？首先這已經是一種，無論從運算量、時間量、空間量都不允許這樣做，好比如你要求計算機計算
兩位數乘兩位數，這樣的要求還是絕對可以完成的，但是要求幾千位數同時乘幾千位數，那計算機怎麼乘？怎麼運算？現在的cpu包括所謂4核的芯，都不可能出現能實現這個要求的指令，而答案必然是分組分部計算，不可能同時運算的。
2：結合第一點的結論，也就是你再算術編碼的時候的運算公式是什麼，然後你得人為的把它拆分，讓字串能每讀取一部分的串通過運算累加後也能得到結果。
通過這一步驟你不需要全部讀完所有的字串，只需要讀取一部分運算，再讀部分運算，從而累加結果。
3：無論是字串還是key都是以char[]來存儲的，因為能開辟的空間較大，同時也是有限的，看你的堆棧設置，當然一般來說完全夠用了，你要是在運行中還出現溢出，那麼請你回頭考慮的你的演算法和解碼過程了
⑻ 算術編碼的工作原理
在給定符號集和符號概率的情況下，算術編碼可以給出接近最優的編碼結果。使用算術編碼的壓縮演算法通常先要對輸入符號的概率進行估計，然後再編碼。這個估計越准，編碼結果就越接近最優的結果。
例: 對一個簡單的信號源進行觀察，得到的統計模型如下：
60% 的機會出現符號 中性
20% 的機會出現符號 陽性
10% 的機會出現符號 陰性
10% 的機會出現符號 數據結束符. (出現這個符號的意思是該信號源'內部中止'，在進行數據壓縮時這樣的情況是很常見的。當第一次也是唯一的一次看到這個符號時，解碼器就知道整個信號流都被解碼完成了。)
算術編碼可以處理的例子不止是這種只有四種符號的情況，更復雜的情況也可以處理，包括高階的情況。所謂高階的情況是指當前符號出現的概率受之前出現符號的影響，這時候之前出現的符號，也被稱為上下文。比如在英文文檔編碼的時候，例如，在字母Q或者q出現之後，字母u出現的概率就大大提高了。這種模型還可以進行自適應的變化，即在某種上下文下出現的概率分布的估計隨著每次這種上下文出現時的符號而自適應更新，從而更加符合實際的概率分布。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。
編碼過程的每一步，除了最後一步，都是相同的。編碼器通常需要考慮下面三種數據：
下一個要編碼的符號
當前的區間(在編第一個符號之前，這個區間是[0,1), 但是之後每次編碼區間都會變化)
編碼器將當前的區間分成若乾子區間，每個子區間的長度與當前上下文下可能出現的對應符號的概率成正比。當前要編碼的符號對應的子區間成為在下一步編碼中的初始區間。
例: 對於前面提出的4符號模型:
中性對應的區間是 [0, 0.6)
陽性對應的區間是 [0.6, 0.8)
陰性對應的區間是 [0.8, 0.9)
數據結束符對應的區間是 [0.9, 1)
當所有的符號都編碼完畢，最終得到的結果區間即唯一的確定了已編碼的符號序列。任何人使用該區間和使用的模型參數即可以解碼重建得到該符號序列。
實際上我們並不需要傳輸最後的結果區間，實際上，我們只需要傳輸該區間中的一個小數即可。在實用中，只要傳輸足夠的該小數足夠的位數(不論幾進制)，以保證以這些位數開頭的所有小數都位於結果區間就可以了。
例: 下面對使用前面提到的4符號模型進行編碼的一段信息進行解碼。編碼的結果是0.538(為了容易理解，這里使用十進制而不是二進制；我們也假設我們得到的結果的位數恰好夠我們解碼。下面會討論這兩個問題)。
像編碼器所作的那樣我們從區間[0,1)開始，使用相同的模型，我們將它分成編碼器所必需的四個子區間。分數0.538落在NEUTRAL坐在的子區間[0,0.6)；這向我們提示編碼器所讀的第一個符號必然是NEUTRAL，這樣我們就可以將它作為消息的第一個符號記下來。
然後我們將區間[0,0.6)分成子區間：
中性 的區間是 [0, 0.36) -- [0, 0.6) 的 60%
陽性 的區間是 [0.36, 0.48) -- [0, 0.6) 的 20%
陰性 的區間是 [0.48, 0.54) -- [0, 0.6) 的 10%
數據結束符 的區間是 [0.54, 0.6). -- [0, 0.6) 的 10%
我們的分數 .538 在 [0.48, 0.54) 區間；所以消息的第二個符號一定是NEGATIVE。
我們再一次將當前區間劃分成子區間：
中性 的區間是 [0.48, 0.516)
陽性 的區間是 [0.516, 0.528)
陰性 的區間是 [0.528, 0.534)
數據結束符 的區間是 [0.534, 0.540).
我們的分數 .538 落在符號 END-OF-DATA 的區間；所以，這一定是下一個符號。由於它也是內部的結束符號，這也就意味著編碼已經結束。（如果數據流沒有內部結束，我們需要從其它的途徑知道數據流在何處結束——否則我們將永遠將解碼進行下去，錯誤地將不屬於實際編碼生成的數據讀進來。）
同樣的消息能夠使用同樣短的分數來編碼實現如 .534、.535、.536、.537或者是.539，這表明使用十進制而不是二進制會帶來效率的降低。這是正確的是因為三位十進制數據能夠表達的信息內容大約是9.966位；我們也能夠將同樣的信息使用二進制分數表示為.10001010（等同於0.5390625），它僅需8位。這稍稍大於信息內容本身或者消息的信息熵，大概是概率為0.6%的 7.361位信息熵。（注意最後一個0必須在二進制分數中表示，否則消息將會變得不確定起來。）
⑼ 算術編碼的編碼方法
若有一個a、b、c、d四種符號的單符號信源，待編序列為S=abda，已知：
符號a b c d
符號概率Pi 0．100 0．010 0．001 0．001
（以二進位小數表示）
累積概率∑pi 0．000 0．100 0．110 0．111
按照一定精度的數值作為序列的算術編碼，實質上是分割單位區間的過程。實現它，必須完成兩個遞推過程：一個代表碼字C（·），另一個代表區間寬度為A（·）。若記SXi表示S的增長（即S後增加一個符號Xi）序列。則有圖1 。
若記λ為空序列，有A（λ）=1，C（λ）=0，則有如圖2 。
並依次求得：C（abd）= 010111， A（abd）= 0．00001
C（abda）= 0．010111 ，A（abda）= 0．000001 該編碼過程可以用圖3所示的單位區間劃分的過程來描述。
解碼為逆遞推過程，可以通過對編碼後的數值進行比較來實現。即判斷C（S）落入哪一個區間，最後得出一個相應的符號序列S'=Ma=S。
實際的編譯碼過程比較復雜，但原理相同，算術編碼的理論性能也可使平均符號代碼長度接近符號熵，而且對二元信源的編碼實現比較簡單，故受重視。中國將它應用於報紙傳真的壓縮設備中，獲得了良好的效果。
⑽ 用C語言算術編碼的數據壓縮
哈夫曼編碼