下载文档原格式
10级电子信息工程《信息论与编码技术》学习报告霍夫曼编码在数据压缩中的应用姓名学号班级成绩2012年11月现代社会是信息社会，我们无时无刻都在跟信息打交道，如上网查阅图文资料，浏览最新的新闻，QQ聊天或者传送文件等。
人类对信息的要求越来越丰富，希望无论何时何地都能够方便、快捷、灵活地通过文字、语音、图像以及视频等多媒体进行通信。
在早期的通信领域中，能够处理和传输的主要是文字和声音，因此，早期的计算机和通信设备的处理能力跟人类的需求有相当大的差距。
随着通信信道及计算机容量和速度的提高，如今信息已成为通信领域市场的热点之一。
可是，大数据量的信息会给存储器的存储容量、通信干线信道的宽度以及计算机的处理速度增加极大的压力。
单纯依靠增加存储器容量、提高通信网络带宽和计算机处理速度来解决问题，在技术和经济上都不太现实。
显然，在信道宽度、通信链路容量一定的前提下，采用编码压缩技术、减少传输数据量，是提高通信速度的重要手段。
在信息化高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息在传递的过程中，能够保持节省性、保密性、无损性和高效性，而著名的霍夫曼编码就能够达到这样的要求。
因此研究霍夫曼编码对信息的压缩就是相当有必要的。
一、霍夫曼编码简介霍夫曼编码是一种可变字长编码的方式。
霍夫曼于1952年提出这种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的的码字，是一种构造最佳码的方法。
霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。
这样，处理全部信息的总码长一定小于实际信息的符号长度。
霍夫曼编码是一种根据字母的使用频率而设计的变长码,能提高信息的传输效率,至今仍有广泛的应用。
霍夫曼编码方法的具体过程是：1、首先把信源的各个输出符号序列按概率递降的顺序排列起来,求其中概率最小的两个序列的概率之和,并把这个概率之和看做是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)；2、然后,对参与概率求和的两个符号序列分别赋予二进制数字0和1。
图像处理中的图像压缩与恢复方法图像压缩是在图像处理领域中非常重要的一项技术。
在计算机视觉、数字通信以及存储等领域中，图像压缩可以大幅减少图像数据的大小，从而提高数据传输速度和存储效率。
同时，图像恢复则是在压缩后的图像还原以及修复中起到重要作用的技术。
在本文中，我们将介绍一些常见的图像压缩与恢复方法。
一. 图像压缩方法1. 无损压缩方法无损压缩方法是一种能够通过压缩图像数据，但不会导致图像失真的技术。
其中，最常见的无损压缩方法为预测编码和霍夫曼编码。
预测编码基于图像中像素之间的冗余性，通过预测后续像素的值，然后用预测值与实际值之间的差值进行编码。
其中，最著名的预测编码算法包括差分编码和游程编码。
霍夫曼编码是一种变长编码方式，利用出现频率较高的像素值分配较短的编码，而较低频率的像素值分配较长的编码。
通过统计每个像素值出现的频率，并根据频率构建霍夫曼树，可以实现对图像数据进行无损压缩。
2. 有损压缩方法有损压缩方法是一种能够通过压缩图像数据，但会导致图像失真的技术。
其中，最常见的有损压缩方法为离散余弦变换（DCT）和小波变换。
DCT是一种将图像从空间域转换到频域的方法，它能够将图像中的冗余信息集中在低频分量中，而将高频细节信息消除或减少。
通过对DCT系数进行量化和编码，可以实现对图像数据进行有损压缩。
小波变换是一种将图像分解成多个不同分辨率的频带的方法，通过对每个不同分辨率的频带进行量化和编码，可以实现对图像数据的有损压缩。
与DCT相比，小波变换可以更好地保留图像的局部细节。
二. 图像恢复方法1. 重建滤波器方法重建滤波器方法是在压缩图像恢复时常用的一种技术。
它是通过在图像的压缩域对被量化或编码的数据进行逆操作，将压缩后的图像数据恢复到原始图像。
常用的重建滤波器方法包括最近邻插值、双线性插值和双立方插值。
最近邻插值是一种简单的插值方法，它通过选择离目标位置最近的像素值来进行插值。
虽然该方法计算速度较快，但会导致图像失真。
图像压缩编码方法图像压缩编码是一种通过减少图像数据的表示量来降低存储和传输成本的技术。
图像压缩编码方法包括有损压缩和无损压缩两种。
有损压缩是指在压缩过程中会丢失一定的图像信息，但通常可以接受的程度在人眼感知上是不可察觉的。
有损压缩编码方法主要通过利用图像中的冗余信息和人眼视觉系统的特性来实现图像的压缩，主要有几种方法：1. 颜色空间转换：将RBG图像转换为YUV或者将CMYK图像转换为RGB，通过减少颜色通道的数量来降低数据量。
2. 离散余弦变换（Discrete Cosine Transform，DCT）：DCT是一种将原始图像通过变换后得到一系列频率系数的方法，低频系数所表示的信息对于人眼来说更加重要，而高频系数相对不重要，因此可以对高频系数进行压缩或丢弃。
3. 量化（Quantization）：通过对DCT系数进行适当的量化，将系数的数值范围映射到较小的范围内，进一步减小数据量。
量化的精度越高，则数据量越小，但图像质量也会受到影响。
4. 预测编码（Predictive Coding）：利用图像中像素之间的相关性，通过对当前像素值的预测来减少需要传输的数据。
常用的预测编码方法有差值编码（Differential Encoding）和运动补偿（Motion Compensation）。
5. 生成码字（Codebook）：通过统计图像中各个像素值的频次来生成一个码本，将高频次出现的像素值用较短的码字表示，以减小数据量。
有损压缩编码方法的主要优点是压缩率高，但缺点是压缩后图像质量有损失。
适用于图像中存在较多冗余信息或对图像质量要求不高的场景，如网络传输、存储等。
无损压缩编码是指在压缩过程中不丢失任何图像信息，通过利用图像内部的冗余性来减小数据量。
常用的无损压缩编码方法有：1. 霍夫曼编码（Huffman Coding）：将出现频率较高的像素值用较短的编码表示，出现频率较低的像素值用较长的编码表示，以减小数据量。
图像处理中的数字图像压缩数字图像压缩在图像处理中扮演着重要的角色。
数字图像压缩可以将图像数据压缩成更小的文件大小，更方便存储和传输。
数字图像压缩分为有损和无损两种不同的技术，本文将详细讨论这两种数字图像压缩方法。
一、无损压缩无损压缩是数字图像压缩中最常用的技术之一。
无损压缩的优点是可以保持图片原始数据不被丢失。
这种方法适用于那些需要保持原始画质的图片，例如医学成像或者编程图像等。
无损压缩的主要压缩方法有两种：一种是基于预测的压缩，包括差异编码和改进变长编码。
另一种是基于统计的压缩，其中包括算术编码和霍夫曼编码。
差异编码是一种通过计算相邻像素之间的差异来达到压缩目的的方法。
它依赖于下一像素的值可以预测当前像素值的特性。
改进的变长编码是一种使用预定代码值来表示图像中频繁出现的值的压缩技术。
它使用变长的代码，使得频繁出现的值使用较短的代码，而不常用的值则使用较长的代码。
算术编码是一种基于统计的方法，可以将每个像素映射到一个不同的值范围中，并且将像素序列编码成一个单一的数值。
霍夫曼编码也是一种基于统计的压缩方法。
它通过短代码表示出现频率高的像素值，而使用长代码表示出现频率较低的像素值。
二、有损压缩有损压缩是另一种数字图像压缩技术。
有损压缩方法有一些潜在的缺点，因为它们主要取决于压缩率和压缩的精度。
在应用有损压缩技术之前，必须确定压缩强度，以确保压缩后的图像满足预期的需求。
有损压缩方法可以采用不同的算法来实现。
这些算法包括JPEG、MPEG和MP3等不同的格式。
JPEG是最常用的有损压缩算法，它在压缩时可以通过调整每个像素所占用的位数来减小图像的大小。
MPEG是用于压缩视频信号的一种压缩技术。
它可以将视频信号分成多个I帧、P帧和B帧。
I帧代表一个完整的图像，而P帧和B帧则包含更少的信息。
在以后的编码中，视频编码器使用压缩技术将视频序列压缩成较小的大小。
MP3是一种广泛使用的音频压缩技术，它使用了同样的技术，包括频域转换、量化和哈夫曼编码。
霍夫曼编码解码过程霍夫曼编码是一种基于概率的变长编码方法，主要用于无损数据压缩。
其核心思想是给出现概率较高的符号赋予较短的编码，反之则赋予较长的编码。
这样，平均码长将会接近于原始数据的熵，从而实现有效的数据压缩。
以下是霍夫曼编码和解码的过程：霍夫曼编码过程：1.首先，统计出待编码数据中每个字符出现的频率，例如，对于字符串"ABABABABA"，我们可以得到字符'A'出现4次，字符'B'出现5次。
2.创建一个霍夫曼树。
这个树是一个二叉树，其中每个节点代表一个字符，节点的频率作为权重。
3.从根节点开始，对于每个节点，如果其左子节点和右子节点代表的字符不同，则将当前节点替换为一个新的字符，这个新字符的码字是左子节点和右子节点码字的组合。
需要注意的是，实际的霍夫曼编码过程中可能会有多种不同的树结构生成相同的结果，因此在具体实现时需要保证算法的稳定性和可重复性。
霍夫曼解码过程：霍夫曼解码是将霍夫曼编码后的数据进行还原的过程。
由于霍夫曼编码是前缀编码，也就是说编码后的码字没有前缀相同的后缀，因此解码过程是唯一的。
具体来说，解码步骤如下：1.从第一个字节开始，根据霍夫曼树的每个分支的权值（即字符出现的频率），从根节点向下查找对应的字符。
例如，对于码字"00"，我们首先找到根节点，然后找到左子节点对应的字符'A'。
2.对于每个后续的字节，重复上述步骤。
需要注意的是，由于霍夫曼编码是前缀编码，因此我们不需要担心码字的结束位置，只要遇到一个码字，就可以一直解码下去，直到所有数据都被解码。
通过以上步骤，我们可以将霍夫曼编码的数据还原成原始的数据。
总的来说，霍夫曼编码是一种非常有效的无损数据压缩方法，尤其适用于数据中存在大量重复元素的情况。
图像编码是将图像转化为数字信号的过程，通过压缩图像，可以减少存储空间和传输带宽的需求。
在图像编码领域，有许多常用方法，本文将介绍其中的几种。
1. 无损编码：无损编码是一种压缩图像的方法，它不丢失任何图像信息。
常见的无损编码方法有：（1）Run-Length Encoding (RLE)：该方法通过将重复的像素值替换为像素值和重复次数的组合来压缩图像。
这种方法在图像中有大量相邻重复像素值的情况下表现良好。
（2）Huffman 编码：Huffman 编码是一种变长编码方法，通过将出现频率较高的像素值用较短的编码表示，出现频率较低的像素值用较长的编码表示来压缩图像。
Huffman 编码在统计图像中像素值分布的情况下可以取得较好的压缩效果。
（3）LZW 编码：LZW 编码是一种字典编码方法，它将连续的像素值序列作为字典项，出现频率较高的连续序列用较短的编码表示，出现频率较低的连续序列用较长的编码表示来压缩图像。
LZW 编码在处理连续重复出现的序列时效果较好。
2. 有损编码：有损编码是一种压缩图像的方法，它在压缩过程中会丢弃一些图像信息，以达到更高的压缩比。
常见的有损编码方法有：（1）JPEG 编码：JPEG 编码是一种基于离散余弦变换的编码方法，它通过将图像分成多个 8x8 尺寸的像素块，然后对每个块应用离散余弦变换，再将变换后的系数进行量化和编码来压缩图像。
JPEG 编码广泛应用于静态图像的压缩。
（2）JPEG2000 编码：JPEG2000 是 JPEG 编码的升级版，它在离散小波变换的基础上进行编码。
JPEG2000 编码使用基于小波变换的空间频率分解，将图像分为多个不同分辨率的子带，并对每个子带进行独立的编码。
这种方法可以提供更好的压缩质量和可扩展性。
（3）WebP 编码：WebP 编码是一种针对网络应用的图像编码方法，它结合了无损和有损编码的特点。
WebP 编码可以根据图像内容的复杂程度自动选择使用无损或有损编码来进行图像压缩，以达到更好的压缩效果和更快的加载速度。
1.1 算法在计算机科学领域的重要性1.2 Lempel-Ziv算法和霍夫曼编码的重要性二、Lempel-Ziv算法2.1 Lempel-Ziv算法的基本原理2.2 Lempel-Ziv算法的应用及优点2.3 Lempel-Ziv算法的局限性及改进方法三、霍夫曼编码3.1 霍夫曼编码的基本原理3.2 霍夫曼编码的应用及优点3.3 霍夫曼编码的局限性及改进方法四、比较与应用4.1 Lempel-Ziv算法和霍夫曼编码的共同点 4.2 Lempel-Ziv算法和霍夫曼编码的区别4.3 Lempel-Ziv算法和霍夫曼编码的实际应用五、结论六、参考文献在当今信息爆炸的社会，算法作为计算机科学领域的核心内容之一，扮演着不可或缺的重要角色。
在众多的算法中，Lempel-Ziv算法和霍夫曼编码以其独特的优势在数据压缩领域得到了广泛的应用。
本文将分别对Lempel-Ziv算法和霍夫曼编码进行深入剖析，并对两者进行比较与应用的研究，旨在全面了解这两种算法的原理、应用及优缺点，以及它们在实际中的应用情况。
二、Lempel-Ziv算法2.1 Lempel-Ziv算法的基本原理Lempel-Ziv算法是一种无损数据压缩算法，主要用于提高数据传输效率和减少存储空间。
该算法主要基于字符串的重复出现，通过动态字典结构改进数据的压缩效果。
Lempel-Ziv算法的基本原理是将输入的数据流进行分析，将重复出现的字符串存储在一个字典中，并用新的符号来代替这些重复的字符串。
通过这种方式，可以大大减小数据的体积，提高了数据的压缩率。
2.2 Lempel-Ziv算法的应用及优点Lempel-Ziv算法在图像压缩、音频压缩、文本压缩等领域有着广泛的应用。
相比其他压缩算法，Lempel-Ziv算法具有压缩速度快、压缩率高的优点，尤其在重复性较高的数据中表现尤为突出。
2.3 Lempel-Ziv算法的局限性及改进方法然而，Lempel-Ziv算法也存在一定的局限性，主要表现在对于非重复字符串的压缩效果不佳，以及字典的不断增大会增加算法的时间复杂度。
什么是数据压缩算法请介绍几种常见的数据压缩算法数据压缩算法是一种通过减少数据表示的位数或者利用数据的统计特性来减少数据占用空间的技术。
数据压缩算法广泛应用于计算机科学和信息技术领域，在数据传输、存储和处理中起到了关键作用。
本文将介绍几种常见的数据压缩算法，包括无损压缩算法和有损压缩算法。
一、无损压缩算法无损压缩算法是指能够还原原始数据的压缩算法，压缩后的数据与原始数据完全相同。
以下是几种常见的无损压缩算法。
1. 哈夫曼编码（Huffman Coding）哈夫曼编码是一种基于数据出现频率的最优前缀编码算法。
该算法通过构建哈夫曼树来生成唯一的编码表，将频率较高的数据用较短的编码表示，从而实现数据压缩。
哈夫曼编码广泛应用于文件压缩、图像压缩等领域。
2. 霍夫曼编码（Huffman Coding）霍夫曼编码是一种用于压缩无损图像数据的编码算法，它是以哈夫曼编码为基础进行优化而得到的。
霍夫曼编码通过统计图像中像素的出现频率来生成编码表，并利用较短的编码来表示频率较高的像素值。
这使得图像数据能够以更少的位数来表示，从而实现了数据的压缩。
3. Lempel-Ziv-Welch压缩算法（LZW）Lempel-Ziv-Welch压缩算法是一种无损压缩算法，常用于文本文件的压缩。
该算法通过不断增加编码长度的方式来处理输入的数据流，将出现的字符序列以短编码代替，并将新出现的字符序列添加到编码表中。
这种算法有效地利用了数据中的重复模式，实现了数据的高效压缩。
二、有损压缩算法有损压缩算法是指为了实现更高的压缩率，可以牺牲一定的数据精度或质量的压缩算法。
以下是几种常见的有损压缩算法。
1. JPEG压缩算法（Joint Photographic Experts Group）JPEG压缩算法是一种广泛应用于图像压缩的有损压缩算法。
该算法通过将图像分割为多个8x8的小块，对每个小块进行离散余弦变换（DCT）和量化，并对量化后的系数进行编码和熵编码。
CAD图像编码和解码的方法CAD软件是一种专业的设计工具，广泛应用于建筑、制造、工程等领域。
在使用CAD软件进行设计时，图像编码和解码是一个非常重要的环节。
本文将介绍CAD图像编码和解码的方法，帮助读者更好地利用CAD软件进行设计工作。
一、CAD图像编码的方法1. 压缩编码法：压缩编码是一种将图像数据进行压缩，减小数据量的方法。
常见的压缩编码方法有无损编码和有损编码两种。
无损编码可以完全恢复原始数据，适用于对图像质量要求较高的应用场合。
常见的无损编码方法有：Run-length encoding（行程编码）、Huffman coding（霍夫曼编码）等。
有损编码则牺牲了一定的图像质量，以达到更高的压缩比。
有损编码方法有：JPEG（联合图像专家组）等。
2. 矢量化编码法：矢量化编码是将图像数据转换为矢量数据的方法。
通过将图像中的像素点转化为点、线、曲线等矢量信息，可以大幅度减小数据量。
矢量化编码方法可以提高CAD软件的绘图效率，并且可以无损地进行缩放和编辑。
常见的矢量化编码方法有：Bezier曲线拟合、多边形拟合等。
3. Huffman编码法：Huffman编码是一种无损编码方法，通过特殊的编码方式，将频率较高的字符用较短的编码表示，将频率较低的字符用较长的编码表示。
在CAD图像编码中，可以通过统计图像数据中像素的出现频率，进行Huffman编码，以减小图像的数据量。
Huffman编码在CAD图像编码中应用广泛，可以提高图像数据的传输和存储效率。
二、CAD图像解码的方法1. 解码器：CAD软件通常会配备相应的解码器，用于解析和恢复编码后的图像数据。
解码器可以根据编码算法和编码参数，还原出原始的图像数据，保证图像的质量。
解码器的优化和改进可以提高解码的速度和效率。
常见的CAD图像解码器有：JPEG解码器、GIF解码器等。
2. 解码算法：不同的编码算法有不同的解码方法。
解码算法通常是对编码过程的逆过程，通过逆向计算和处理，将编码后的数据转化为原始的图像数据。
成绩评定表 学生姓名 班级学号 ********** 专业 电子信息工程 课程设计题目 图像的无损压缩程序设计——霍夫曼编码
评 语 组长签字：
成绩 日期 2015年7月20日 课程设计任务书 学院 信息科学与工程 专业 电子信息工程 学生姓名 班级学号 1203030119 课程设计题目 图像的无损压缩程序设计——霍夫曼编码 实践教学要求与任务： 本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。
工作计划与进度安排： 2015年7月8日—11日：熟悉编程环境，查阅相关资料。 2015年7月11日—12日：图像的霍夫曼编码程序设计。 2015年7月12日—13日：编码、调试、实验与分析。 2015年7月13日—15日：撰写课程设计报告。 2015年7月15日—19日：准备答辩。
指导教师： 2015年7月2日 专业负责人： 2015年7月2日 学院教学副院长： 2015年7月2日 摘 要 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。 关键字：哈夫曼；信源编码；MATLAB 目 录 1设计目的及相关知识 ............................................ 1 1.1设计目的 ................................................. 1 1.2图像的霍夫曼编码概念 ..................................... 1 1.3Matlab图像处理通用函数 ................................... 1
2课程设计分析 .................................................. 3 2.1 图像的霍夫曼编码概述 .................................... 3 2.2 图像的霍夫曼编码举例 .................................... 4
3仿真 .......................................................... 5 4结果及分析 .................................................... 8 5附录 ......................................................... 11 结束语 ......................................................... 14 参考文献 ....................................................... 15 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(...) immovie创建多帧索引图的电影动画 语法：mov=immovie(X,map) \ mov=immovie(RGB) subimage在一副图中显示多个图像 语法：subimage(X,map) \ subimage(I) \ subimage(BW) \ subimage(RGB) \ subimage(x,y,...) \ subimage(...) truesize调整图像显示尺寸 语法：truesize(fig,[mrowsmcols]) \ truesize(fig) warp 将图像显示到纹理映射表面 语法：warp(X,map) \ warp(I ,n) \ warp(z,...) warp(x,y,z,...) \ h=warp(...) zoom 缩放图像 语法：zoom on \ zoom off \ zoom out \ zoom reset \ zoom \ zoom xon \ zoom yon\ zoom(factor) \ zoom(fig,option) 2课程设计分析 2.1 图像的霍夫曼编码概述 赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman算法而产生。Huffman编码是一种基于统计的无损编码。 根据变长最佳编码定理，Huffman编码步骤如下： （1）将信源符号xi按其出现的概率，由大到小顺序排列。 （2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止； （3）对每对组合的上边一个指定为1，下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1）； （4）画出由每个信源符号到概率1.0处的路径，记下沿路径的1和0； （5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的Huffman码。 Huffman编码的特点是： （1）Huffman编码构造程序是明确的，但编出的码不是唯一的，其原因之一是两个概率分配码字“0”和“1”是任意选择的（大概率为“0”，小概率为“1”，或者反之）。第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。这样编出的码字就不是唯一的。 （2）Huffman编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。 （3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了霍夫曼编码的应用。 （4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原因。 2.2 图像的霍夫曼编码举例 假设一个文件中出现了8种符号S0，S1，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3比特。假设编码成000，001，010，011，100，101，110，111那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01，11，101，0000，0001，0010，0011，100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。 可由下面的步骤得到霍夫曼码的码表 (1) 首先把信源中的消息出现的频率从小到大排列。 (2) 每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。 (3) 重复(2)，直到最后得到和为1的根节点。 (4) 将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。 上面的例子用Huffman编码的过程如图下图所示，其中圆圈中的数字是新节点产生的顺序。
