第2章_2数据存储与数据压缩

1、西安交通大学 卫颜俊2013.9大学计算机基础12.2 信息的存储信息的存储 2.3 数据压缩数据压缩本章主要内容信息及其表示 信息的存储数据压缩2本讲主要内容布尔运算逻辑门电路存储器信息熵基本压缩方法多媒体的压缩351. 布尔运算取值： 0,1运算符：非 、与 & 、或 | 、异或 运算规则表： NOT AND OR XOR 非 与 或 异或6位向量布尔变量 p,q 取值0,1逻辑变量， P,Q，取值真,假， 或true,false布尔运算可以作用于单独的位，还能作用于位向量还能作用于位向量位向量：长度为w的由0，1组成的序列。位向量的布尔运算位向量的布尔运算: : 位向量对应分量的布尔运算

2、位向量对应分量的布尔运算【课堂练习2-34】已知位向量a=01101001和b=01010101，计算: a，b，a&b，ab，ab。a=10010110b=10101010 a=01101001&b=01010101 01000001 a=0110 1001| b=0101 0101 0111 1101 a=0110 1001 b=0101 0101 0011 11007【课堂练习2-34】已知位向量a=01101001和b=01010101，计算: a，b，a&b，ab，ab。a=10010110b=10101010 a=01101001&b=01010101 01000001 a=011

3、0 1001| b=0101 0101 0111 1101 a=0110 1001 b=0101 0101 0011 11008布尔运算的应用(1)(1)布尔运算表示有限集合，如：布尔运算表示有限集合，如：a=01101001 a=01101001 表示集合表示集合A=A=0 0，3 3，5 5，6 6b=01010101b=01010101表示集合表示集合B=B=0 0，2 2，4 4，6 6位向量的位向量的a,ba,b的布尔运算的布尔运算| |，& &， 对应集合的并交补对应集合的并交补(2)(2)配色配色长度为长度为3 3的的0 0，1 1序列表示一种红绿蓝三原色构成的颜色序列表示一种红

4、绿蓝三原色构成的颜色如，如，100100表示红表示红,010,010表示绿表示绿,001,001表示蓝。表示蓝。100 | 010=110 =100 | 010=110 =红红+ +绿绿= =黄黄 相加混色相加混色110&011(110&011(青青)=010=)=010=绿色绿色 相减混色相减混色100=011(100=011(青青) )，补色，补色 (3)(3)文献检索文献检索表达检索意愿表达检索意愿文献的关键词特征文献的关键词特征笔记本笔记本 电脑电脑 ； 电脑电脑 ( (笔记本笔记本) ) 笔记本笔记本-(-(电脑电脑) )布尔代数设0，1w表示长度为w由0，1组成的串的集合aw表示由

5、w个a组成的串，那么，构成布尔代数。不同的w就是不同的布尔代数102. 门电路和触发器门？一种物理器件，输入布尔值，输出为某种布尔运算的结果。门电路？实现逻辑运算的电路。门电路可以通过多种技术制造出来，如齿轮、继电器、光学器件、半导体器件等。门电路是信息存储、处理部件的基本构件。计算机中，门电路通过微电子集成电路实现。11基本的门电路-与门12基本的门电路-或门、非门或门非门非门13基本的门电路-异或门14基本门电路的国外符号 由 门电路组成触发器15触发器一个可以产生0或1输出值的电路，它会一直保持输出不变，直到外部送来一个触发脉冲使其改变成另一个值。16触发器的另外方案或门、非门组成的触发

6、器触发器的电路图触发器的电路图17触发器的应用触发器、门电路组成更复杂的电路，实现更高级的功能.18演示3 存储器的结构存储设备是用于储存信息的设备或设备。通常是将信息数字化后再以利用电、磁或光学等方式的媒体加以存储。常见的存储设备有：利用电能方式存储信息的设备如：如各式随机存取存储器（RAM）、只读存储器（ROM）等利用磁能方式存储信息的设备如：硬盘、软盘、磁带、磁芯存储器、磁泡存储器利用光学方式存储信息的设备如：CD或DVD利用磁光方式存储信息的设备如：MO（磁光盘）利用其他实体物如纸卡、纸带等存储信息的设备如：打孔卡、打孔带等19202122233 存储器的结构存储器：主存、内存主存、内

7、存外存外存内存使用了大量的半导体电路（如触发器）来构造存储器，每一个单元电路能够存储一个二进制位。这种存储器称为主存储器（main memory）或内部存储器，简称主存或内存。每每8 8位组成一个存储单元，位组成一个存储单元，8 8位称为一个字节。位称为一个字节。76543210最高有效位（第7位）最低有效位（第0位）24若干存储单元集成到一起组成内存芯片若干内存芯片集成到一个小的板子上做成内存条内存条插到主机板中，称为计算机的内存。触发器储存单元存储芯片内存条2526计算机的内存由成千上万的存储单元组成。一个存储单元可以存放？一组有意义的信息需要多少存储单元？如何存放?如何在内存中有效地存取

8、数据？【思考】要到某个住宅小区找人，需要知道什么信息才能找到他？从从0 0开始，按顺序每个存储单元有一个编号，称为地址开始，按顺序每个存储单元有一个编号，称为地址（内存地址）（内存地址）地址由地址由CPUCPU产生，产生，地址译码器确定选择的存取单元地址译码器确定选择的存取单元数据线上读出数据线上读出/ /写入数据写入数据27内存芯片的结构示意总线地址总线地址总线数据总线数据总线控制总线控制总线地址总线的条数，决定能访问的内存数地址总线的条数，决定能访问的内存数量量28主存储器的逻辑视图与编址765432100122n-22n-1地址29连续存储的数据的地址=起始地址+偏移地址随机存取inti

9、nt a10; a10; 表示能存放表示能存放1010个整数的数组个整数的数组内存中分配内存中分配4 4* *10=4010=40个字节的存储空间个字节的存储空间a0a0表示第表示第1 1个元素，个元素，aiai 表示第表示第i+1i+1元素元素intint * *p=a; pp=a; p表示表示a a的地址（第的地址（第1 1个元素的地址）个元素的地址）p+5p+5表示第表示第6 6个元素的地址个元素的地址30主存的读写特点“拷贝”读，“破坏”写存储器存取信息和仓库存取货物这两件事情，抽象后可以认为都是存取某种对象。讨论二者之间的区别。【课堂练习2-39】已知5号存储单元中存放了数值8。以下

10、两个操作有什么关系？（相同之处？不同之处？）将数值5写入6号存储单元；将5号存储单元的内容移到6号存储单元。“随机”读写主存储器对每一个存储单元编址，所以每一个存储单元都可以独立存取。为了反映这种能力，主存储器经常被称为随机存取存储器（Random Access Memory，RAM）。31内存的类型只读存储器只读存储器ROM（Read Only Memory）ROM的特点计算机中为什么需要ROM？常见ROM的种类EPROMEEPROMFLASH ROM计算机中的ROMBIOS嵌入式系统中的程序存储器USB 移动存储器（U盘）SSD（固态硬盘）RAM(Random Access Memory)

11、32常见DRAM种类目前微机中常用的DRAM都属于SDRAM（Synchronous Dynamic Random Access Memory，同步动态随机存储器）。名字中的“同步”是指SDRAM能与CPU以相同的速度同步工作。SDRAM又分为DDR2 SDRAM、DDR3 SDRAM、DDR4 SDRAM等。DDR（Double Data Rate）即双倍数据速率，意思是每个存储周期传输两或更多次的数据。DDR2的传输带宽（每秒传输数据的字节数）为640MB/s，DDR3的传输带宽为1.28GB/s，而DDR4可达到2.56GB/s。DRAM在计算机中的应用主存储器显示存储器34本节内容基本

12、压缩方法游程编码游程编码huffmanhuffman编码编码字典编码字典编码图像和音视频的压缩35引言什么是数据压缩？什么是数据压缩？为什么要压缩？为什么要压缩？数据压缩的可能性？数据压缩的可能性？信息以二进制数或二进制编码的形式在存储器中存放然而，存储器是非常有限的能否用仅可能少的空间，存放更多的信息？这就是数据的压缩问题数据压缩的本质是重新编码，使表示的信息的意义不变而使数据量减少36压缩的必要性数字电话采样频率8kHz,样本精度8位，数据率64kb/s数据率数据率比特率、数码率、码率、速率、数据率比特率、数码率、码率、速率、数据率一小时的数据量一小时的数据量64/864/8* *3600

13、=28800kB=28MB3600=28800kB=28MB数字图像30723072* *23042304* *3=20.25MB3=20.25MB广播级彩色数字电视4:2:24:2:2分量采样，采样频率分量采样，采样频率13.5/6.75/6.57Hz,13.5/6.75/6.57Hz,每样本精每样本精度度8 8位，数据率位，数据率I=(13.5+6.57+6.57)I=(13.5+6.57+6.57)* *8=216Mb/s8=216Mb/s一小时约一小时约95GB95GB的数据量的数据量高清数字电视码率码率=1280=1280* *720720* *6060* *3 3* *8=1327

14、Mb/s8=1327Mb/s卫星云图、遥感数据37压缩的可能性信息冗余空间冗余规则物体和规则背景的表面物理特性都具有相关性规则物体和规则背景的表面物理特性都具有相关性时间冗余序列图像序列图像 ( ( 如电视图像和运动图像如电视图像和运动图像 ) ) 和语音数据的前和语音数据的前后有着很强的相关性后有着很强的相关性38AA结构冗余图像中纹理结构的相似性图像中纹理结构的相似性39信息熵冗余数据携带的信息量少于数据本身视觉冗余（感官冗余）：由人的视觉特性所产生的冗余，人的视觉系统一般的分辨能力约为26灰度等级，而图像量化一般采用28灰度等级，这样的冗余就称为视觉冗余知识冗余图像的记录方式与人对该图像

15、的知识之间的差异而产生。例如 人脸的图像就有固定的结构，鼻子位于脸的中线上，上方是眼睛，下方是嘴等。我们可以构造其基本模型，并创建对应各种特征的图像库，进而图像的存储只需要保存一些特征参数，就可以大大减少数据量4041数据压缩对猜数游戏0000100400111015010211060113111742 对于乘何种交通工具来到学校可能性：火车80%，汽车10，自行车5，飞机5，船0% 0 1 2 3火车0自行车110汽车10飞机111传输传输100次，告诉次，告诉100人到校的交通方式人到校的交通方式火车的数据量火车的数据量80位，汽车位，汽车20位，自行车位，自行车15，飞机，飞机15，共，

16、共130位，平均位，平均1.3个位。个位。1.3称为平均编码长度称为平均编码长度43平均编码长度平均编码长度=(80*1+10*2+5*3+5*3)/100 =0.8*1+0.1*2+0.05*3+0.05*3 =1.344信息熵理论上，计算平均编码长度的公式叫熵2- ( )Log( )xH XP xP x（ ）对交通工具问题：对交通工具问题：02193. 1)05. 0log*05. 005. 0log*05. 01 . 0log*1 . 08 . 0log*8 . 0()(2222xH4550万字的中文书信息量有多少了？信息量信息量500000500000* *(-log(-log2 2(

17、1/500000)(1/500000) 9465784 9465784 （bitbit） 1183223.01183223.0（ByteByte）按前面的两字节编码，按前面的两字节编码，5050万汉字，数据量万汉字，数据量100100万字节，万字节，约约1M(1 000 000Byte)1M(1 000 000Byte)常用常用70007000个汉字。假如每个字出现的概率相等，那么个汉字。假如每个字出现的概率相等，那么需要多少比特表示一个汉字？（提示需要多少比特表示一个汉字？（提示 2127000213）取整取整 13位位77311.1270001log70001*7000)(2xH46如果用

18、如果用1313位编码每个汉字，位编码每个汉字，5050万字的书的数据量为万字的书的数据量为500000500000* *13/8=812 500Byte13/8=812 500Byte实际上实际上，汉字的使用不是等概率的。经过统计，使用概，汉字的使用不是等概率的。经过统计，使用概率最大的前率最大的前10%10%的汉字使用率占的汉字使用率占95%95%以上。考虑每个汉字以上。考虑每个汉字的出现概率以及上下文相关性，汉字的信息熵只有的出现概率以及上下文相关性，汉字的信息熵只有5 5比比特左右。特左右。由此，由此，5050万字的中文书的信息量大约是万字的中文书的信息量大约是250250万比特，或万比

19、特，或313K313K字节。字节。这两个数量的差距，在信息论中称作冗余度（redundancy)。 冗余度越大的信息，通过压缩能够获得好处就越大（减小存储空间和传输时间）。47信息熵的意义信息熵给出了表示信息的最小平均比特数当一种信息出现概率更高的时候，表明它被传播得更广泛，或者说，被引用的程度更高。从信息传播的角度来看，信息熵可以表示信息的价值。信息熵也可以说是系统有序化程度的一个度量。一个系统越是有序，信息熵就越低； 一个系统越是混乱，信息熵就越高。48基本压缩方法数据压缩方案有两大类无损压缩（无损压缩（lossless compresslossless compress）有损压缩（有损压

20、缩（lossylossy compress compress）无损压缩压缩过程中不丢失信息压缩过程中不丢失信息压缩率低压缩率低常用于文字信息、程序的压缩常用于文字信息、程序的压缩有损压缩压缩过程中丢失部分信息压缩过程中丢失部分信息压缩率高压缩率高常用于图像、声音、视频的压缩常用于图像、声音、视频的压缩49(1)行程长度编码(run-length encoding)【课堂练习】有字符串“aaaaaabbccccdddffffff”,请用另一种表示方法,使数据量减少,但能准确还原原来的信息。？行程编码，又称游程编码，适合于被压缩数据中重复信息较多的情况。是一种无损压缩方法是一种无损压缩方法压缩方法

21、：将一组相同的数据序列转换成一个压缩方法：将一组相同的数据序列转换成一个二元组，指出重复的成分以及在其序列中出现二元组，指出重复的成分以及在其序列中出现的次数。形式如（的次数。形式如（x x，n n）。）。50(2)Huffman编码【例】字符串“accacccbcc”中，a出现的频率为0.2，b出现的频率为0.1，c出现的频率为0.7。计算频率相关编码方法的压缩率。 解：按照一般的编码方法，三个字符需要2位二进制编码，则该字符串需要用20位二进制编码来表示。 采用频率相关编码，可将c编码为0、a编码为10、b编码为11，这样该字符串只需要用13位二进制编码来表示。 压缩比=13/20=0.6

22、5这意味着可节省35%的数据存储空间或节省35%的数据传输时间。51huffman编码算法字符串“accacccbcc”中，a出现的频率为0.2，b出现的频率为0.1，c出现的频率为0.7。用霍夫曼算法对a、b、c进行编码。c0.7a0.2b0.11初始态初始态c0.72排序排序a0.2b0.1c0.73合并排序合并排序a0.2b0.10.3c0.74合并排序合并排序a0.2b0.10.31c0.75标注标注a0.2b0.10.31最优二叉树最优二叉树0101霍夫曼编码：霍夫曼编码：c：0a：10b：11最优二叉树最优二叉树52最优二叉树树二叉树有两个叶子节点有两个叶子节点带权二叉树节点上带有

23、权值的二叉树节点上带有权值的二叉树带权路径长度最优二叉树最优二叉树给定给定n个权值（在此是指符号出现的概率）作为个权值（在此是指符号出现的概率）作为n个叶子结点，构个叶子结点，构造一棵二叉树，造一棵二叉树，若带权路径长度达到最小若带权路径长度达到最小，称这样的二叉树为最，称这样的二叉树为最优二叉树优二叉树1 . 0*22 . 0*27 . 0*1P53huffman编码编码思想：经常出现的编码较短，不常出现的编码较长经常出现的编码较短，不常出现的编码较长特点变长编码变长编码需要知道被压缩信息码元出现概率需要知道被压缩信息码元出现概率是一种频率相关的编码方法是一种频率相关的编码方法适用于文本信息

24、的压缩适用于文本信息的压缩无损压缩无损压缩传输压缩数据时需要带编码表传输压缩数据时需要带编码表54(3)字典编码压缩(dictionary encoding)【课堂练习2-44】下面是一首缺词少字的歌词，试着对它解码以恢复它的原貌。（提示：从头开始依照空白处箭头的指示，复制所指示的内容来补齐缺少的字词） 注意：请不要指望计算机也熟悉这首歌词，能够倒背如流！新年好呀，新年好呀，祝大家新年好。我们唱歌，祝大家新年好。我们跳舞，55字典编码压缩上述练习中涉及的压缩技术称为字典编码（dictionary encoding）。压缩后的信息是字典中单词的索引号。字典编码的一个实例就是字处理系统。在字处理系

25、统中。为了拼写检查，已经包含了经过精心设计的字典。每个单词可以编码成字典的一个索引号。例如，一个字处理系统中的字典包括了50000个条目，那么一个条目就可以用0-49999中的一个整数来标识。也就是说，字典中的一个词条用16位二进制就可识别。相反，如果一个单词包括6个字母，使用8位ASCII则需要48位，使用Unicode则需要96位。针对这个案例计算一下（假定原始文本采用Unicode编码）：1）如果有5000个字典条目出现在原始文本中，按每个单词包含6个字母计算，它 共有多少字节？2）用字典编码方法压缩后的文本包含多少字节？3）压缩后比压缩前缩小了多少？56字典编码压缩【课堂练习2-45】

26、下面是一首外国诗歌，其中包含了许多重复的字母组合。The RainPitter patterPitter patterListen to the rainPitter patterPitter patterOn the window pane将此诗歌按照图示方法压缩。57现在归纳一下字典编码压缩的思想在文本中查找字母组合，如果这个字母组合曾经出现过（意味着可以被索引），它将被移除并用指针/索引（就像上面练习中画出的箭头和方格）代替。在计算机上的实现？所画的指示箭头和需要参照的字符串用当前位置与参照字符串的距离和拷贝字符数来表示。例如，Pitter patter压缩后的结果为Pitter pa（

27、7，4）。其中，7表示从当前位置倒数7个字符（包括空格），4表示把从该处开始的4个字符复制到当前位置。58字典编码压缩还可以如何实现？在实际应用中，为了加快速度、提高压缩比，往往采用的并不是文本自参照方法，而是需要使用一个字典来作为文本中出现的字母或单词的参照。文本将被编码为一个包含了许多字典索引号的数字串。同时，字典也是随着编码过程的进展而不断扩充的（称为自适应字典编码）。初始字典仅包含基本字符和单词，随着压缩过程的进展，信息中包含的更长的单词会逐渐被加入字典，而新加入的单词又可用在其后的编码过程中。59字典编码压缩【例2-14】考虑压缩文本：xyx xyx xyx xyx。首先要有一个包含

28、3个条目的字典：第一个条目是x，第二个是y，第三个是空格。分别记为（1，x），（2，y）和（3，“ ”）。文本中的第1个单词xyx编码为121，这3个数字指出了文本中要参照的字典条目索引号。下一个字符是空格，所以编码扩展为1213.空格意味前3个字符形成了一个单词，于是将xyx添加到字典中作为第四个条目。 字典变成了（1，x），（2，y），（3，“ ”）和（4，xyx）。以此类推，整段文本最终编码为121343434。解压缩时，仍用原始的3条目字典，首先将起始的1213解码为xyx和一个空格。因为xyx形成了一个单词，就将其添加到字典中作为第4个条目。接着发现后面的索引4是指字典中的第4个条目

29、，于是将其解码为xyx，由此得到12134表示的是xyx xyx。按这种方法，最终将121343434解码为原始文本：xyx xyx xyx xyx。6061字典编码压缩的应用LZW（Lempel-Ziv-Welsh）压缩也称LZ压缩；RAR压缩和ZIP压缩格式的文件；图像文件，如GIF和PNG格式的文件。62差分编码压缩(differential encoding)2021-10-1763预测编码数字压缩技术工作原理：把图像按行扫描进行编码。在扫到某一像素前，可以用此像素前面的一些像素值进行预测估计，然后与实际像素值进行比较。即用实际值减去预测估值得到差值信号，再将此差值信号量化、编码和传输

30、。在接收端用量化的差值信号重建图像信号。2021-10-1764预测编码数字压缩技术原理图如下：65特点无损压缩有损压缩，有不精确的量化器存在,预测编码应用适用于动画或视频的压缩适用于动画或视频的压缩动画或视频中的连续图像帧（看成是很多连续动画或视频中的连续图像帧（看成是很多连续的数据块）之间的差别很小，帧与帧之间有很的数据块）之间的差别很小，帧与帧之间有很多重复的信息。因此只需记录连续数据块之间多重复的信息。因此只需记录连续数据块之间的差别即可，而无需记录整个数据块。的差别即可，而无需记录整个数据块。66图像和音视频的压缩1.图像压缩？【例2-15】再一次请出“a”的位图。假定编码中白色像素个数在前。在“a”的位图中，第一行包含3个白色像素，接着是4个黑色像素，然后又是3个白色像素。于是这一行被编码为（3，4，3）。其他行也用此方法进行编码， 顺利完成，似乎没有什么问题。但是认真考虑第八行的编码（注意它是以1开头的）：编码为（2，5，1，2）会出现什么问题？如何解决？用0表示开头没有白色像素！现在第八行的编码是什么？进一步思考：如果同颜色像素的个数超出了行程长度的上限，如何解决？67其他的图像压缩方法除了RLE压缩外，其他的图像压缩方法还包括GIF（用于简单图片）和JPEG（用于照片）等。GIF（Graphic Inter