三进制霍夫曼编码
题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。
※将霍夫曼编码推广至三进制编码
设一个数据文件包含Q个字符：A1，A2，……，Aq，每个字符出现的频度对应为P：P1，P2，……，Pq。
1.将字符按频度从大到小顺序排列，记此时的排列为排列1。
2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为
3.)
3.对排列2重复上述步骤2，直至最后剩下3个概率值。
4.从最后一个排列开始编码，根据3个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。
5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。
6.如此一直往前，直到排列1所有的频度值都被编码为止。
举例说明如下（假设Q=9）：
字符A1 A2 A3 A4 A5 A6 A7 A8 A9
频度0.22 0.18 0.15 0.13 0.10 0.07 0.07 0.05 0.03
字符频度编码频度编码频度编码频度编码A1 0.22 2 0.22 2 0.30 1 0.480 A2 0.18 00 0.18 00 0.22 2 0.30 1 A3 0.15 02 0.1501 0.18 00 0.22 2 A4 0.13 10 0.15 02 0.15 01
A5 0.10 11 0.13 10 0.15 02
A6 0.07 12 0.10 11
A7 0.07 010 0.07 12
A8 0.05 011
A9 0.03 012
频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。
构造三进制霍夫曼编码伪码程序如下：
HUFFMAN(C)
1 n ←∣C ∣
2 Q ← C
3for i ←1 to n-1
4 do allocate a new node s
5 left[s] ←x ←EXTRACT-MIN(Q)
6 middle[s] ←y ←EXTRACT-MIN(Q)
7 right[s] ←z ←EXTRACT-MIN(Q)
8 f[s] ←f[x]+f[y]+f[z]
9 INSERT(Q，z)
10 return EXTRACT-MIN(Q)
※霍夫曼编码（三进制）最优性证明
在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a，设f(a)表示a在文件中出现的频度，d T(a)表示字符a的编码长度，亦即a的叶子在树中的深度。这样，编码一个文件所需的位数就是
B(T)=∑f(a)d T(a)
设A为一给定文件，其中每个字符都定义有频度f[a]。设x，y和z是A中具有最低频度的两个字符。并设A'为文件A中移去x，y和z，再加上新的字符s后的文件，亦即A'=A-{x,y,z}∪{s}；如A一样为A'定义f，其中f[s]=f[x]+f[y]+f[z]。设T'为文件A'上最优前缀编码的任意一棵树，那么，将T'中叶子节点s换成具有x，y和z孩子的内部节点所得到的树T，表示文件A上的一个最优前缀编码。
证明：对每一个a∈A-{x,y,z}，有d T(a)=d T'(a)，故f[a]d T(a)=f[a]d T'(a)。又d T'(x)=d T'(y)=d T'(z)=d T''(s)+1，从而有：
f[x]d T'(x)+f[y]d T'(y)+f[z]d T'(z)=(f[x]+f[y]+f[z])(d T''(s)+1)=f[s]d T''(s)+(f[x]+f[y]+f[z])
由此可得：
B(T)=B(T')+f[x]+f[y]+f[z]
假设T不表示A的最优前缀编码，那么存在一棵树T''，有B(T'') B(T''')=B(T'')-f[x]-f[y]-f[z] 与之前假设的T'表示A'上的最优前缀编码矛盾，故T必定表示文件A上的最优前缀码，证毕。 构造三进制霍夫曼编码程序代码及运行结果如下： 程序源码： #include #include #include int Sorting(int *x,int n) {//排序 int *a,b,i,j,r=0; a=x; for(j=0;j { for(i=0;i { if((*(a+i+1))<=(*(a+i))) { b=*(a+i); *(a+i)=*(a+i+1); *(a+i+1)=b; if(i==r) r++; } } } return r; } char *strcatzp(char *str1,const char *str2) {//字符串拼接 //ASSERT((str1!=NULL)&&(str2!=NULL)); char *addr=(char *)malloc((strlen(str1)+strlen(str2)+1)*sizeof(char)); char *des=addr; //ASSERT(addr!=NULL); while(*str1) { *addr=*str1; str1++; addr++; } while(*str2) { *addr=*str2; str2++; addr++; } *addr='\0'; return des; } void main(void) { char character[100]={""}; char *code[100]={""}; char *temp=NULL; char InputChar; float Input_p; int p[100][100]={0}; int count=6,i,j,m,tc=0; int *k; int i_charinput=0,i_pinput=1; //数据输入 printf("请输入字符，按Enter键结束输入:\n"); InputChar = getchar(); while(InputChar!='\n')/*约定一个结束符为-1*/ { if (InputChar!=' ') { character[i_charinput++]=InputChar; } InputChar = getchar(); } printf("请输入相应字符出现的频率，按0+Enter键结束输入:\n"); scanf("%f", &Input_p); while(Input_p!=0) { p[0][i_pinput++]= (int)((Input_p* 1000.0+1)/10); scanf("%f", &Input_p); } if(i_charinput!=(i_pinput-1)) { printf("输入字符与频率个数不相等，请确认后重新输入\n"); return; } count = i_charinput; k=&p[0][1]; for(j=0;j { for(i=0;i { if((*(k+i+1))<=(*(k+i))) { m=*(k+i); *(k+i)=*(k+i+1); *(k+i+1)=m; InputChar=character[i]; character[i]=character[i+1]; character[i+1]=InputChar; } } } //for test /* for(i=1;i<10;i++) { printf("%d ",p[0][i]); } */ Sorting(&p[0][1],count); if(count%2 != 0) { tc=(count-3)/2; for(i=1;i<=tc;i++) { p[i][1]=p[i-1][1]+p[i-1][2]+p[i-1][3]; for(j=2;j { p[i][j]=p[i-1][j+2]; } p[i][0]=1+Sorting(&p[i][1],count-2*i); } code[0]="2"; code[1]="1"; code[2]="0"; for(i=tc;i>0;i--) { temp=code[p[i][0]-1]; for(j=count-2*i-1;j>=0;j--) { if(j>p[i][0]-1) code[j+2]=code[j]; else if(j code[j+3]=code[j]; } code[0]=strcatzp(temp,"2"); code[1]=strcatzp(temp,"1"); code[2]=strcatzp(temp,"0"); } printf("字符编码为:\n"); for(i=0;i { printf("%c->%s\n",character[i],code[i]); } printf("\n"); //for test /* for(i=0;i<(count-1)/2;i++) { for(j=0;j<1+count-2*i;j++) { printf("%d ",p[i][j]); } printf("\n"); } */ } else { tc=(count+2)/2; for(i=1;i<=tc;i++) { p[i][1]=p[i-1][1]+p[i-1][2]; for(j=2;j { p[i][j]=p[i-1][j+1]; } p[i][0]=1+Sorting(&p[i][1],count-i); } code[0]="2"; code[1]="1"; code[2]="0"; for(i=tc;i>0;i--) { temp=code[p[i][0]-1]; for(j=count-i-1;j>=0;j--) { if(j>p[i][0]-1) code[j+1]=code[j]; else if(j code[j+2]=code[j]; } code[0]=strcatzp(temp,"1"); code[1]=strcatzp(temp,"0"); } printf("字符编码为:\n"); for(i=0;i { printf("%c->%s\n",character[i],code[i]); } printf("\n"); //for test /* for(i=0;i { for(j=0;j { printf("%d ",p[i][j]); } printf("\n"); }*/ } } 附录二 表1. 传真用的修正霍夫曼编码表 构造码 64 11011 0000001111 960 011010100 0000001110011 128 10010 000011001000 1024 011010101 0000001110100 192 010111 000011001001 1088 011010110 0000001110101 256 0110111 000001011011 1152 011010111 0000001110110 320 00110110 000000110011 1216 011011000 0000001110111 384 00110111 000000110100 1280 011011001 0000001010010 448 01100100 000000110101 1344 011011010 0000001010011 512 01100101 0000001101100 1448 011011011 0000001010100 576 01101000 0000001101101 1472 010011000 0000001010101 640 01100111 0000001001010 1536 010011001 0000001011010 704 011001100 0000001001011 1600 010011010 0000001011011 768 011001101 0000001001100 1664 011000 0000001100100 832 011010010 0000001001101 1728 010011011 0000001100101 896 011010011 0000001110010 EOL 000000000001 000000000001 结尾码 游程长度 白游程编码 黑游程编码 游程长度白游程编码 黑游程编码 0 00110101 0000110111 32 000111011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110 7 1111 00011 39 00101000 000011010111 8 10011 000101 40 00101001 000001101100 9 10100 000100 41 00101010 000001101101 10 00111 0000100 42 00101011 000011011010 11 01000 0000101 43 00101100 000011011011 12 001000 0000111 44 00101101 000001010100 13 000011 00000100 45 00000100 000001010101 14 110100 00000111 46 00000101 000001010110 15 110101 000011000 47 00001010 000001010111 16 101010 0000010111 48 00001011 000001100100 17 101011 0000011000 49 01010010 000001100101 18 0100111 0000001000 50 01010011 000001010010 19 0001100 00001100111 51 01010100 000001010011 20 0001000 00001101000 52 01010101 000000100100 21 0010111 00001101100 53 00100100 000000110111 22 0000011 00000110111 54 00100101 000000111000 23 0000100 00000101000 55 01011000 000000100111 24 0101000 00000010111 56 01011001 000000101000 25 0101011 00000011000 57 01011010 000001011000 26 0010011 000011001010 58 01011011 000001011001 27 0100100 000011001011 59 01001010 000000101011 28 0011000 000011001100 60 01001011 000000101100 29 00000010 000011001101 61 00110010 000001011010 30 00000011 000001101000 62 00110011 000001100110 31 00011010 000001101001 63 00110100 000001100111 205 目录 一、摘要 (3) 二、题目 (3) 三、实验目的 (3) 四、实验原理 (3) 五、需求分析 (4) 5.1实验要求 (4) 5.2实验内容 (4) 六、概要设计 (4) 6.1所实现的功能函数 (4) 6.2主函数 (5) 6.3 系统结构图 (6) 七、详细设计和编码 (6) 八、运行结果 (12) 九、总结 (15) 9.1调试分析 (15) 9.2 心得体会 (15) 参考文献 (16) 一、摘要 二、题目 哈夫曼树的编码与译码 三、实验目的 （1）熟悉对哈夫曼的应用以及构造方法，熟悉对树的构造方式的应用； （2）进一步掌握哈夫曼树的含义； （3）掌握哈夫曼树的结构特征，以及各种存储结构的特点以及使用范围； （4）熟练掌握哈夫曼树的建立和哈夫曼编码方法； （5）提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法； （6）掌握一种计算机语言，可以进行数据算法的设计。 四、实验原理 哈夫曼（Huffman）编码属于长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： （1）初始化，根据富豪概率的大小按由大到小顺序对符号进行排序； （2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和； （3）重复第（2）步，直到形成一个符号为止（树），其概率最后等于1； （4）从编码树的根开始回溯到原始的符号，并将每一下分支赋值1，上分支赋值0； 译码的过程是分解电文中字符串，从根出发，按字符“0”或者“1”确定找做孩 子或右孩子，直至叶子节点，便求得该子串相应的字符。 图像压缩编码实验报告 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： （1）无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。（2）有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； （3）混合编码 JBIG，，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致 中国矿业大学2015-2016学年第二学期 《数字视频技术》课程小设计考核 图像的Huffman编码研究 专业班级：信息13-04班 学生姓名：王振宇、龙航、王一鸣 学生学号：04131407、04131403、04131406 本人郑重声明：本人认真、独立完成了查找资料、完成作业、编写程序等考核任务，无抄袭行为。 签字： 日期：2016.05.17 1.引言 1.1图像数据压缩的目的 数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。一般原始图像存在很大的冗余度。所以，对图像数据压缩显得非常重要。 1.2图像数据压缩的原理 对数字图像压缩主要运用两个基本原理：一是图像的相关性。在图像同一相邻像素之间，活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就除去或减少图像信息中的冗余度，继而实现对数字图像的压缩。二是人的视觉心理特征，人的视觉对于边缘急剧变化不敏感，对颜色分辨力弱，利用这些特征在相应部分降低编码精度而使人从视觉上感觉不到图像质量的下降，从而达到对数字图像压缩的目的。 1.3Huffman编码 Huffman编码是一种编码方式，是一种用于无损数据压缩的熵编码算法。它是Huffman 在1952年根据Shannon在1948年和Fano在1949年阐述的这种编码思想下提出的一种不定长编码的方法，有时也称之为最佳编码。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，完全依据字符出现概率来构造异字头的平均长度最短的码字。哈夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。 2.设计任务 2.1设计任务 研究实现灰度图像的Huffman编码和解码恢复。 2.2设计目的 (1)了解Huffman编码的基本原理及其特点； (2)理解并熟练对图像进行哈夫曼编码的算法； (3)学习和熟悉MA TLAB图像处理工具箱； (4)熟悉和掌握MA TLAB程序设计方法； 2.3设计要求 现灰度图像的Huffman编码和解码恢复图像；处理结果要求最终图像显示，且计算图像的信息熵，平均码字长度，编码效率，压缩比。 3.总体设计方案 3.1系统运行环境 Windows 8.1/10系统 3.2编程软件平台 MATLAB R2013a/R2014a 3.3Huffman编码算法原理 哈夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的哈夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 (1)计算信源符号出现的概率； (2)将信源符号按其出现的概率，由小到大顺序排列，并从左至右排列为叶节点[1]； 三进制霍夫曼编码 Prepared on 22 November 2020 题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据文件包含Q个字符：A1，A2，……，Aq，每个字符出现的频度对应为P：P1，P2，……，Pq。 1.将字符按频度从大到小顺序排列，记此时的排列为排列1。 2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为 3.) 3.对排列2重复上述步骤2，直至最后剩下3个概率值。 4.从最后一个排列开始编码，根据3个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。 5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。 6.如此一直往前，直到排列1所有的频度值都被编码为止。 举例说明如下（假设Q=9）： 频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。 构造三进制霍夫曼编码伪码程序如下： HUFFMAN(C) 1 n ←∣C ∣ 2 Q ← C 3 for i ← 1 to n-1 4 do allocate a new node s 5 left[s] ← x ← EXTRACT-MIN(Q) 6 middle[s] ← y ← EXTRACT-MIN(Q) 7 right[s] ← z ← EXTRACT-MIN(Q) 8 f[s] ← f[x]+f[y]+f[z] 9 INSERT(Q，z) 10 return EXTRACT-MIN(Q) ※霍夫曼编码（三进制）最优性证明 在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a，设f(a)表示a在文件中出现的频度，d T(a)表示字符a的编码长度，亦即a 的叶子在树中的深度。这样，编码一个文件所需的位数就是 B(T)=∑f(a)d T(a) 设A为一给定文件，其中每个字符都定义有频度f[a]。设x，y和z是A中具有最低频度的两个字符。并设A'为文件A中移去x，y和z，再加上新的字符s后的文件，亦即A'=A-{x,y,z}∪{s}；如A一样为A'定义f，其中f[s]=f[x]+f[y]+f[z]。设T'为文件A'上最优 #include Computer Knowledge and Technology 电脑知识 与技术第6卷第23期(2010年8月)浅析图像压缩编码方法 徐飞 （闽西职业技术学院，福建龙岩364021） 摘要：该文描述了图像压缩编码的概念，原理以及主要分类，介绍了目前常见的三种图像压缩编码方法的原理，特点以及简单讨论了其中两种方法的MATLAB 代码实现。 关键词：图像压缩编码；编码原理；编码分类；编码方法；MATLAB 中图分类号：TP301文献标识码：A 文章编号：1009-3044(2010)23-6584-03 Analysis of the Image Compression Coding Method XU Fei (Minxi Vocational &Technical College,Longyan 364021,China) Abstract:This paper is mainly about the concept,principle and classification of image compression coding,introduces the concepts and characteristic of three kinds of image compression coding methods that are common used,and discusses how to using matlab to accomplish the two common methods which mentions in the front. Key words:image compression coding;coding principle;coding classification;coding method;MATLAB 现代社会是信息社会，随着信息技术的发展，图像信息被广泛应用于多媒体通信、计算机系统和网络中。因为对图像的要求越来越高，图像信息量也越来越大，所以在传输之前需要进行信息处理，必须采用合适的方法对其进行压缩，因此有必要对图像压缩编码方法进行研究。 1图像压缩编码 1.1概述 图像压缩编码就是在满足一定保真度和图像质量的前提下，对图像数据进行变换、编码和压缩，去除多余的数据以减少表示数字图像时需要的数据量，便于图像的存储和传输。即以较少的数据量有损或无损地表示原来的像素矩阵的技术,也称图像编码。 1.2图像压缩编码原理 图像数据的压缩机理来自两个方面:一是利用图像中存在大量冗余度可供压缩；二是利用人眼的视觉特性。 1.2.1图像数据的冗余度 1)空间冗余： 在一幅图像中规则的物体和规则的背景具有很强的相关性。 2)时间冗余：电视图像序列中相邻两幅图像之间有较大的相关性。 3)结构冗余和知识冗余： 图像从大面积上看常存在有纹理结构，称之为结构冗余。 4)视觉冗余：人眼的视觉系统对于图像的感知是非均匀和非线性的，对图像的变化并不都能察觉出来。 1.2.2人眼的视觉特性 1)亮度辨别阈值：当景物的亮度在背景亮度基础上增加很少时，人眼是辨别不出的，只有当亮度增加到某一数值时，人眼才能感觉其亮度有变化。人眼刚刚能察觉的亮度变化值称为亮度辨别阈值。 2)视觉阈值：视觉阈值是指干扰或失真刚好可以被察觉的门限值，低于它就察觉不出来，高于它才看得出来，这是一个统计值。3)空间分辨力：空间分辨力是指对一幅图像相邻像素的灰度和细节的分辨力，视觉对于不同图像内容的分辨力不同。 4)掩盖效应：“掩盖效应”是指人眼对图像中量化误差的敏感程度，与图像信号变化的剧烈程度有关。 1.3图像压缩编码的分类 根据编码过程中是否存在信息损耗可将图像编码分为: 1)无损压缩:又称为可逆编码(Reversible Coding)，解压缩时可完全回复原始数据而不引起任何失真； 2)有损压缩:又称不可逆压缩(Non-Reversible Coding)，不能完全恢复原始数据，一定的失真换来可观的压缩比。 根据编码原理可以将图像编码分为: 1)熵编码：熵编码是编码过程中按熵原理不丢失任何信息的编码。熵编码基本原理是给出现概率大的信息符号赋予短码字，出收稿日期：2010-06-10 作者简介；徐飞（1982-），男，福建龙岩人，闽西职业技术学院，助教，理学学士，主要研究方向为数字图象，软件开发，软件测试。ISSN 1009-3044Computer Knowledge and Technology 电脑知识与技术Vol.6,No.23,August 2010,pp.6584-6586,6589E-mail:eduf@https://www.wendangku.net/doc/3a8851193.html, https://www.wendangku.net/doc/3a8851193.html, Tel:+86-551-56909635690964 霍夫曼编码 霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。1952年，David A. Huffman在麻省理工攻读博士时所提出一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 该方法完全依据字符出现概率来构造异字头的平均长度最短的 码字，有时称之为最佳编码，一般就叫作Huffman编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他 在MIT信息论的同学需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 霍夫曼（Huffman）编码是一种统计编码。属于无损（lossless）压缩编码。 以霍夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 ←根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次数越 多，其编码的位数就越少。 ←广泛用在JPEG, MPEG, H.2X等各种信息编码标准中。霍夫曼编码的步骤 霍夫曼编码的具体步骤如下： １）将信源符号的概率按减小的顺序排队。 ２）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率１。 3）将每对组合的上边一个指定为1，下边一个指定为0（或相反）。４）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。 信源熵的定义： 概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵(entropy)，记为： 例：现有一个由5个不同符号组成的30个符号的字 符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 哈夫曼树描述文档 一、思路 通过一个argv[]数组存储从test文件中读取字母，然后利用ascal 码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。 二、截图 三、代码 #include intrchild; }HTNode; typedefstruct { char cd[50]; int start; }HCode; using namespace std; int enter(char argv[])//进行读入操作 { fstream in; ofstream out; char c; int number=0;//字母个数置为0 in.open("test.txt",ios::in); //打开文件test.txt out.open ("code.txt",ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空 if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c printf("原文本是:\n"); while(! in.eof()){ //文件不为空，循环读取一个字符 cout< clear X=imread('lena512.bmp'); data=uint8(X); [zipped,info]=huffencode(data); %调用Huffman编码程序进行压缩 unzipped=huffdecode(zipped,info,data); %调用Huffman编码程序进行解码 %显示原始图像和经编码后的图像，显示压缩比，并计算均方根误差得erms=0，表示是Huffman是无失真编码 subplot(121);imshow(data); subplot(122);imshow(unzipped); %erms=compare(data(:),unzipped(:)) cr=info.ratio whos data unzipped zipped function [zipped, info] = huffencode(vector) % 输入和输出都是uint8 格式 % info 返回解码需要的结构信息 % info.pad 是添加的比特数 % info.huffcodes 是Huffman 码字 % info.rows 是原始图像行数 % info.cols 是原始图像列数 % info.length 是原始图像数据长度 % info.maxcodelen 是最大码长 if ~isa(vector, 'uint8') error('input argument must be a uint8 vector'); end [m, n] = size(vector); vector = vector(:)'; f = frequency(vector); %计算各符号出现的概率 symbols = find(f~=0); f = f(symbols); [f, sortindex] = sort(f); %将符号按照出现的概率大小排列 symbols = symbols(sortindex); len = length(symbols); symbols_index = num2cell(1:len); codeword_tmp = cell(len, 1); % 生成Huffman 树，得到码字编码表 while length(f)>1 index1 = symbols_index{1}; index2 = symbols_index{2}; codeword_tmp(index1) = addnode(codeword_tmp(index1), uint8(0)); codeword_tmp(index2) = addnode(codeword_tmp(index2), uint8(1)); #include"stdafx.h" #include"stdio.h" #include"conio.h" #include 视频压缩编码及常用格式 数据压缩编码已经拥有很长的历史，压缩编码的理论基础是信息论。从信息的角度看，压缩就是去除数据中的消除冗余。即保留不确定的信息，去除确定的信息，用一种更接近信息本质的描述来代替原有冗余的描述压缩的目的是在尽可能保证视觉效果的前题下减少数据率。视频压缩比是指压缩后的数据量与压缩前的数据量之比。由于视频是连续的静态图像，因此其压缩编码算法与静态图像的压缩算法有某些共同的地方，但是运动的视频还有其本身的特性，因此在压缩是还要考虑其运动特性，这样才能达到高效果压缩的目的。 自从上世纪四十年代第一台电视机问世以来，视频技术的研究与应用已经有近六十年的历史。当前电视技术均为模拟视频技术，经过几十年的发展和完善，已经十分成熟。世界通行的模拟电视制式主要有：PAL（欧洲、中国）NTSC（北美、日本）和SECAM（法国）。 随着计算机技术近二十年的发展，特别是九十年代以来互联网的广泛应用，多媒体数字视频技术已经成为了当前信息科学中十分活跃的研究方向。数字化技术的引用。使得对视频信号的捕获、处理、压缩和储存都有了革命性的进步特别是在视频数据的压缩和储存上。国际电信联合会（ITC）于1990年正式提出了ITU-TH261建议，这是第一个关于使用化视频图像压缩编码的国际标准提议。九十年代中，IUT在该建议上提出了MPEG1、MPEG2、MPEG4、H.263和JPEG2000等压缩标准。这些标准的制定和颁布，极大的促进了数字视频压缩与编码技术的研究和实用化。 视频编码标准的发展 视频编码技术在近年得到了迅速的发展和广泛的应用，并在日渐成熟，起标准是多个视频编码国际化标准的制定与应用，即国际标准化组织ISO和国际电工委员会IEC关于静态图像的编码标准JPEG、国际电信联盟ITU-T关于电视、电话会议的视频编码标准H261、H.263及H.264和ISO/TEC关于活动图像的编码标准MPEG-1,MPEG-2、MPEG-4等。这些标准图像编码算法融合了各种性能优良的图像编码方法，代表了目前编码的发张水平。 MPEG-1 MPEG-1标准于1993年8月公布，用于传输1.5Mbps数据传输的数据储存媒体运动图像及其伴音的编码。该标准包括五个部分：第一：说明如何根据第二部（视频）以及第三部分（音频）的规定，对音频和视频进行复合编码。第四部分说明检验解码器或编码器的输出比流符合前三部分规定的过程。第五部分是一个用完整的C语言实现的编码和解码器。 MPEG-1取得一连串的成功，如VCD和MP3的大量使用，可携式MPEG-1摄像 实验四哈夫曼树与哈夫曼编码 一、实验内容 [问题描述] 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求] 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。 对给定的待编码字符序列进行编码。 二、概要设计 算法设计： 要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。 流程图： 算法： 模块： 在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下： 首先建立一个哈夫曼树和哈夫曼编码的存储表示： typedef struct { int weight; int parent,lchild,rchild; char elem; }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。 构造哈夫曼树： for(i=n+1;i<=m;++i) {//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2); AE 编码压缩方案 AVI用的最多 AVI为后缀的视频文件，其采用的压缩算法可能不同，需要相应的解压软件才能识别和回放该AVI文件。各种编码生成的AVI文件的大小和质量是不同的，对系统和硬件要求也不同。 常见的视频编码 1、Cinepak Codec by Radius 它最初发布的时候是用在386的电脑上看小电影，在高数据压缩率下，有很高的播放速度。利用这种压缩方案可以取得较高的压缩比和较快的回放速度，但是它的压缩时间相对较长。 2、Microsoft Video 1 用于对模拟视频进行压缩，是一种有损压缩方案，最高仅达到256色，它的品质就可想而知，一般还是不要使用它来编码AVI。 3、Microsoft RLE 一种8位的编码方式，只能支持到256色。压缩动画或者是计算机合成的图像等具 大面积色块的素材可以使用它来编码，是一种无损压缩方案。 4、Microsoft H.261和H.263 Video Codec 用于视频会议的Codec，其中H.261适用于ISDN、DDN线路，H.263适用于局域网，不过一般机器上这种Codec是用来播放的，不能用于编码。 5、Intel Indeo Video R3.2 所有的Windows版本都能用Indeo video 3.2播放AVI编码。它压缩率比Cinepak大， 但需要回放的计算机要比Cinepak的快。 6、Intel Indeo Video 4和5 常见的有4.5和5.10两种，质量比Cinepak和R3.2要好，可以适应不同带宽的网络，但必须有相应的解码插件才能顺利地将下载作品进行播放(一般在Windows里已经有了)。适用于装了Intel 公司MMX以上CPU的机器(多数奔腾的机器也差不多该进垃圾堆了吧)，回放效果优秀。如果一定要用AVI的话，推荐使用5.10，在效果几乎一样的情况下，它有更快的编码速度和更高的压缩比。 7、Intel IYUV Codec 使用该方法所得图像质量极好，因为此方式是将普通的RGB色彩模式变为更加紧凑的YUV色彩模式。如果你想将AVI压缩成MPEG-1的话，用它得到的效果比较理想，只是它的块头太大了(恐怕你得考虑一下磁盘空间了)。 8、Microsoft MPEG-4 Video codec --------------------------可以编辑的精品文档，你值得拥有，下载后想怎么改就怎么改--------------------------- 实验四图像压缩 姓名：学号：邮箱： 一、实验目的 1.掌握DCT变换的原理 2.了解DCT变化在图像压缩中的应用 3.掌握图像压缩的基本原理及方法 4.了解霍夫曼编码原理 5.熟悉图像压缩的MATLAB编程 二、实验原理 DCT是目前比较好的图像变换，它有很多优点。DCT是正交变换，它可以将8x8图像空间表达式转换为频率域，只需要用少量的数据点表示图像；DCT产生的系数很容易被量化，因此能获得好的块压缩；DCT算法的性能很好，它有快速算法，如采用快速傅立叶变换可以进行高效的运算，因此它在硬件和软件中都容易实现；而且DCT算法是对称的，所以利用逆DCT算法可以用来解压缩图像。 由于DCT主要应用在数据和图像的压缩，因此希望原信号的能量在变换后能尽量集中在少数系数上，且这些大能量的系数能处在相对集中的位置，这将有利于进一步的量化和编码。但是如果对整段的数据或整幅图像来做DCT，那就很难保证大能量的系数能处在相对集中的位置。因此，在实际应用中，一般都是将数据分成一段一段来做，一般分成8x8或16x16的方块来做。 二维DCT正交变换的公式为： 二维DCT逆变换公式： 其中 三、实验要求 利用DCT变换对图像进行压缩，对比不同压缩比下的结果，对比不同压缩比下图像大小的变化。压缩过程如下图所示： 四、实验过程与结果 实验程序如下：（先给出主程序，然后给出各功能子函数的程序） 主程序： clear load('')%调入170*170大小的一幅彩色lena图像 l=imresize(lena,[256 256]);%将图像变换为8的整数倍大小 X=rgb2gray(l); Y1=double(X);%读入图像数据lianghua=[16 11 10 16 24 40 51 61;%量化矩阵，量化的程度序决定压缩比 12 12 14 19 26 58 60 55; 14 13 16 24 40 57 69 56; 14 17 22 29 51 87 80 62; 18 22 37 56 68 109 103 77; DCT变换 量化huffman编码 哈夫曼树编码 #include } if (j==t->total) { t->arr[t->total].ch = text[i]; t->arr[t->total].weight = 1; t->total ++; } } printf("char frequence\n"); for (i=0; i 图像压缩编码的方法概述摘要：在图像压缩的领域，存在各种各样的压缩方法。不 同的压缩编码方法在压缩比、压缩速度等方面各不相同。本文从压缩方法分类、压缩原理等方面分析了人工神经网络压缩、正交变换等压缩编码方法的实现与效果。 关键词：图像压缩；编码；方法 图像压缩编码一般可以大致分为三个步骤。输入的原始图像首先需要经过映射变换，之后还需经过量化器以及熵编码器的处理最终成为码流输出。 一、图像压缩方法的分类 1.按照原始信息和压缩解码后的信息的相近程度分为以下两类：（1）无失真编码又称无损编码。它要求经过编解码处理后恢复出的图像和原图完全一样，编码过程不丢失任何信息。如果对已量化的信号进行编码，必须注意到量化所产生的失真是不可逆的。所以我们这里所说的无失真是对已量化的信号而言的。特点在于信息无失真，但压缩比有限。（2）限失真编码中会损失部分信息，但此种方法以忽略人的视觉不敏感的次要信息的方法来得到高的压缩比。图像的失真怎么度量，至今没有一个很好的评判标准。在由人眼主观判读的情况下，唯有人眼是对图像质量的最有利评判者。但是人眼视觉机理到现在为止仍为被完全掌握，所以我们很难得到一个和主观评价十分相符的客观标准。目前用的最多的仍是均方误差。这个失真度量标准并不好，之所以广泛应用，是因为方便。 2.按照图像压缩的方法原理可分为以下三类：（1）在图像编码过程中映射变换模块所做的工作是对编码图像进行预测，之后将预测差输出供量化编码，而在接受端将量化的预测差与预测值相加以恢复原图，则这种编码方法称为预测编码。预测编码中，我们只对新的信息进行编码。并且是利用去除邻近像素之间的相关性和冗余性的方法来达到压缩的目的。（2）若压缩编码中的映射变换模块用某种形式的正交变换来代替，则我们把这种方式的编码方法称为变换编码。在变换编码中常用的变换方法有很多，我们主要用到的有离散余弦变换（DCT），离散傅立叶变换（DFT）和离散小波变换（DWT）等。（3）混合编码，LZW算法以及近些年来的一些新的压缩编码方法，最主要的有分形编码算法、小波变换压缩算法、基于模型的压缩算法等。 3.按照压缩对象来分，我们可将图像压缩方法分为静止图像压缩和运动图像压缩。它们所采用的压缩编码标准有所不同，对于静止图像压缩而言，采用的是JPEG、JPEG2000标准；而对运动的图像进行压缩时，我们则采用的是、、、MPEG-1、MPEG-2、MPEG-4、MPEG-7等。 二、常用的图像压缩方法 图像压缩方法至研究开始至今，已经有将近70年的发展了，随着科技的不断发展和人们越来越高的期望和要求，使得图像压缩技术也在不断的发展着，不断的进步着，各种各样的方法层出不穷，争对不同的要求我们可以选择不同的方法对图像进行压缩，以达到霍夫曼编码表
哈夫曼树的编码与译码
图像压缩编码实验报告
基于MATLAB的图像Huffman编码研究.docx
三进制霍夫曼编码
实验六 哈夫曼树及哈夫曼编码
浅析图像压缩编码方法
霍夫曼编码
构建哈夫曼树及输出哈夫曼代码及算法思想
霍夫曼图像压缩编码源程序
哈夫曼树的编码和译码
视频压缩编码及常用格式
实验四 哈夫曼树与哈夫曼编码
AE的编码压缩方法
实验四dct变换huffman编码图像压缩
哈夫曼树编码
图像压缩编码的方法概述
- 基于灰度图像的霍夫曼编解码技术 161120058 陈琪
- 霍夫曼图像压缩编码源程序
- 图像压缩编码
- 基于哈夫曼编码的图像压缩技术研究
- 数字图像处理 第六章图像压缩与编码
- 数据压缩霍夫曼编码算术编码
- 图像压缩编码实验报告
- 第十一章图像的压缩编码
- JPEG图像编码标准-共86页文档
- 用matlab仿真huffman编码在jpg图像压缩中的应用 崔微微(推荐文档)
- 图像压缩编码实验报告
- 图像的无损压缩程序设计 霍夫曼编码
- 图像霍夫曼编码与解码以及熵,平均码长,冗余度的计算
- 图像霍夫曼编码与解码以及熵-平均码长-冗余度的计算
- 图像编码-霍夫曼编码
- 实验四dct变换huffman编码图像压缩
- 用Huffman编码实现图像压缩
- 图像无损压缩程序设计 霍夫曼编码
- 医学图像处理 第六章 图像压缩编码
- 基于MATLAB的图像Huffman编码研究.docx