霍夫曼编码简介
霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉20%~90%。这里考虑的数据指的是字符串序列。要理解霍夫曼编码，先要理解霍夫曼树，即最优二叉树，是一类带权路径长度最短的树。
霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
路径是指从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。
树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和.
霍夫曼树是指所有叶子结点的二叉树中带权路径长度最小的二叉树.
当给定了n个叶子结点的权值后，构造出的最优二叉树的结点数目m就确定了，即m=2n-1,所以可用一维结构树组来存储最优二叉树
霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
以下这个简单例子说明了这一过程。
1)．字母A,B,C,D,E已被编码，相应的出现概率如下： p(A)=0.16,
p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11
2)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE 的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的霍夫曼编码可能由相同的数据产生。
3)．各节点相应的概率如下：p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13 D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。
4)．剩下节点的概率如下： p(AD)=0.29, p(B)=0.51, p(CE)=0.20 AD和CE
两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。
5)．剩下两个节点相应的概率如下： p(ADCE)=0.49, p(B)=0.51 它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE 的一边记为0。 6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中：w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010
在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。
另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。
应用霍夫曼编码
假设有一个包含100 000个字符的数据文件要压缩存储。各字符在该文
一个字符编码问题。大小为100 000个字符的一个数据文件仅包含字符a~f，每个字符出现的频度如表中所示。如果对每个字符赋予一个三位的编码，则该文件可被编码为300000位。如果利用表中的可变长度编码，该文件可被编码为224000位。
可以用很多种方式来表示这样一个文件。采用固定长度编码，则需要三位二进制数字来表示六个字符：a=000，b=001，…，f=101。这种方法需要300 000
来对整个原文件编码。
而可变长度编码是对频度高的字符赋以短编码，而对频度低的字符赋以较长一些的编码。表1显示了这种编码，其中一位串0表示a，四位串1100表示f。这种编码方式需要
（45*1+13*3+12*3+16*3+9*4+5*4）*1000 = 224 000 位
来表示整个文件，即可压缩掉约25%。这其实就是最优字符编码（霍夫曼编码）
前缀编码
我们这里考虑的编码方案中，没有一个编码是另一个编码的前缀。这样的编码称为前缀编码（或许“无前缀编码“是个更好的名字，但是前缀编码是标准的书面语）。
对任何一种二进制字符编码来说编码总是简单的，这只要将文件中表示每个字符的编码并置起来即可。利用表1的可变长度编码，把包含三个字符的文件abc编成
0 . 101 . 100 = 0 101 100,其中“.“表示并置。
在前缀编码中解码也是很方便的。因为没有一个码是其他码的前缀，故被编码文件的开始处的编码是确定的。我们只要识别出第一个编码，将它翻译成原文字符，再对余下的编码文件重复这个解码过程即可。在我们的例子中，可将串001 011 101唯一地分析为0.0.101.1101，因此可解码为aabe。
解码过程需要有一种关于前缀编码的方便表示，使得初始编码可以很容易地被识别出来。有一种表示方法就是叶子为给定字符的二叉树。在这种树中，我们将一个字符的编码解释为从根至该字符的路径，其中0表示“转向左子结点”，1表示“转向右子结点“。
这里需要注意的一点是，我们的Huffman对各个字符的编码是不会冲突的，也就是说，不会存在某一个编码是另一个编码的前缀，不然的话就会大问题了。因为encode后的编码是没有分隔符的。
解码
编码的结果就是使每一个字符的编码都与另一个字符编码的前一部分不同.不可能出现像a:00,b:001这种情况.这样就不会遇到莫棱两可的情况了. 这是由二叉树的特点决定的,编码是由从根节点到一个叶子的路径决定的.不同的叶子对应的这种路径不可能出现像a:00,b:001这种情况.可以通过画二叉树的方式，来解答霍夫曼编码的解码。并且通过这种方式十分好懂。
霍夫曼编码重要作用就是用最少的编码长度表示相同的内容,主要依据"频率大的编码短,频率小的编码长".
霍夫曼编码的特点
霍夫曼编码具有一些明显的特点：
1) 编出来的码都是异字头码，保证了码的唯一可译性。 2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。 3) 编码长度不统一，硬件实现有难度。 4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。 5) 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
学习心得体会
学习信息论与编码这门课，是在我们大三上学期的时候，是一门选修课，当时也不知道为什么稀里糊涂的就选了这门选修课。后来发现老师特别平易近人而且很幽默，对于我们也不算特别的严厉，上课的时候虽然会紧张但是也不会感觉到不舒服。总的来说我们还是很喜欢胡学敏老师滴。
这门课东西较多，理解起来很有点难度。第三章信道及信道容量 1，本章主要内容（1）信道的描述和分类；（2）信道容量的定义（重点）；（3）信道容量的计算（重点和难点）；（4）有噪信道编码与Shannon第二编码定理（重点）；（5）信道编码原理； 2，心得体会根据不同的条件，信道的种类各不相同。如按随机变量的取值类型划分，信道可分为离散信道，连续信道和
半离散半连续信道；而根据信道的输入、输出个数划分时，信道又可分为单用户信道和多用户信道。信息传输率，也就是通信原理里面所说的传信率，是本课程中最重要的一个知识点，它看似简单，其实暗藏玄机，做题时一不小心就会掉进“沟里”去了，在学习通信原理的过程中我对此是颇有体会。
所谓信道容量就是一个信道的最大信息传输速率，它是描述信道传输信息能力的一个参数。对于信道容量的计算，如对称信道的信道容量，准对称信道的信道容量，可逆矩阵信道的信道容量等，是重点，同时也是一个难点。有噪信道编码与Shannon第二编码定理部分，理论性很强，要想深刻领悟该部分，必须得有很好的数学基本功，对香农定理和Shannon第二编码定理的证明等难度较大。
信道编码原理部分和我们正在学习的《信道编码》相辅相成，对我们以后的学习起到了良好的指引作用。第四章离散信源 1，本章主要内容（1）离散无记忆信源的扩展信源；（2）离散平稳信源；（3）马尔科夫信源；（4）信源的信息冗余。 2，心得体会将信源输出的随机变量分组，每组作为一个随机矢量，则信源可等效为一个输出随机矢量的信源，称为离散无记忆信源的扩展信源。联合熵，平均符号熵，条件熵是离散平稳信源里面的几个重要概念，应重点理解和记忆。同时，离散平稳信源的四个性质也应熟练掌握。
马尔可夫信源就是任何时刻信源符号发生的概率只与前面已经发生的m个符号有关，而与更前面发生的符号无关的信源。在实际中，信源一般先验概率分布不均匀且有记忆，因此引入信源的冗余度来衡量信源的相关性程度，在此基础上形成了数据压缩等相关课程。
虽然我们都很喜欢胡学敏老师，但是喜欢老师也不能拯救我的智商，对于这种课程真的是无能为力啊。很多时候都听不懂所以有时候听着听着就睡着了，或者就走神了，所以在课堂上老师可能会感觉我没有专心听讲，但其实事实是听不懂然后就。。。好吧，但其实还是学到了很多东西，而且还欣赏到了老师优美的摄影哈哈哈哈。
附录二 表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
三进制霍夫曼编码 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'上最优
中国矿业大学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]；
霍夫曼编码 霍夫曼编码(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) 该字符串的平均码长
图像压缩编码实验报告 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： （1）无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。（2）有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； （3）混合编码 JBIG，H.261，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致分
哈夫曼编码步骤： 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。） 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，直到集合F中只有一棵二叉树为止。 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在Win-TC 下测试通过 * 实现过程：着先通过HuffmanTree() 函数构造哈夫曼树，然后在主函数main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/ #include
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));
实验四图像压缩 姓名：学号：邮箱： 一、实验目的 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"stdafx.h" #include"stdio.h" #include"conio.h" #include
霍夫曼编码的matlab实现 一、实验内容： 用Matlab语言编程实现霍夫曼（Huffman）编码。 二、实验原理及编码步骤： 霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。以本教材P74例题3-18信源为例： 信源： X x1 x2 x3 x4 x5 q(X) = 0.4 0.2 0.2 0.1 0.1 解：
通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。 特点：霍夫曼编码在三种编码方法中编码效率最高 基本步骤：p72 三、实验程序及运行结果 （见附录6） 程序流程图：XXXXXXXXXXXX 四 分析结果 由程序运行结果可知： 方法一（概率之和往上排）： 码字：11 01 00 101 100 编码效率： %4.962 .212 .21log 2 .22.038.0212 .2)(log ) (log )(log n 5 11≈= ==?+?==-= = ∑ηη所以：） （D n X H D n xm q xm q D X H
码长均值：2.22.038.02n 1=?+?= 码长均方差：{}16.02.0)2.23(8.0)2.22()2221=?-+?-=-n n E （ 方法二（概率之和往下排）： 码字：0 10 111 1101 1100 编码效率： %4.962 .212 .21log 2.22.042.032.024.0112.2)(log ) (log )(log n 5 12≈= ==?+?+?+?==-= =∑ηη所以：） （D n X H D n xm q xm q D X H 码长均值：2.22.042.032.024.01n 2=?+?+?+?= 码长均方差： { }36 .12.02.2-42.02.2-32.0)2.22(4.0)2.21()2 2222 22=?+?+?-+?-=-）（）（（n n E 比较方法一和方法二可知：两张编码方法平均码长相等，但方法二均方差较大，一般取均方 差小的编码方法，这样译码会更简单。
1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律
使用缺省的哈夫曼编码表有
解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等;
霍夫曼编码 四川大学计算机学院2009级戚辅光 【关键字】 霍夫曼编码原理霍夫曼译码原理霍夫曼树霍夫曼编码源代码霍夫曼编码分析霍夫曼编码的优化霍夫曼编码的应用 【摘要】 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman 编码。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。它属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 【正文】 引言 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 霍夫曼编码原理： 霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2*n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i].parent，如果i是myHuffmantree[i].parent 的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了。 霍夫曼树：
题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据文件包含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
成绩评定表
课程设计任务书
摘要 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。 关键字：哈夫曼；信源编码；MATLAB
目录 1设计目的及相关知识 (1) 1.1设计目的 (1) 1.2图像的霍夫曼编码概念 (1) 1.3Matlab图像处理通用函数 (1) 2课程设计分析 (3) 2.1 图像的霍夫曼编码概述 (3) 2.2 图像的霍夫曼编码举例 (4) 3仿真 (6) 4结果及分析 (9) 5附录 (12) 结束语 (15) 参考文献 (16)
1设计目的及相关知识 1.1设计目的 1）了解霍夫曼编码的原理。 2）理解图像的霍夫曼编码原理，了解其应用，掌握图像的霍夫曼编码的方法。3）对图像编码程序设计进行较深入的认识，对知识牢固掌握。 4）掌握图像霍夫曼编码的整个过程及其中的注意事项。 5）了解图像无损压缩的目的及好处。 1.2图像的霍夫曼编码概念 所谓霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码 1.3 Matlab图像处理通用函数 colorbar 显示彩色条 语法：colorbar \ colorbar('vert') \ colorbar('horiz') \ colorbar(h) \ h=colorbar(...) \ colorbar(...,'peer',axes_handle) getimage从坐标轴取得图像数据 语法：A=getimage(h) \ [x,y,A]=getimage(h) \ [...,A,flag]=getimage(h) \ [...]=getimage imshow显示图像 语法：imshow(I,n) \ imshow(I,[low high]) \ imshow(BW) \ imshow(X,map) \ imshow(RGB)\ imshow(...,display_option) \ imshow(x,y,A,...) \ imshow filename \ h=imshow(...) montage 在矩形框中同时显示多幅图像 语法：montage(I) \ montage(BW) \ montage(X,map) \ montage(RGB) \ h=montage(...)
以下是Huffman编码原理简介： 霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 对于学多媒体的同学来说，需要知道Huffman编码过程的几个步骤： l）将信号源的符号按照出现概率递减的顺序排列。（注意，一定要递减） 2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。 3）重复进行步骤1和2直到概率相加的结果等于1为止。 4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。 5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。 下面我举个简单例子: 一串信号源S＝{s1,s2,s3,s4,s5}对应概率为p＝{40，30，15，10，5}，（百分率） 按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！ 最后概率最大的编码为0，最小的编码为1。如图所示： 所以，编码结果为 s1=1 s2=00 s3=010 s4=0110 s5=0111 霍夫曼编码具有如下特点： 1) 编出来的码都是异字头码，保证了码的唯一可译性。 2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。 3) 编码长度不统一，硬件实现有难度。 4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。 5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
多媒体技术实验—图像压缩编码 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： (1)无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。(2)有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； (3)混合编码 JBIG，H.261，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT 和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其
中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致分成三个步骤： (1)使用正向离散余弦变换(forward discrete cosine transform，FDCT)把空间域表示的图变换成频率域表示的图。 (2)使用加权函数对DCT系数进行量化，该加权函数使得压缩效果对于人的视觉系统最佳。 (3)使用霍夫曼可变字长编码器对量化系数进行编码。 3、离散余弦变换（DCT）变换原理 离散余弦变换（DCT）是一种实数域变换，其变换核为实数余弦函数，图像处理运用的是二维离散余弦变换，对图像进行DCT，可以使得图像的重要可视信息都集中在DCT的一小部分系数中。二维DCT变换是在一维的基础上再进行一次DCT变换，公式如下： 11 (0.5)(0.5) (,)()()(,)cos cos () N N i j i j F u v c u c v f i j u v N N u c u u ππ == ++ ???? =???? ???? = = ≠ ∑∑ (1) f为原图像，经DCT 变换之后，F为变换矩阵。(0,0) F是直流分量，其他为交流分量。上述公式可表示为矩阵形式： (0.5) (,)()cos T F AfA j A i j c i i N π = + ?? =?? ?? (2) 其中A是变换系数矩阵，为正交阵。 逆DCT 变换： (,)(,) T f i j A F u v A = (3) 这里我们只讨论两个N相等的情况，即图像为方形(行列数相等)，在实际应用中对不是方阵的数据都应先补齐再进行变换的。 4、图象质量评价 保真度准则是压缩后图象质量评价的标准。客观保真度准则：原图象和压缩图象