算术编码压缩
⑴ 算术编码的相关介绍
上面对算术编码的解释进行了一些简化。尤其是，这种写法看起来好像算术编码首先使用无限精度精度的数值计算总体上表示最后节点的分数，然后在编码结束的时候将这个分数转换成最终的形式。许多算术编码器使用优先精度的数值计算，而不是尽量去模拟无限精度，因为它们知道解码器能够匹配、并且将所计算的分数在那个精度四舍五入到对应值。一个例子能够说明一个模型要将间隔[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语言算术编码的数据压缩
哈夫曼编码