数据压缩技术试卷.doc

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

1、数据压缩技术试卷一、名词解释(3′×5)(1)压缩器（编码器）：压缩输入流中的原始数据，建立由低冗余度数据构成的输出流的程序。(2)流（从压缩角度解释）文件：数据压缩处理中一般用“流”的概念来代替“文件”，因为压缩数据可直接传给解码器，无需成为文件再保存。(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.25×2+0.20×2+0.15×3+0.15×3+0.10×3+0.10×4+0.05×4=2.7位/字符1.

3、01(1)已知一个文本符号种类为5种，第1个符号出现的概率为0.4，其余依次为0.2，0.2，0.1，0.1。试用霍夫曼编码方式进行编码，并计算平均码长。0.601解：10.4:010120.2:100.4130.2:1110.2040.1:1101050.1:1100平均长度=0.4×1+0.2×2+0.2×3+0.1×4+0.1×4=2.2位/字符一、问答题(15′×2)(1)为什么说任何压缩方法都有局限性？答：任何压缩方法都有局限性，它不能无失真地压缩所有长度为N的文件，因为这些文件中有些是随机的

4、。假定存在一种算法，能无失真的压缩所有N位长的文件，长为N的文件共有2N个，用该算法压缩必须得到2N个短于N的文件。那么有多少个短于N的文件呢？答案是长度为N-1的文件有2N-1个，为N-2的有2N-2个，等等。一直到长度为N-N=0的文件有2N-N=1个，这些文件的总数为：2N-1+2N-2+…+1=2N-1不是2N：因此至少有两个长度为N的不同文件被压缩成较短的相同文件，这意味着该算法有失真。(1)什么叫熵？熵的计算公式是什么？计算结果能说明什么问题？答：用概率表示的信息量叫做熵(Entropy)。

5、熵的计算公式为：从平均意义上来说，“熵”表示一个符号所需的最少位数。一、问答题(10′×2)(1)试述LZ77基本工作原理。答：LZ77是由JacobZiv和AbrahamLempel在20世纪70年代最早提出的滑动窗式的字符串压缩方法。其基本思想是：把已输入数据流的一部分作为字典，编码器为输入流开一个窗口，并随着字符串的编码而把窗口中数据从右移到左。因而这是一种基于滑动窗口的方法。(2)试述自适用（即动态）霍夫曼编码方式的工作原理。答：压缩器从一棵空的霍夫曼树开始工作，对任何符号都没有分配码字。它把输

6、入的第一个符号不经压缩地直接写进输出流，然后把它添加到树中，赋予码字。下次再见到这个码字时，就把字的当前码字写进输出流，并将其出现频率加1。解压器镜像对应压缩器的相同步骤。二、问答题(15′)设计一个标志符的RLE文本压缩系统（要求给出压缩、解压流程图，进行工作原理说明，画出界面结构等，并思考实用压缩器的结构及工作原理）。解：RLE文本压缩算法：设C为字符数目记数单元，设R为重复记数单元，CH为当前字符有效单元，SC为比较或匹配字符存放单元。C←0,R←0从文本缓冲区顺序读1个字符到CH单元是文本结束符

7、号否？Y结束NC←C+1SC=CH?H?C=1?NNR<4?Y按R值将SC中字符写入压缩文件SC←CHR←R+1YYN在压缩文件中写压缩格式内容(占3个字节)R←0,SC←CHRLE文本解压缩算法流程：清压缩标志顺序读文本字符Y结束NYNChar=’@’?输出字符Y是文本结束符号否？压缩标志清除否？置压缩标志读入N,输出N个N后相同的字符