数据压缩技术试卷

《数据压缩技术试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据压缩技术试卷一、名词解释(3*5)(1)压缩器(编码器)：压缩输入流中的原始数据，建立由低冗余度数据构成的输出流的程序。⑵流(从压缩角度解释)文件：数据压缩处理中一般用“流”的概念来代替“文件”，因为压缩数据可直接传给解码器，无需成为文件再保存。(3)压缩比：输出流的大小/输入流的大小。(4)不可逆压缩：通过简单地舍弃一些信息来“压缩”原始数据，有时是可以接受的，这叫做不可逆压缩。(5)算法信息容量：把某个二进制字符串Sin的复杂度定义为能生成S(如显示、打印或写进文件中)的最短的计算机程序的长度。二、编码(

2、10仪2)(1)已知一个文本符号种类为7种，第1符号出现的概率为0.25,其余依次为0.20,0.15,0.15,0.10,0.10,0.05。试用香农-费诺编码方式进行编码，并计算平均码长。解：10.2511:1120.2010:1030.15011:01140.15010:01050.10001:00160.100001:000170.050000:0000平均长度=0.25x2+0.20x2+0」5x3+0.15x3+0」0x3+0・10x4+0.05><4=2.7位/字符(2)已知一个文本符号种类为5种，

3、第1个符号出现的概率为0.4,其余依次为0.2,0.2,0.1,O.lo试用霍夫曼编码方式进行编码，并计算平均码长。解:10.420.200.6101.0:0140.150.1J0040.20:1101:110030.21平均长度=0.4xl+0.2x2+0.2x3+0・1x4+0」x4=2.2位/字符三、问答题(15仪2)(1)为什么说任何压缩方法都有局限性？答：任何压缩方法都有局限性，它不能无失真地压缩所有长度为N的文件，因为这些文件中有些是随机的。假定存在一种算法，能无失真的压缩所有N位长的文件，长为N的文

4、件共有2“个，用该算法压缩必须得到2“个短于N的文件。那么有多少个短于N的文件呢？答案是长度为N-1的文件有2刘个，为N・2的有2旧个，等等。一直到长度为N-N=0的文件有2n_n=1个，这些文件的总数为：2n-'+2n-2+...+1=2n-1不是2n:因此至少有两个长度为N的不同文件被压缩成较短的相同文件，这意味着该算法有失真。(2)什么叫嫡？嫡的计算公式是什么？计算结果能说明什么问题？答：用概率表示的信息量叫做(Entropy)o的计算公式为：MH=-工印亦i=l从平均意义上来说，“爛”表示一个符号所需的最

5、少位数。四、问答题(10*2)(1)试述LZ力基本工作原理。答：LZ77是由JacobZiv和AbrahamLempel在20世纪70年代最早提出的滑动窗式的字符串压缩方法。其基本思想是：把已输入数据流的一部分作为字典，编码器为输入流开一个窗口，并随着字符串的编码而把窗口中数据从右移到左。因而这是一种基于滑动窗口的方法。(2)试述自适用(即动态)霍夫曼编码方式的工作原理。答：压缩器从一棵空的霍夫曼树开始工作，对任何符号都没有分配码字。它把输入的第一个符号不经压缩地直接写进输出流，然后把它添加到树中，赋予码字。下次

6、再见到这个码字时，就把字的当前码字写进输出流，并将其出现频率加lo解压器镜像对应压缩器的相同步骤。五、问答题(15‘)设计一个标志符的RLE文本压缩系统(要求给出压缩、解压流程图，进行工作原理说明，画出界面结构等，并思考实用压缩器的结构及工作原理)。解：RLE文本压缩算法：设C为字符数目记数单元，设R为重复记数单元，CH为当前字符有效单元，SC为比较或匹配字符存放单元。RLE文本解压缩算法流程:置压缩标志