数据压缩技术试卷.doc

数据压缩技术试卷一、 名词解释(35)(1) 压缩器（编码器）：压缩输入流中的原始数据，建立由低冗余度数据构成的输出流的程序。(2) 流（从压缩角度解释）文件：数据压缩处理中一般用“流”的概念来代替“文件”，因为压缩数据可直接传给解码器，无需成为文件再保存。(3) 压缩比：输出流的大小/输入流的大小。(4) 不可逆压缩：通过简单地舍弃一些信息来“压缩”原始数据，有时是可以接受的，这叫做不可逆压缩。(5) 算法信息容量：把某个二进制字符串Sin的复杂度定义为能生成S（如显示、打印或写进文件中）的最短的计算机程序的长度。二、 编码(102)(1) 已知一个文本符号种类为7种，第1符号出现的概率为0.25，其余依次为0.20，0.15，0.15，0.10，0.10，0.05。试用香农-费诺编码方式进行编码，并计算平均码长。解：1 0.25 1 1 :112 0.20 1 0 :103 0.15 0 1 1 :0114 0.15 0 1 0 :0105 0.10 0 0 1 :0016 0.10 0 0 0 1 :00017 0.05 0 0 0 0 :0000平均长度=0.252+0.202+0.153+0.153+0.103+0.104+0.054 =2.7位/字符1.01(2) 已知一个文本符号种类为5种，第1个符号出现的概率为0.4，其余依次为0.2，0.2，0.1，0.1。试用霍夫曼编码方式进行编码，并计算平均码长。0.601解：1 0.4 :01012 0.2 :100.413 0.2 :1110.204 0.1 :110105 0.1 :1100平均长度=0.41+0.22+0.23+0.14+0.14=2.2位/字符三、 问答题(152)(1) 为什么说任何压缩方法都有局限性？答：任何压缩方法都有局限性，它不能无失真地压缩所有长度为N的文件，因为这些文件中有些是随机的。假定存在一种算法，能无失真的压缩所有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的不同文件被压缩成较短的相同文件，这意味着该算法有失真。(2) 什么叫熵？熵的计算公式是什么？计算结果能说明什么问题？答：用概率表示的信息量叫做熵(Entropy)。熵的计算公式为：从平均意义上来说，“熵”表示一个符号所需的最少位数。四、 问答题(102)(1) 试述LZ77基本工作原理。答：LZ77是由Jacob Ziv和Abraham Lempel在20世纪70年代最早提出的滑动窗式的字符串压缩方法。其基本思想是：把已输入数据流的一部分作为字典，编码器为输入流开一个窗口，并随着字符串的编码而把窗口中数据从右移到左。因而这是一种基于滑动窗口的方法。(2) 试述自适用（即动态）霍夫曼编码方式的工作原理。答：压缩器从一棵空的霍夫曼树开始工作，对任何符号都没有分配码字。它把输入的第一个符号不经压缩地直接写进输出流，然后把它添加到树中，赋予码字。下次再见到这个码字时，就把字的当前码字写进输出流，并将其出现频率加1。解压器镜像对应压缩器的相同步骤。五、 问答题(15)设计一个标志符的RLE文本压缩系统（要求给出压缩、解压流程图，进行工作原理说明，画出界面结构等，并思考实用压缩器的结构及工作原理）。解：RLE文本压缩算法：设C为字符数目记数单元，设R为重复记数单元，CH为当前字符有效单元，SC为比较或匹配字符存放单元。C0,R 0从文本缓冲区顺序读1个字符到CH单元是文本结束符号否？Y结束NC C+1SC=CH?H?C=1?NNR4?Y按R值将SC中字符写入压缩文件SC CHR R+1YYN在压缩文件中写压缩格式内容(占3个字节)R 0