填空题：
1、信源编码主要解决传输的问题，信道编码主要解决传输的问题。
2、数据压缩的信号空间包括、、。
3、数据压缩按其压缩后是否产生失真可划分为
和两大类。
第二章
填空题：
1、脉冲编码调制包括、、三个步骤。
2、连续信号的多种离散表示法中，我们最常用的取样方法是。
3、若要将取样信号准确地恢复成原信号，取样频率必须满足定理。
4、黑白电视信号的带宽大约为5MHz，若按256级量化，则按奈奎斯特准则取样时的数据速率为。如果电视节目按25帧/s发送，则存储一帧黑白电视节目数据需内存容量。
5、量化器可分为和两大类。
6、量化器的工作特性可分为、、三个区域。
6、按照处理方法是否线性来判断，我们认为量化过程本身是。
7、我国数字电话网中压扩量化的对数函数采用曲线。
8、信号质量的主观度量方法中最常用的判决方法是。
9、对信号压缩系统的性能评价应从几个性能指标上综合评价，这些性能指标包括、、、。
简答题：
1、量化误差和噪声的本质区别是什么
2、简述压扩量化的工作过程
3、数据压缩中的“二次量化”是指什么它和模数转换时的量化有什么区别
证明题：
d和量化输出电1、试导出以均方误差最小定义的最佳量化方法中量化判决电平
k
平k y 的表达式。
2、证明M-L 量化器的最小量化误差为：{}{}∑-=+≤<-=1
012
2min J k k k k d x d p y x E ε
第三章
填空题：
1、离散无记忆平稳信源的冗余度隐含在 。
2、对于联合信源，其冗余度除了各自本身的冗余度外还隐含在 。
3、离散有记忆信源的的理论极限是 。
4、在限失真编码理论中，使限失真条件下比特数最少的编码称为 。
问答题：
1、什么是平均自信息量（信息熵），平均条件自信息量（条件熵）以及平均互信
息量它们之间有什么关系
2、简述率失真函数的基本含义，并指出它对信源编码的指导意义。
3、什么是最大离散熵它对数据压缩有什么指导意义
证明题：
2、证明 ()()|H Y X H Y ≤，并简述它对数据压缩的意义。
3、证明：()()()Y |X H X H Y X I －＝；。
第四章
填空题：
1、统计编码主要是利用消息或消息序列 的分布特性，注重寻
找 的最优匹配。
2、长度为L 1，L 2，…，L n 的m 进制唯一可译码存在的充分必要条件是 。
3、唯一可译码的基本要求是 。
4、若W 中任一码字都不是另一个码字的字头，则W 称为 。
5、霍夫曼编码完全依据 来构造平均码长最短的异字头码字。
6、基本RLC 的压缩效能取决于整个数据流中的 、 和
。
7、算数编码中为使条件概率p 和不确定数Q 这两个参数匹配好，关键问题是要
选择合适的概率模型，使 。
8、LZW 算法的显著特点是 、 、 。
9、不需要知道信源统计特性的最佳信源编码理论，称为 。
简答题：
1、 简述自适应霍夫曼编码的主要思想和工作过程
2、 简述Golomb 编码的基本思想
3、 简述算数编码的基本原理
4、 简述自适应算数编码的实现过程
计算题
1、设信源X 的符号集为{a 1 a 2 a 3 a 4 a 5 a 6}，其在信源中出现的概率分别为：P(a 1)=，
P(a 2)=，P(a 3)=，P(a 4)=，P(a 5)=，P(a 6)=。（20分）
(1)计算该信源的熵及冗余度；
(2)对其进行霍夫曼编码；
(3)计算编码效率。
1、对一个7符号的信源{}721,,,A a a a ＝，设721,,,a a a 出现的概率分别
为，，，，，，。（20分）
(1) 计算该信源的熵及冗余度；
(2) 对其进行霍夫曼编码；
(3) 计算编码效率。
2、设信源X 的符号集为{a 1 a 2 }，出现概率分别为P(a 1)=，P(a 2)=。
(1) 计算该信源的熵及冗余度；
(2) 设码符号为A={0，1}，做出霍夫曼编码，并求出平均码长l ；
(3) 分别将X 延长至X 2及X 3进行延长霍夫曼编码，并求出K=2和K=3时的平均
码长（K l K /）；
(4) 计算上述K=1，2，3时的编码效率。
2、设信源X 的符号集为{a 1 a 2 }，出现概率分别为P(a 1)=，P(a 2)=。
(1) 计算该信源的熵及冗余度；
(2) 设码符号为A={0，1}，做出霍夫曼编码，并求出平均码长l ；
(3) 分别将X 延长至X 2及X 3进行延长霍夫曼编码，并求出K=2和K=3时的平均
码长（K l K /）；
(4) 计算上述K=1，2，3时的编码效率。
3、设某信源取自符号集S={a,b,c,d,e,!},其中前5个符号为实际英文字母，而最后
一个符号“！”则用来表示编码结束，各符号概率和初始子区间范围[P （a i-1,a i ）]
如下表所示。设待编码的字符串为单词“bed ”,编码器和解码器都知道区间初值为
[0,1]
3、设某信源取自符号集S={a,b,c,d,e,!},其中前5个符号为实际英文字母，而最后一个符号“！”则用来表示编码结束，各符号概率
和初始子区间范围[P （a i-1,a i ）]如下表所示。
设待编码的字符串为单词“bad ”,编码器和解码器都知道区间初值为[0,1]
4、试对一个3字母字符串“abcbabaaaaaaa ”作出LZW 编码。 4、试对一个3字母字符串“ababcbabaaaaa ”作出LZW 编码。
第五章
填空题：
1、预测编码中最经典的最佳预测方法是。
2、预测编码中一般情况下若{x k}为N阶马尔可夫过程，则用阶预测。
1、人耳可以听到的声音频率范围在。
2、语音信息能够压缩的基本理论依据是
和。
3、如果有两个声音，那么一个声音的存在会影响人耳对另一个声音的听觉能力，称为声音的。
3、掩蔽效应与两个声音的声强、频率、相对方向及延续时间有关，可分为
和。
5、语音压缩需要在、以及三方面进行折衷。
6、传统语音压缩技术的两种主要方法是、。
6、对静止图像进行预测编码时，根据这些已知样值与待测样值间的位置关系，可分为预测、预测和预测。
7、JPEG无损压缩系统中采用的的预测编码方法为。
8、JPEG-LS编码系统和JPEG无损压缩模式的最大不同是引入、
和。
7、我国规定的视频带宽和建议传输用的带宽均为。
8、为便于制式转换与兼容，CCIR601规定对彩色电视信号的亮度和色差采用
编码。
8、对采样率为f，每样值R位编码的数字信源，其需要的传输率I可以用公式表示为。一幅512×512的彩色图像，若按4：2：2的分量编码标准格式，用频率采样，按8bit/pel编码，则其数码率为。
9、为便于不同电视制式的相互转换，建议的视频压缩标准中的输入图像格式为，其具体参数为。
9、为避免CIF格式的缺陷，MPEG-1建议的视频压缩标准中采用了格式，具体参数为、。
11、电视信号的冗余度主要体现在相关性、相关性
和相关性几方面。
12、利用序列图像在时间轴方向的相关性而进行的压缩编码称为。
13、人类视觉系统具有特性、特性、特性。
14、要充分利用人的主观视觉约束，电视图像编码器在设计实现时需
和。
15、运动补偿帧间预测技术组成主要有、、和
四部分。
16、是最常用的一类运动估计方法。
17、衡量块匹配效果的常用准则中用得最多的是。
18、块匹配算法中最简单可靠的最优匹配搜索方法是。
19、H．264允许编码器使用多于一帧的先前帧用于运动估计，称为技术。
问答题:
1、为什么DPCM能进行数据压缩它利用了数据压缩的哪条基本途径
2、简述LPC语音合成模型是如何合成语音信号的
1、分别以DPCM、LPC声码器和线性预测合成-分析编码为例简述语音信号波形编码、参数编码和混合编码的工作原理。
1、简述DPCM的基本原理及其在语音预测编码和活动图像预测编码中的具体应用方法。
计算题：
1、设有如图所示的8×8图像{x(m,n)}
4 4 4 4 4 4 4 4 n
4 5 5 5 5 5 4 3
4 5 6 6 6 5 4 3
4 5 6 7 6 5 4 3
4 5 6 6 6 5 4 3
4 5 5 5 5 5 4 3
4 4 4 4 4 4 4 3
m 4 4 4 4 4 4 4 3
(1) 计算该图像的熵值；
(2) 对该图像做前值预测（即列差值。8×8区域之外图像取零值）：
x
n
m
x
=n
m
(
,
)
,
)1
(?-
试给出误差图像及其熵值；
(3) 若对上述误差图像再做行差值：
m
e
n
m
=
e-
,
(?n
,1
)
(
)
请再给出误差图像及其熵值；
(4) 试比较上述3个熵值，你能得出什么结论
第六章
填空题：
1、映射变换的关键在于能产生，使对其编码所需总比特数比对原始数据小得多。
2、二维DCT的计算采用。
2、正交变换具有如下有用的性质：、、、
。
3、对于图像编码，最常用的子图像块大小为M×M= 。
4、图像变换编码中变换域系数的选择，原则上应是保持的系数。
5、变换系数的选择通常有、两种方法。
5、JPEG图像建立的两种模式分别为、。
6、JPEG标准可采用的四种操作模式为、
、、。
7、JPEG基本系统的核心是。
8、由于正交变换在边界处存在固有的不连续性，使得在块边界处可能产生很大的幅度差异，这种现象称为。
6、MDCT采用技术来减轻变换编码的“边界效应”。
简答题：
1、简述正交变换实现数据压缩的物理本质
计算题：
1、
第七章
填空题：
1、子带编码中由于两个半带滤波器不理想造成的高、低子带信号能量相互混叠的现象称为，解决方法可采用滤波器组。
2、宽带音频编码高效编码器一定包含和两个模型。
问答题：
1、简述分析-综合编码的实质并具体阐明子带编码中整数半带滤波器分析和综合系统的基本原理。-
压缩技术实验编码 实验一统计编码 实验目的 1.熟悉统计编码的原理 2.掌握r元Huffman编码的方法； 3.了解Huffman编码效率及冗余度的计算; 二、实验原理 霍夫曼编码，又称最佳编码，根据字符出现概率来构造平均长度最短的变长编码。 Huffman编码步骤： (1)把信源符号x i(i=1,2,…按出现概率的值由大到小的顺序排列； (2)对两个概率最 小的符号分别分配以“ 0和“ 1,'然
后把这两个概率相加作为一个新的辅助符号的概率； (3)将这个新的辅助符号与其他符号一起重新按概率大小顺序排列； ⑷跳到第2步，直到出现概率相加为1为止； (5)用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号； (6)从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“ 0或“ 1顺序排列起来，就是端点所对应的信源符号的码字。 以上是二元霍夫曼编码。如果是r元霍夫曼编码，则应该如何做呢？ 在HUFFMAN 编码方案中，为出现概率较小的信源输出分配较长的码字，而对那些出现可能性较大的信源输出分配较短的码字。为此，首先将r 个最小可能的信源输出合并成为一个新的输出，该输出的概率就是上述的r 个输出的概率之和。重复进行该过程直到只剩下一个输出为止。信源符号的个数q 与r 必须满足如下的关系式： q = (r-1) n + r n 为整数如果不满足上述关系式，可通过添加概率为零的信源符号来满足。这样就生成了一个树，从该树的根节点出发并将0、1 分别分配给任何r 个来自于相同节点的 分支，生成编码。可以证明用这种方法产生的编码在前向树类
《多媒体技术基础》复习题（最新） 一、填空 1、多媒体的英文是multimedia，Virtual Reality的含义是虚拟现实。 2、Windows95(98)系统中播放声音的软件有：CD播放器、媒体播放机和录音机。 3、文本、声音、图形、图像和动画等信息的载体中的两个或多个的组合构成了多 媒体。 4、图形也称矢量图，是由诸如直线、曲线、圆或曲面等几何图形（称 为图形）形成的从点、线、面到三维空间的黑白或彩色几何图。 5、音频有时也泛称声音，包括语音说明、背景音乐和效果音响。 6、计算机中保存声音文件的格式有多种，常用的有：波形音频文件（WAV）和 数字音频文件（MIDI）。 7、波形音频文件是真实声音数字化后的数据文件。 8、数字音频文件又称乐器数字接口，是以一系列指令来表示声音的，可看成 是声音的符号表示。 9、多媒体系统可分成6个层次：多媒体外围设备、多媒体计算机硬件系 统、多媒体核心系统、媒体制作平台与工具、创作/编辑软件、 应用系统。 10、构建一个多媒体系统，硬件是基础，软件是灵魂。 11、多媒体外围设备包括：音频、视频等多种媒体的输入/输出设备和装置，通 讯（网络）传输设备及装置。 12、多媒体计算机硬件系统，包括多媒体计算机主机系统（MPC）及各种外围设备 的接口部件。 13、多媒体核心系统，其实质就是多媒体操作系统，也包括设备的驱动程序。 14、媒体制作平台与工具，就是多媒体素材准备工具。 15、多媒体编辑与创作系统，该层是开发多媒体应用系统的平台或环境，可以 实现各种媒体的综合利用。 16、多媒体关键技术一般分成二类：多媒体应用所涉及的关键技术、研制多媒 体计算机系统本身要解决的关键技术。 17、研制多媒体计算机系统要解决的关键技术包括：多媒体数据压缩技术、多 媒体专用芯片技术、多媒体输入/输出技术、多媒体存储技术、多 媒体系统软件技术。 18、多媒体应用涉及的关键技术包括：多媒体素材采集/制作技术、多媒体应 用程序开发技术、多媒体创作工具及开发环境、多媒体界面设计与人 机交互技术、多媒体网络通讯技术、虚拟现实技术。 19、目前常用的压缩编码方法分为两类：无损压缩法（或冗余压缩法/熵编码）和有 损压缩法（或熵压缩法）。 20、多媒体通讯是多媒体技术和通讯技术结合的产物，它将计算机的交互 性、通讯的分布性和广播、电视的真实性融为一体。如普通电话到可视电话。 21、现有的通讯网络包括：电话网、计算机局域网、综合业务数字网、宽 带综合业务数字网、有线电视网等。 22、计算机总线分为：ISA总线、PCI总线、USB总线。ISA总线只具备了 2Mbps 到6Mbps 的带宽；PCI总线具备了 133Mbps 的带宽；USB总线具有 12Mbps
龙源期刊网 https://www.doczj.com/doc/4614812827.html, 数据压缩技术综述 作者：汪见晗 来源：《科学与财富》2016年第04期 摘要：在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字 化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。本文从专利文献的视角对数据压缩技术的发展进行了全面的统计分析，总结了与数据压缩相关的专利申请趋势、主要申请人分布，介绍了数据压缩技术的重点技术分支及其发展历程，并分析了全球数据压缩技术演进特点，并绘制了国内重点申请人的技术发展路线图。 关键词：数据压缩；发展路线 1 数据压缩介绍 1.1 数据压缩的分类 目前，通用的主流压缩方法分为无损压缩和有损压缩。无损压缩利用数据的统计冗余进行压缩。数据统计冗余度的理论限制为2：1到5：1，所以无损压缩的压缩比一般比较低。这类方法广泛应用于文本数据、程序和特殊应用场合的图像数据等需要精确存储数据的压缩，通常的无损压缩编码方法有香农-范诺编码，霍夫曼（Huffman）编码，算术编码，字典压缩编码等。 有损压缩方法利用了人类视觉、听觉对图像、声音中的某些频率成分不敏感的特性，允许压缩的过程中损失一定的信息。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了比较大的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩，按照应用领域来分，有损压缩编码分为图像压缩编码，视频压缩编码，音频压缩编码。 2 数据压缩专利申请数据分析 本章主要对全球和国内数据压缩专利申请情况以及国内外专利重要申请人进行分析，从中得到技术发展趋势，以及各阶段专利申请人所属的国家分布和主要申请人。其中以每个同族中最早优先权日期视为该申请的申请日，一系列同族申请视为一件申请。 2.1 全球专利申请状况 2.1.1 全球数据压缩专利申请量
第四章 多媒体数据压缩与存储技术习题 4-1填空题 1．自信息函数是 的函数。必然发生的事件概率 为 ，自信息函数值为 。把 叫作信息熵或简称熵（Entropy ），记为 。 2．所有概率分布p j 所构成的熵，以 为最大，因此，可设法改变信源 的概率分布使 ，再用最佳编码方法使 来达到高效编码的目的。 3．MPEG 中文翻译“动态图像专家组”，MPEG 专家组推出的MPEG-1标准中文含 义是 标准，它包括 四部分。 4．CD-DA 中文含义 ，其相应的国际标准称为 书标准。CD-ROM 中文含义 ，其相应的国际标准称为 书标准。 5．在CD-ROM 光盘中，用 代表“1”， 而 代表“0”，为保证光盘上的信息能可靠读出，把“0”的游程最小长度限制在 个，而最长限制在 个。 6．DVD 原名 ，中文翻译 。DVD 光盘按单/双面与 单/双层结构可以分为 四种。按照DVD 光盘的不同用途，可以把它分为： ， ， ， ， ， 。 4-2简答题 1．请解释信息熵的本质为何？ 2．请解释在MPEG 压缩算法中，最好每16帧图像至少有一个帧内图（I 帧） 的原因。 3．简要说明光盘的类型有哪些？ 4．DVD 有哪些类型？DVD 存储容量大大增加的原因是什么？ 4-3应用题 1．某信源有以下6个符号，其出现概率如下： 求其信息熵及其Huffman 编码？ 2．设某亮度子块按Z 序排列的系数如下： ? ?????=8/1 8/1 8/1 8/1 4/1 4/1 654321a a a a a a X
k 0 1 2 3 4 5 6 7-63 系数： 12 4 1 0 0 -1 1 0 0 请按JPEG基本系统对其进行编码。 4-4计算题 1．请计算52速光盘的传输速率。 4-5上机应用题 1．请用Nero Express 7将上一章编辑的电影剪辑制作成VCD。
第二章作业 作业总体要求： 1.认真独立的完成 2.让文件名重新命名为自己的学号，然后通过http://10.66.4.241提交。 一．选择题 1.下列说法中不正确的是【B】。 A.有损压缩法会减少信息量 B.有损压缩法可以无失真地恢复原始数据 C.有损压缩法是有损压缩 D.有损压缩法的压缩比一般都比较大 2.下列属于无损压缩的是【B 】。 A．WA VE文件压缩成MP3文件 B.TXT文件压缩成RAR文件 C. BMP文件压缩成JPEG文件 D.A VI文件压缩成RM文件 3.图像序列中的两幅相邻图像，后一幅图像与前一幅图像之间有较大的相关， 这是【 D 】。 A. 空间冗余 B.时间冗余 C.信息熵冗余 D.视觉冗余 4.衡量数据压缩技术性能好坏的主要指标是【C】。 （1）压缩比（2）算法复杂度（3）恢复效果（4）标准化 A. （1）（3） B. （1）（2）（3） C. （1）（3）（4） D.全部 5.MPEG标准不包括下列哪些部分【C 】。 A.MPEG视频 B.MPEG音频 C.MPEG系统 D.MPEG编码 6.下列属于静态图像编码和压缩标准的是【B 】。 A．JPEG B.MPEG-1 C．MPEG-2 D.MPEG-4 7.声音信号是声波振幅随时间变化的【A 】信号. A.模拟 B.数字
C.无规律 D.有规律 8.在数字视频信息获取与处理过程中，下述顺序正确的是【A 】。 A.采样、A/D变换、压缩、存储、解压缩、D/A变换 B.采样、D/A变换、压缩、存储、解压缩、A/D变换 C.采样、压缩、A/D变换、存储、解压缩、D/A变换 D.采样、压缩、D/A变换、存储、解压缩、A/D变换 9.一般来说,表示声音的质量越高,则【C 】 A.量化位数越多和采样频率越低 B.量化位数越少和采样频率越低 C.量化位数越多和采样频率越高 D.量化位数越少和采样频率越高 10.5分钟双声道、16位采样位数、44.1kHZ采样频率声音的不压缩数据量是 【 B 】。 A. 48.47MB B. 50.47MB C. 105.84MB D. 25.23MB 11.下列采集的波形声音【 D 】的质量最好。 A、单声道,8位量化，22.05kHz采样频率 B、双声道,8位量化，44.1kHz采样频率 C、单声道,16位量化，22.05kHz采样频率 D、双声道,16位量化，44.1kHz采样频率 12.频率在20HZ-20KHZ的被称为【 A 】 A. 可听声波 B. 次声波 C.超声波 D.超音波 13.MIDI是音乐与【 A 】结合的产物. A.计算机 B.通信 C.高科技 D.通讯 14.Windows中使用录音机录制的声音文本的格式是【B 】 A. MIDI B.WA V C.MP3 D.MOD
数据结构实验报告记录文件压缩
————————————————————————————————作者：————————————————————————————————日期：
数据结构与程序设计实验 实验报告 课程名称数据结构与程序设计实验课程编号0906550 实验项目名称文件压缩 学号年级 姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静 实验室名称地点21B276 哈尔滨工程大学
实验报告四 实验课名称：数据结构与程序设计实验 实验名称：文件压缩 班级：学号：姓名：时间：2016.04.21 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat 中。 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt 文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 解压：将CodeFile.dat 文件利用哈夫曼树译码解压，恢复为源文件。 二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。 1.使用结构体数组统计词频，并存储: typedef struct Node{ int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }LeafNode[N]; 2.使用结构体数组存储哈夫曼树: typedef struct{ unsigned int weight;//权值 unsigned int parent, LChild, RChild; }HTNode,Huffman[M+1]; //huffman树 3.使用字符指针数组存储哈夫曼编码表： typedef char *HuffmanCode[2*M]; //haffman编码表 三、算法设计 1.读取文件，获得字符串 void read_file(char const *file_name, char *ch){ FILE *in_file = Fopen(file_name, "r"); unsigned int flag = fread(ch, sizeof(char), N, in_file); if(flag == 0){ printf("%s读取失败\n", file_name); fflush(stdout); } printf("读入的字符串是: %s\n\n", ch); Fclose(in_file); int len = strlen(ch);
数据压缩算法的综述 S1******* 许申益 摘要：数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机通讯领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上一些已经取得的成果，其中包括算术编码、字典式压缩方法以及Huffman码及其改进。 关键字：数据压缩；数据存储；计算机通讯；多媒体技术 1.引言 数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的存储和表示中常常存在一定的冗余度，一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman 提出了一种基于统计模型的压缩方法，Ziv Jacob 提出了一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机和通讯两个领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上的一些已经取得的成果。 本文主要介绍了香农范诺编码以及哈弗曼算法的基本思想，运用其算法的基本思想设计了一个文件压缩器，用Java 语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。 2数据压缩算法的分类 一般可以将数据压缩算法划分为静态的和动态的两类。动态方法又是又叫做适应性（adaptive）方法，相应的，静态方法又叫做非适应性方法（non-adaptive）。 静态方法是压缩数据之前，对要压缩的数据经过预扫描，确定出信源数据的
一、选择题(每题 1 分，共 15 分) 1、统计编码算法的性能评价指标主要是B。 （A）信号质量（B）比特率（C）复杂度（D）通信时延2、语音信号的预测编码中，不需传送预测误差的是C。（A）△M（B）（C）声码器（D）混合编码 3、以下对于算术编码的描述中，不正确的是C。 （A）具有自适应功能（B）不必预先定义信源的概率模型 （C）是分组码（D）二进制编码中的进位问题用插入填充位来解决 4、活动图像的预测编码中，常用的二维运动估计的运动估计模型是 C 。 （A）全局运动（B）密相运动（C）基于块的运动（D）基于对象的运动 5、对于联合信源（X，Y），对其进行数据压缩的理论极限是A。（A）联合熵（B）条件熵（C）无条件熵（D）平均互信息量 6、下列B是声码器发送端不需传送的参数？ （A）基音周期（B）音调间隔（C）预测系数（D）增益7、设信源发出，被编码成，若为有失真压缩，且允许失真为D，则数据压缩的极限数码率R（D）由C控制。
（A ）),(k j b a P （B ）)(k j b a P （C ）)(j k a b Q （D ）),(k j b a I 8、对图像进行二维子带分解时，若要进行三级倍频程分解，则共需要 C 个整数半带滤波器组。 （A ）4 （B ）6 （C ） 7 （D ）9 9、对图像进行二维子带分解时，若要进行三级倍频程分解，则共可划分出 B 个子带。 （A ）7 （B ）10 （C ）16 （D ）64 10、某图像子块共64个样本，对其进行子带编码，若利用滤波器组将 其划分成64个子带，则此编码利用的基本压缩途径是 B 。 （A ）概率匹配 （B ）对独立分量进行编码 （C ）利用条件概率 （D ）对平稳子信源进行编码 11、下列 D 是正确的？ （A ）若要用整数半带滤波器组划分出M 个子带，则需要M 个整数半带滤波器组。 （B ）用整数半带滤波器组划分子带之后，需要将子带频谱搬移到基带。 （C ）对某一频段来说，若要划分出低频和高频两个子带，需要两个整数半带滤波器组。 （D ）子带编码时，用整数半带滤波器组划分子带后，还需对子带重新取样。
第三章多媒体数据压缩
3.1 数据压缩的 基本原理和方法
3.1 数据压缩的基本原理和方法 ?压缩的必要性 音频、视频的数据量很大，如果不进行处理，计算机系统几乎无法对它进行存取和交换。 例如，一幅具有中等分辨率（640×480）的真彩色图像（24b/像素），它的数据量约为7.37Mb/帧，一个 100MB（Byte）的硬盘只能存放约100帧图像。若要达到每秒25帧的全动态显示要求，每秒所需的数据量为 184Mb，而且要求系统的数据传输率必须达到184Mb/s。 对于声音也是如此，若采用16b样值的PCM编码，采样速 率选为44.1kH Z ，则双声道立体声声音每秒将有176KB的 数据量。
3.1 数据压缩的基本原理和方法 ?视频、图像、声音有很大的压缩潜力 信息论认为：若信源编码的熵大于信源的实际熵，该信源中一定存在冗余度。 原始信源的数据存在着很多冗余度：空间冗余、时间冗余、视觉冗余、听觉冗余等。
3.1.1 数据冗余的类型 ?空间冗余：在同一幅图像中，规则物体和规则背景的表面物理特性具有相关性，这些相关性的光成像结果在数字化图像中就表现为数据冗余。 –一幅图象中同一种颜色不止一个象素点，若相邻的象素点的值相同，象素点间（水平、垂直）有冗余。 –当图象的一部分包含占主要地位的垂直的源对象时，相邻 线间存在冗余。
3.1.1 数据冗余的类型 ?时间冗余：时间冗余反映在图像序列中就是相邻帧图像之间有较大的相关性，一帧图像中的某物体或场景可以由其它帧图像中的物体或场景重构出来。 –音频的前后样值之间也同样有时间冗余。 –若图象稳定或只有轻微的改变，运动序列帧间存在冗余。
一、 名词解释 1、数据压缩：以最小的数码表示信源所发的信号，减少容纳给定消息集合或数据采样 集合的信号空间 2、数据压缩比： 将压缩前每个信源符号（取样）的编码位数（m log ）与压缩后平均每符号的编码位数（l ） 之比，定义为数据压缩比 3、均匀量化：把输入信号的取值域按等距离分割的量化称为均匀量化 4、最优量化（MMSE 准则）：使均方误差最小的编码器设计方法称为最小均方误差 （MMSE ）设计。以波形编码器的输入样值k x 与波形解码器的输出样值k y 之差 k k k y x e -=的均方误差{}22k e e E =σ 作为信号质量的客观评判标准和MMSE 的设计准则。 （能使量化误差最小的所谓最佳量化器，应该是非均匀的。） 5、信息熵定义：信息量的概率平均值，即随机变量)(j a I 的数学期望值，叫做信息熵 或者简称熵 6、统计编码定义：主要利用消息或消息序列出现概率的分布特性，注重寻找概率与码 字长度间的最优匹配，叫做统计编码或概率匹配编码，统称熵编码。 7、变长编码： 与等长编码相对应，对一个消息集合中的不同消息，也可以用不同长度 码字来表示，这就叫做不等长编码或变长编码。 8、非续长码： 若W 中任一码字都不是另一个码字的字头，换句换说，任何一个码字 都不是由另一个码字加上若干码元所构成，则W 称为非续长码、异字头码或前缀码。 9、游程长度：是指字符（或信号采样值）构成的数据流中各字符重复出现而形成字符 串的长度 10、电视图像的取向：我国彩色电视制式采用逐行倒相的PAL-D 制。 11、HVS 的时间掩蔽特性：指随着时间变化频率的提高，人眼对细节分辨能力下降的 特性 12、空间掩蔽特性：指随着空间变化频率的提高，人眼对细节分辨能力下降的特性 13、亮度掩蔽特性：指在背景较亮或较暗时，人眼对亮度不敏感的特性 14、CIF 格式：是常用的标准图像格式。是一种规范Y 、B C 、R C 色差分量视频信号 的像素分辨率的标准格式。288352?=CIF 像素。 15、SIF 格式:是一种用于数字视频的存储和传输的视频格式。 16、压扩量化：由于低电平信号出现概率大、量化噪声小；高电平信号虽然量化噪声变 大，但因为出现概率小，总的量化噪声还是变小了，从而提高量化信噪比。这种方法叫做压 缩扩张量化。（压扩量化用一个非线性函数变换先将信号“压缩”后再均匀量化，它和非线 性量化器完全等效。） 17、信号压缩系统的复杂度：指实现编解码算法所需的硬件设备量，典型地可用算法的 运算量及需要的存储量来度量。 18、离散信源：被假设为由一系列随机变量所代表，往往用随机出现的符号表示，称输 出这些符号集的源为信源，如果取值于某一离散集合，就叫做离散信源。 19、互信息量：对两个离散随机时间集X 和Y ，事件j y 的出现给出关于i x 的信息量，即为互信息量。 20、联合熵：两个变量 和 的联合熵定义为：∑∑==-=m j n k k j k j b a P b a P Y X H 11)(log ),()(，即平均互信息量表示信源X 的平均不确定性与 其在信源Y 被确定条件下仍保留的平均不确定性之差。（联合熵是联合概率分布所具有信息 量的概率平均值，表示两个事件集联合发生时所能得到的总的平均信息量。） 21、极限熵：如果把n 个信源符号当作一个n 维随机矢量X 。n 越大，所得到的熵就 越接近于实际信源所含有的熵，而式 ),,,()(121lim lim -∞ →∞→=n n n n n X X X X H X H ，称为极限熵或极限信息量，用∞H 表示。
实验六 压缩试验(快速法) 1 试验目的 测定土的湿密度、含水率，计算土样干密度、初始孔隙比，并用此密度、含水率条件下的试样进行压缩试验，根据试验数据绘制孔隙比与压力的关系曲线（即压缩曲线），确定土的压缩系数、压缩模量，评价土体的压缩性。 ⑴掌握以磅秤式(或杠杆式)加压设备测定土压缩系数的方法，并根据试验数据绘制孔隙比与压力的关系曲线（即压缩曲线）； ⑵根据求得的压缩系数21-a 评定土的压缩性。 2 试验方法 ⑴密度试验——环刀法； ⑵含水率试验——烘干法； ⑶压缩试验——快速固结试验法。 3 试验原理 土样在外力作用下便产生压缩，其压缩量的大小是与土样上所加的荷重大小以及土样的性质有关。如在相同的荷重作用上，软土的压缩量就大，而坚密的土则压缩量小；又如在同一种土样的条件下，压缩量随着荷重的加大而增加。因此，我们可以在同一种土样上，施加不同的荷重，一般情况下，荷重分级不宜过大。视土的软硬程度及工程情况可取为12.5、25、50、100、200、300、400、600、800 kPa 等。最后一级荷重应大于土层计算压力的100～200kPa 。这样，便可得不同的压缩量，从而可以算出相应荷重时土样的孔隙比。如图6-1可见，当土样在荷重P 1作用下，压缩量为h ?。一般认为土样的压缩主要由于土的压密使孔隙减少产生的。因此，与未加荷前相比，可得：10e e h -=?。 而土样在荷重P 1作用下产生的应变为 h h ?= ε，从图6-1可得： ) 1(100 100 1 00e h h e e e e e h h +?=-+-=? 式中：1e ——在荷重P 1作用下，土样变形稳定时的孔隙比； 0e 、0 h ——分别为原始土样的孔隙比和高度； h ?——在荷重P 1作用下，土样变形稳定时的压缩量。
单项选择题： 1.地理信息系统形成于20世纪：（B ） A．50年代 B．60年代 C.70年代 D.80年代 2．地理信息区别与其他信息的显著标志是（ D ） A．属于属性信息 B．属于共享信息 C．属于社会经济信息 D．属于空间信息 3.对一幅地图而言，要保持同样的精度，栅格数据量要比矢量数据量（ A ） A．大 B.小 C.相当 D.无法比较 4.有一点实体其矢量坐标为P（9.5，1 5.6），若网格的宽与高都是2，则P 点 栅格化的行列坐标为：（ B ） A. P（5，8） B.P（8，5） C. P（4，7） D. P（7，4） 5.“3S”技术指的是：（ A ） A．GIS、RS、GPS B．GIS、DSS、GPS C．GIS、GPS、OS D．GIS、DSS、RS 6.地理决策问题属于：（ B ） ．半结构化决策结构化决策 BA． ．以上都不是．非结构化决策 DC（ D ） 7.对数据文件操作，进行数据记录的交换都要经过： ．缓冲区．GIS软件 D．软盘 A B．用户区 C（ C 获取栅格数据的方法 有：） 8. ．屏幕鼠标跟踪数字化法 A．手扶跟踪数字化法 B C．扫描数字化法 D．人工读取坐标法（9.矢量结构的特点是： A ） B．定位明显、属性明显A．定位明显、属性隐含．定位隐含、属性隐含C．定位隐含、属性明显 D（ 10.下列栅格结构编码方法中，具有可变分辨率和区域性质的是 D ） B．链码 A．直接栅格编码．四叉树编码 D C．游程编码（ B 11.带有辅索引的文件称为：） ．倒排文件 B A．索引文件．随机文件 C．顺序文件 D（中组织属性数据，应用较多的数据库模型是： A ） 12.在GIS A．关系模型 B．层次模型．混合模型 C．网状模型 D（ C ）下列属于13.GIS输入设备的是：．显示器 C A．主机 B．绘图机．扫描仪 D（14.质心量测可用于： D ） B．缓冲区分析．人口变迁分析 A ．人口分布 C．人口预测 D （15.用数字化仪数字化一条折线，合适的操作方式为： A ） ．连续流方式．开关流方式 A．点方式 B C D．增量方式（ D 在数据采集与数据应用之间存在的一个中间环节是：） 16. ．数据变换 C D．数据处理．数据压缩数据编辑．A B（ 17.“二值化”是处理何种数据的一个技术步骤： A ） D．属性数据．关系数据．矢量数据扫描数据．A B C（ D ） 18.对于离散空间最佳的内插方法是： B．局部内插法．整体内插法 A D．移动拟合法．邻近元法 C ：DEM下列给出的方法中，哪项适合生 成19.） A （．多边形环路法 B．等高线数字化法 A． C．四叉树法 D．拓扑结构编码法 20.提取某个区域范围内某种专题内容数据的方法是：（ C ） A．合成叠置 B．统计叠置 C．空间聚类 D．空间聚合
材料的拉伸压缩实验 【实验目的】 1．研究低碳钢、铸铁的应力——应变曲线拉伸图。 2．确定低碳钢在拉伸时的机械性能（比例极限R p、下屈服强度R eL、强度极限R m、延伸率A、断面收缩率Z等等）。 3. 确定铸铁在拉伸时的力学机械性能。 4.研究和比较塑性材料与脆性材料在室温下单向压缩时的力学性能。 【实验设备】 1.微机控制电子万能试验机； 2.游标卡尺。 3、记号笔 4、低碳钢、铸铁试件 【实验原理】 1、拉伸实验 低碳钢试件拉伸过程中，通过力传感器和位移传感器进行数据采集，A/D转换和处理，并输入计算机，得到F-?l曲线，即低碳钢拉伸曲线，见图1。 对于低碳钢材料，由图1曲线中发现OA直线，说明F正比于?l，此阶段称为弹性阶段。屈服阶段（B-C）常呈锯齿形，表示载荷基本不变，变形增加很快，材料失去抵抗变形能力，这时产生两个屈服点。其中，B'点为上屈服点，它受变形大小和试件等因素影响；B点为下屈服点。下屈服点比较稳定，所以工程上均以下屈服点对应的载荷作为屈服载荷。测定屈服载荷Fs时，必须缓慢而均匀地加载，并应用σs=F s/ A0（A0为试件变形前的横截面积）计算屈服极限。 图1低碳钢拉伸曲线 屈服阶段终了后，要使试件继续变形，就必须增加载荷，材料进入强化阶段。
当载荷达到强度载荷F b后，在试件的某一局部发生显著变形，载荷逐渐减小，直至试件断裂。应用公式σb=F b/A0计算强度极限（A0为试件变形前的横截面积）。 根据拉伸前后试件的标距长度和横截面面积，计算出低碳钢的延伸率δ和端面收缩率ψ，即 % 100 1? - = l l l δ，% 100 1 0? - = A A A ψ 式中，l0、l1为试件拉伸前后的标距长度，A1为颈缩处的横截面积。 2、压缩实验 铸铁试件压缩过程中，通过力传感器和位移传感器进行数据采集，A/D转换和处理，并输入计算机，得到F-?l曲线，即铸铁压缩曲线，见图2。 对铸铁材料，当承受压缩载荷达到最大载荷F b时，突然发生破裂。铸铁试件破坏后表明出与试件横截面大约成45?～55?的倾斜断裂面，这是由于脆性材料的抗剪强度低于抗压强度，使试件被剪断。 材料压缩时的力学性质可以由压缩时的力与变形关系曲线表示。铸铁受压时曲线上没有屈服阶段，但曲线明显变弯，断裂时有明显的塑性变形。由于试件承受压缩时，上下两端面与压头之间有很大的摩擦力，使试件两端的横向变形受到阻碍，故压缩后试件呈鼓形。 铸铁压缩实验的强度极限：σb=F b/A0（A0为试件变形前的横截面积）。 【实验步骤及注意事项】 1、拉伸实验步骤 （1）试件准备：在试件上划出长度为l0的标距线，在标距的两端及中部三个位置上，沿两个相互垂直方向各测量一次直径取平均值，再从三个平均值中取最小值作为试件的直径d0。 （2）试验机准备：按试验机→计算机→打印机的顺序开机，开机后须预热十分钟才可使用。按照“软件使用手册”，运行配套软件。 （3）安装夹具：根据试件情况准备好夹具，并安装在夹具座上。若夹具已 图2 铸铁压缩曲线
数据压缩大作业——算数编码压缩与解压缩程序 姓名：杨宁 学号： 14020181051
目录 一、试验背景及目的 (3) 二、试验内容 (3) 2.1 试验步骤 (3) 2.2 试验原理 (3) 三、算法流程 (6) 3.1 编码器算法 (6) 3.2解码器算法 (6) 四、程序设计说明 (7) 五、程序压缩性能评价 (8) 5.1 data.txt文件的测试结果 (8) 5.2 textdata.txt文件的测试结果 (11) 5.3 程序压缩性能评价 (13) 六、程序源代码 (14) 七、测试数据文件 (22)
一、试验背景及目的 霍夫曼方法比香农-费诺方法更有效，但这两种方法都很少能产生最佳变长编码，仅当符号概率等于2的负整数次幂时，这些方法才能产生最佳结果（码字的平均长度等于熵）。算数编码克服了这个问题，它是把一个码字（通常较长）分配给整个输入流，而不是给各符号分别分配码字。它可以为特定序列指定码字，而又不需要为所有同一长度的序列生成代码。 算术编码逐个符号读输入流，每输入和处理一个符号，就在码字后面加上几位，因此，在算数编码中，当前区间的下限和上限随着码流长度的增大，将变得无限长。而实际上，双精度的实数也只有16位有效数字，更长精度的数无法表示，除此之外，即使有一种方法能够表示足够长的数据精度，两个很长的数进行运算，花费的时间也无法承受。因此，一个实用的方案应当采用有限长度的整数运算，利用有限字长寄存器来实现算数编码，该方法即为整数算数编码。 本实验的目的即根据算数编码的原理，利用二进制定点数法编写算数编码压缩及解压缩程序，实现对*.txt文件的压缩及解压缩，并对程序压缩性能进行评价，从而加深对算数编码原理的理解，掌握相关算法的设计方法以及进一步提高程序编写的能力。 二、试验内容 2.1 试验步骤 根据试验目的，本次试验的具体步骤如下： ○1参考相关资料对算数编码的原理进行分析与理解， ○2根据其原理，利用二进制定点数法设计符合要求的算法， ○3根据所设计的算法，利用C语言编写相关程序， ○4利用测试数据文件对程序进行测试，并对程序的压缩性能进行评价。 2.2 试验原理 2.2.1 编码器的实现
院系：计算机学院 实验课程：实验3 实验项目：文本压缩与解压 指导老师： 开课时间：2010 ～ 2011年度第 1学期专业： 班级： 学生： 学号：
一、需求分析 1.本程序能够实现将一段由大写字母组成的内容转为哈弗曼编码的编码功能以及将哈弗曼编码翻译为字符的译码功能。 2.友好的图形用户界面，直观明了，每一个操作都有相应的提示，用户只需按着提示去做，便能轻松实现编码以及译码的效果，编码及译码结果都被保存成txt 文档格式，方便用户查看。 3.本程序拥有极大的提升空间，虽然现在只能实现对大写字母的译码以及编码，但通过改进鉴别的算法，即能够实现小写字母乃至其他特殊符号等的编码。 4.本程序可用于加密、解密，压缩后文本的大小将被减小，更方便传输 5.程序的执行命令包括： 1）初始化 2）编码 3）译码 4）印代码文件 5）印哈弗曼树 6）退出 6.测试数据 （1）THIS PROGRAM IS MY FAVOURITE （2）THIS IS MY FAVOURITE PROGRAM BUT THE REPORT IS NOT 二、概要设计 为实现上述功能，应有哈弗曼结点，故需要一个抽象数据类型。 1.哈弗曼结点抽象数据类型定义为： ADT HaffTree{ 数据对象：HaffNode* ht，HaffCode* hc 基本操作： Haffman(int w[],int n) 操作结果：构造哈弗曼树及哈弗曼编码，字符集权值存在数组w，大小为n setdep() setdep(int p,int l) 操作结果：利用递归，p为哈弗曼节点序号，l为哈弗曼节点深度setloc() 操作结果：设置哈弗曼节点坐标，用以输出到界面 setloc2() 操作结果：设置哈弗曼节点坐标，用以输出到文本，默认状态下不启用 } ADT HaffTree 2.本程序包含4个模块 1）主程序模块： 接受用户要求，分别选择执行①初始化②编码③译码④印代码文件⑤印哈弗曼树⑥退出 2）哈弗曼树单元模块——建立哈弗曼树 3）哈弗曼编码单元模块——进行哈弗曼编码、译码 4）响应用户操作，输出内容到界面或文本 各模块之间的关系如下：
天津工业大学（2013—2014学年第一学期） 研究生《数据压缩》参考试卷 特别提示：请在密封线左侧的指定位置按照要求填写个人信息，若写在其它处视为作弊。本试卷共有3页，共七道大题，请核对后做答，若有疑问请与监考教师联系。祝同学们考出好成绩！ 1.对于信源X 1/161/81/161/41/81/41/8=? ??? ， 若每个符号的出现是独立的，其熵是_______。 2.数据压缩的一般步骤包括:建模表达、_________和__________。 3.对于离散无记忆信源，无失真编码的平均码长l ____H(x) (注：请选 >≥<、、或≤)。 4.运动补偿帧间隔预测的技术组成主要有：图像分割、__________、_________和预测信息编码。 5.非均匀量化是按照信号幅值大小来确定量化间隔，当信号幅值大时其量化间隔_________，当信号幅值小时其量化间隔_______。
6.非压缩后的文件能否准确恢复原文件为界限，将压缩编码技术分为_________和_________。 7.语音信号分帧编码处理，是依据信号的__________________。 8.人讲话时产生的两种类型的声音是__________和___________。 9.彩色电视信号传输中，将R 、G 、B 格式的图像转化成Y 、U 、V 格式的图像，是为了___________和____________。 https://www.doczj.com/doc/4614812827.html,ITT 推荐的G722标准为_______，它将音频信号的带宽从________提高到__________，保证了传输信号的质量。 11.JEPG 压缩编码算法的主要步骤是:①DCT 变换，②量化，③Z 字形编码， ④使用DPCM 对直流系数（DC ）进行编码, ⑤使用RLE 对交流系数（AC ）进行编码，⑥熵编码。假设计算机的精度足够高，在上述计算方法中，___________对图像的质量是有损的，___________对图像的质量是无损的。（填写序号） 简答题（每题5分） 二、 1、简单对编码器进行数学描述，并说明码字和码元的含义。 2、简单描述视频信号中存在的冗余度。（每种冗余度后面要有简单的描述） 3、简要描述下正交变换实现数据压缩的物理本质。 4、画出自适应差分脉冲编码调制（ADPCM ）的编码方框图，并说明编码原理。 计算题（每题5分） 三、 1、黑白电视信号的带宽大约为5MHz ，若按256级量化。计算按奈奎斯特准则取样时的数据速率。如果电视节目按25帧/s 发送，则存储一帧黑白电视节目数据需要多大的内存容量. 2、一幅图像输入的亮度x 服从均匀分布())1M L p x a a =-，对其进行最佳量化，求判决电平和输出量化值得表达式。
数据结构与程序设计实验实验报告 哈尔滨工程大学
实验报告四 一、问题描述 哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树， 并将该哈夫曼树保存到文件HufTree.dat 中。 根据哈夫曼树（保存在HufTree.dat 中）对每个字符进行哈夫曼编码，并 将字符编码保存到HufCode.txt 文件中。 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件Code。 解压：将Code 文件利用哈夫曼树译码解压，恢复为源文件。 二、数据结构设计 由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。 1.使用结构体数组统计词频，并存储: typedef struct Node{ int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }LeafNode[N]; 2.使用结构体数组存储哈夫曼树: typedef struct{ unsigned int weight;//权值 unsigned int parent, LChild, RChild; }HTNode,Huffman[M+1]; //huffman树 3.使用字符指针数组存储哈夫曼编码表： typedef char *HuffmanCode[2*M]; //haffman编码表 三、算法设计 1.读取文件，获得字符串 void read_ const *, char *ch){ FILE *in_file = Fopen(, "r"); unsigned int flag = fread(ch, sizeof(char), N, in_file); if(flag == 0){ printf("%s读取失败\n", ); fflush(stdout); } printf("读入的字符串是: %s\n\n", ch); Fclose(in_file); int len = strlen(ch);
压缩技术Compression Techniques基本的压缩技术有： 空格压缩(Null Compression) 将一串空格用一个压缩码代替，压缩码后面的数值代表空格的个数。 游长压缩(Run-Length Compression)它是空格压缩技术的扩充，压缩任何4个或更多的重复字符的串。该字符串被一个压缩码、一个重复字符和一个代表重复字符个数的值所取代。关键字编码(Key-word encoding）创建一张由表示普通字符集的值所组成的表。频繁出现的单词如for、the或字符对如sh、th，被表示为一些标记（token），用来保存或传送这些字符。 哈夫曼统计方法(Huffman statistical method）这种压缩技术假定数据中的字符有一个变化分布，换句话说，有些字符的出现次数比其余的多。字符出现越频繁，用于编码的位数就越少。这种编码方案保存在一张表中，在数据传输时，它能被传送到接收方调制解调器使其知道如何译码字符。 因为压缩算法是基于软件的，所以实时环境中，存在着额外开销，会引起不少问题。而文件备份、归档过程中的压缩不会有什么问题。使用高性能的系统有助于消除大部分的额外开销和性能问题。另外，压缩消除了文件的可移植性，除非解压缩软件也与文件一起传送。 注意，有些文件已经被压缩，进一步的外部压缩不会有任何好处，一些图形文件格式，如标签映象文件格式（TIFF），就已经包含了压缩。 存储系统压缩Storage System Compression存储系统压缩 在讨论文件存储的压缩算法之前，应该明确文件压缩不同于磁盘编码。磁盘编码通常由磁盘驱动器把更多的数字1和0写到磁盘的物理表面上。文件压缩把文件中的字符和位串挤压到更小的尺寸。它在文件信息传送到硬盘驱动器的写头之前由软件完成。现代的使用编码的硬盘驱动器只是从CPU接收1和o的位流，并且把它们压挤到比没有使用编码小得多的空间中。磁盘编码简单讨论到这儿，下面将着重讨论文件压缩。 磁盘记录系统如硬盘驱动器通过改变磁盘表面的磁场来记录信息。两种可能状态间的磁场变化称为磁通翻转（flux transition）。简单地说，磁通翻转代表数字1，磁通不翻转代表数字0。编码提供了一种方法使每个磁通翻转代表更多数字信息。改进调频制 MFM(Modified frequency modulation）将一个磁通翻转表示多个1，将磁通不翻转表示多个0。编码技术包括下述几种。 游长受限码（Run Length limited(RLU））把位组合格式表示为代码，可以用较少的磁通翻转来存储。与MFM相比，存储容量提高了50%。 改进的游长受限码（Advanced run length limited(ARLL) 通过把位组合格式转换成能用四倍密度磁通翻转来存储的代码，从而把MFM的记录密度翻了一倍。 因为磁盘编码是由硬盘驱动器在硬件级自动处理的，这里没有必要进一步讨论。当你购买一个硬盘驱动器，它使用一种编码方案而获得一定的容量，但是只要驱动器的容量满足你的要求，购买后，就不必关心它的编码方案了。 文件压缩文件压缩的实现有几种方式，提供的各种工具使你能每次压缩一个文件，或压缩一组文件。一组文件能压缩成单个文件，更易于传送到其它用户，解压缩工具把文件解开。一个流行的共享文件压缩工具称为PKZIP（威斯康辛州Glendale的PKWARE公司），