下载文档原格式
算术编码+ 统计模型= 数据压缩- 第一部分：算术编码作者：Mark Nelson现在通用的大多数数据压缩方法都属于两大阵营之一：基于字典的方案和统计方法。
在小系统世界中，基于字典的数据压缩技术此时似乎更加流行。
不过，通过将算术编码与强大的模型技术结合在一起，数据压缩的统计方法可以真正达到更好的性能。
这篇分成两部分的文章讨论了如何用几个不同的模型方法与算术编码组合以达到一些重大的压缩率。
本文的第一部分详细说明算术编码是如何工作的。
第二部分说明如何开发一些可以使用算术编码的有效模型以生成高性能压缩程序。
钟爱的术语数据压缩通常通过从输入“文本”获取“符号”、处理它们，并将“代码”写入到压缩后的文件来进行运作。
对于本文来说，符号通常是字节，但是他们很可能只是像素、80 位的浮点数或者EBCDIC 字符。
数据压缩方案需要能够将已压缩的文件转换回到与输入文本的一样的拷贝才是有效的。
如果已压缩的文件比输入文本更小，那么不必说，它也是有用的。
基于字典的压缩系统通过用固定长度码来代替输入文本中的一组符号来进行运作。
字典技术的一个众所周知的例子是LZW 数据压缩。
（请参见DDJ 的89 年第10 期中的“LZW 数据压缩”一文）。
LZW 通过通常从9 到16 位大小范围的码来取代本来无限长的字符串来进行运作。
数据压缩的统计方法采取一种完全不同的方法。
它们通过一次编码多个符号来运作。
将符号编码到可变长的输出码中。
输出码的长度根据符号的概率或者频率进行变化。
低概率的符号用较多的位进行编码，并且高概率符号用较少的位进行编码。
实践中，统计和字典方法之间的分界线并不总是那么清晰。
一些方案并不能明显地归为某一个阵营或者另一个，并且总是有一些使用来自两种技术特性的混合方案。
不过，在本文中讨论的方法使用算术编码来实现纯粹的统计压缩方案。
霍夫曼（Huffman）编码：退役的冠军在数据流中只是能够精确地计算字符的概率还不够，我们也需要能有效地利用这个知识的编码方法。
算术编码工作原理在给定符号集和符号的情形下，算术编码能够给出接近最优的编码结果。
利用算术编码的紧缩算法通常先要对输入符号的概率进行估量，然后再编码。
那个估量越准，编码结果就越接近最优的结果。
例: 对一个简单的信号源进行观看，取得的模型如下：60% 的机遇显现符号中性20% 的机遇显现符号阳性10% 的机遇显现符号阴性10% 的机遇显现符号数据终止符. (显现那个符号的意思是该信号源'内部中止'，在进行数据紧缩时如此的情形是很常见的。
当第一次也是唯一的一次看到那个符号时，解码器就明白整个信号流都被解码完成了。
)算术编码能够处置的例子不止是这种只有四种符号的情形，更复杂的情形也能够处置，包括高阶的情形。
所谓高阶的情形是指当前符号显现的概率受之前显现符号的阻碍，这时之前显现的符号，也被称为上下文。
比如在英文文档编码的时候，例如，在字母Q 或q显现以后，字母u显现的概率就大大提高了。
这种模型还能够进行自适应的转变，即在某种上下文下显现的的估量随着每次这种上下文显现时的符号而自适应更新，从而加倍符合实际的概率散布。
不管编码器利用如何的模型，解码器也必需利用一样的模型。
一个简单的例子以下用一个符号串行如何被编码来作一个例子：假设有一个以A、B、C三个显现机遇均等的符号组成的串行。
假设以简单的分组编码会十分浪费地用2 bits 来表示一个符号：其中一个符号是能够不用传的(下面能够见到符号B正是如此)。
为此，那个串行能够三进制的0和2之间的有理数表示，而且每位数表示一个符号。
例如，“ABBCAB”那个串行能够变成(base3)(即0为A, 1为B, 2为C)。
用一个定点二进制数字去对那个数编码使之在恢复符号表示时有足够的精度，譬如(base2) –只用了9个bit，比起简单的分组编码少(1 –9/12)x100% = 25%。
这关于长串行是可行的因为有高效的、适当的算法去精准地转换任意进制的数字。
![[讲义] Huffman编码与lzw编码扩展](https://img.taocdn.com/s1/m/2835c64cf7ec4afe04a1dff7.png)
python算术编码算术编码是一种常用的数据压缩算法，其主要原理是将数据转化为一个数值范围内的小数，然后将其储存下来。
在数据解压时，根据压缩时使用的转化方法，就能将原始数据准确地还原出来。
算术编码在实际应用中已经被广泛地运用在文件压缩、图像压缩和语音压缩等方面。
本文将从算术编码的原理、实现方式以及应用场景三个层面进行详细介绍。
一、算术编码的原理算术编码的原理是将一个字符串转化为一个小数，该小数对应的是一个数值范围内的一段连续区间。
这个小数的值越接近1，表示原始字符串中的内容就越靠近该区间的顶端，而值越接近0，表示原始字符串的内容越靠近该区间的底端。
在解码时，将该小数从第一位开始与不同的区间进行匹配，就能够还原出原始的字符串。
二、算术编码的实现方式算术编码是一种非常灵活的编码方式，因此在实现方式上也存在多种不同的方法。
其中一种常见的实现方法是基于概率模型的顺序算术编码。
它的具体流程如下：1. 对于每一个字符，统计其在原始字符串中出现的概率。
2. 将每一个字符的概率映射到数值范围内的一个小数区间。
3. 依次将每个字符的小数区间叠加起来，形成一个新的数值范围。
4. 当一个字符对应的小数区间完全包含在新的数值范围内时，就将新的数值范围作为编码结果储存。
5. 重复步骤4，直到所有字符都被编码。
6. 解码时，根据编码结果以及字符串中每个字符对应的概率，重新定位原始字符串中的每个字符。
三、算术编码的应用场景算术编码在实际的应用场景中已经被广泛地使用，其主要优点是可以实现更高的压缩比，以及更加精确的拟合，从而能够表现出更好的压缩效果。
在文件压缩方面，算术编码可以实现更好的压缩效果，并且不需要占用太多的存储空间。
在图像压缩方面，算术编码能够准确地描述图像的数据内容，从而实现更好的压缩效果。
在语音压缩方面，算术编码的灵活性和高效性使其成为了一种不可替代的压缩方式。
总之，算术编码作为一种常用的数据压缩算法，其原理清晰、实现方式多样，并且拥有广泛的应用场景。
算术编码的原理算术编码是一种数据压缩算法，它可以将一个长字符串压缩成一个更短的数值。
它与其他数据压缩算法不同，它不是将整个字符串划分成固定长度的块，而是将每个字符映射为一个数字，再将这些数字压缩成一个数值。
算术编码的原理可以简单地概括为以下几点：1. 确定字符集在压缩之前，必须先确定字符集。
字符集包括所有可能出现的字符。
例如，在英语中，字符集包括所有字母、数字以及其他符号。
2. 计算每个字符的概率通过预处理或对大量数据的统计，可以计算每个字符在字符串中出现的概率。
3. 对每个字符进行编码编码的过程是将每个字符映射为一个数字。
这个数字必须能唯一地表示每个字符，并且尽可能不会出现冲突。
编码的方式可以根据具体情况进行选择，例如 ASCII 码就是一种常见的字符编码方式。
4. 计算每个字符的编码区间每个字符根据其在字符串中出现的概率，可以确定一个编码区间。
例如，一个字符在字符串中出现的概率为 0.25，则其编码区间为 0-0.25。
5. 压缩数据将每个字符的编码区间连续地组成一个区间，最终压缩成一个数值。
如果字符集很大，压缩后得到的数值可能非常大，因此需要使用高精度运算来处理。
6. 解压数据解压数据的过程就是将压缩后的数值还原为原始字符串的过程。
解压的过程需要根据先前编码的字符集和编码区间进行计算，从而还原字符串。
总之，算术编码的原理可以简单概括为确定字符集、计算每个字符的概率、为每个字符编码、计算每个字符的编码区间、压缩数据和解压数据。
虽然算术编码的实现比较复杂，但它可以很好地压缩数据，并且是一种通用的数据压缩算法。
算术编码原理算术编码是一种将字符序列压缩成一个浮点数的方法，它的压缩效率比传统的哈夫曼编码更高，因为它可以使用原本不是整数的浮点数表示更多的信息。
本文将介绍算术编码的原理，分为以下几个部分：一、概念解释1.1 算术编码的基本概念算术编码是在一个有限长度的区间内对字符序列进行编码的方式，其中每个字符对应的编码值是一个实数。
编码值在编码区间内是唯一的，且编码值可以通过解码得到压缩前的字符序列。
1.2 字符频率在进行算术编码时，需要知道每个字符在字符序列中出现的频率，频率可以是小数或整数，且每个字符的频率之和必须为1。
二、算法过程2.1 编码过程算术编码主要分为以下几个步骤：（1）定义初始编码区间根据字符频率，可以计算出每个字符的编码区间，例如字符A的编码区间是[0,0.3)，字符B的编码区间是[0.3,0.5)，字符C的编码区间是[0.5,0.6)，字符D的编码区间是[0.6,1]。
（2）收缩编码区间根据每个字符的频率，计算每次的编码区间长度。
例如，如果字符序列是ABCD，且字符频率分别为0.3、0.2、0.1和0.4，那么初始编码区间的长度为1，第一次收缩后，区间缩小到0.3，表示字符A出现的概率为0.3。
第二次收缩后，区间缩小到0.06，表示字符AB出现的概率为0.06。
一直推进到最后，得到压缩后的编码值。
2.2 解码过程解码过程需要使用压缩后的编码值和字符频率进行计算。
例如，解码一个值为0.2的字符时，需要找到0.2所在的字符区间，然后计算该区间对应的字符。
三、算法特点3.1 压缩率高由于算术编码可以对每个字符对应的区间进行无限分割，因此可以表示更多的信息。
相比于传统的哈夫曼编码，算术编码可以达到更高的压缩率。
3.2 复杂度高虽然算术编码的压缩效果好，但是编码和解码的计算复杂度非常高，因此需要配合分治法、搜索算法等其它算法来减少计算量。
3.3 广泛应用算术编码在数据压缩、无损图像压缩、音频压缩、视频压缩等多个领域都有广泛应用。
1.判定唯一可译码2.LZw 编码3.算数编码一 判定唯一可译码1．任务说明输入：任意的一个码(即已知码字个数及每个具体的码字)输出：判决结果（是/不是）输入文件:in1.txt ，含至少2组码，每组的结尾为”$”符输出文件:out1.txt ，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串2．问题分析、实现原理、流程图参考算法伪代码：For all ,i j W W C ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合0F 中End ifEnd forLoopFor all i W C ∈ doFor all j n W F ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中Else if j W 是i W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中End ifEnd forEnd fori i F F ←If ,i i W F W C ∃∈∈ thenReturn falseElse if F 中未出现新的元素 thenReturn trueEnd if//能走到这里，说明F 中有新的元素出现，需继续End loop3．实现源码#include <iostream>#include <string>using namespace std;struct strings{char *string;struct strings *next;};struct strings Fstr, *Fh, *FP;//输出当前集合void outputstr(strings *str){do{cout<<str->string<<endl;str = str->next;}while(str);cout<<endl;}inline int MIN(int a, int b){ return a>b?b:a; }inline int MAX(int a, int b){ return a>b?a:b; }#define length_a (strlen(CP))#define length_b (strlen(tempPtr))//判断一个码是否在一个码集合中，在则返回0，不在返回1int comparing(strings *st_string,char *code){while(st_string->next){st_string=st_string->next;if(!strcmp(st_string->string,code))return 0;}return 1;}//判断两个码字是否一个是另一个的前缀，如果是则生成后缀码void houzhui(char *CP,char *tempPtr){if (!strcmp(CP,tempPtr)){cout<<"集合C和集合F中有相同码字:"<<endl<<CP<<endl<<"不是唯一可译码码组!"<<endl;exit(1);}if (!strncmp(CP, tempPtr, MIN(length_a,length_b))){struct strings *cp_temp;cp_temp=new (struct strings);cp_temp->next=NULL;cp_temp->string=new char[abs(length_a-length_b)+1];char *longstr;longstr=(length_a>length_b ? CP : tempPtr);//将长度长的码赋给longstr //取出后缀for (int k=MIN(length_a,length_b); k<MAX(length_a,length_b); k++) cp_temp->string[k - MIN(length_a,length_b)]=longstr[k];cp_temp->string[abs(length_a-length_b)]=NULL;//判断新生成的后缀码是否已在集合F里，不在则加入F集合if(comparing(Fh,cp_temp->string)){FP->next=cp_temp;FP=FP->next;}}}void main(){//功能提示和程序初始化准备cout<<"\t\t唯一可译码的判断!\n"<<endl;struct strings Cstr,*Ch, *CP,*tempPtr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;char c[]="C :";Ch->string=new char[strlen(c)];strcpy(Ch->string, c);Ch->next=NULL;char f[]="F :";Fh->string=new char[strlen(f)];strcpy(Fh->string, f);Fh->next=NULL;//输入待检测码的个数int Cnum;cout<<"输入待检测码的个数:";cin>>Cnum;cout<<"输入待检测码"<<endl;for(int i=0; i<Cnum; i++){cout<<i+1<<" ：";char tempstr[10];cin>>tempstr;CP->next=new (struct strings);CP=CP->next;CP->string=new char[strlen(tempstr)] ;strcpy(CP->string, tempstr);CP->next = NULL;}outputstr(Ch);CP=Ch;while(CP->next->next){CP=CP->next;tempPtr=CP;do{tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);}while(tempPtr->next);}outputstr(Fh);struct strings *Fbegin,*Fend;Fend=Fh;while(1){if(Fend == FP){cout<<"是唯一可译码码组!"<<endl;exit(1);}Fbegin=Fend;Fend=FP;CP=Ch;while(CP->next){CP=CP->next;tempPtr=Fbegin;for(;;){tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);if(tempPtr == Fend)break;}}outputstr(Fh);//输出F集合中全部元素}}4.运行结果：输入、输出及结果分析5．设计体会通过对判定唯一可译码算法的实现，我进一步了解判定唯一可译码缩的基本原理及过，体会到了其重要性,同时也锻炼了我独立分析问题以及解决问题的能力,这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。
