计算机数据通信教程第7章 数据压缩与数据交换.ppt

第7章 数据压缩与数据交换 7.1 数据压缩 随着电子通信新应用的大量涌现，建立更快更廉价的数据发送方法的趋势也日益明显，比如光纤、高频微波和速度更快的调制解调器等。然而，某些应用无法等待这些新发明的来临，它迫使人们寻找其它快速而廉价的通信方法。 表7-1给出了一种使用0～25的5bit代码。根据这张表，发送站点用一个5 bit代码代替原来的8 bit代码，接收站点可以进行反向的转换。结果是信息照样发送出去了，而传送数据的比特数只有5n——减少了37.5%。 7.1.1 哈夫曼编码 ASCII编码和表7-1的代码有一个共同特点，即所有的字符都使用举例来说，假设表7-2显示了一个数据文件中字符的频率(即它们出现的次数的百分比)。为了让这个例子易于处理，假设只有5个字符。如果愿意的话，你也可以做一个类似的包含全部26个字母的例子。表7-3给出了这些字符的一种哈夫曼编码。注意这里说的是“一种”哈夫曼编码，因为它并不是惟一的。 图7-1显示了如何解释一个哈夫曼编码字符串的过程。当一个站点接收到比特流时，它把比特位连接起来构成一个子字符串。当子字符串对应某个编码字符时，它就停下来。在图7-1的例子中，站点在形成字符串01时停止，表明A是第一个被发送的字符。为了找到第二个字符，它放弃当前的子字符串，从下一个接收到的比特开始构造一个新的子字符串。同样，它还是在子字符串对应某个编码字符时停下来。这一次，接下来的3个比特110对应字符B。注意在3个比特都被收到之前，子字符串不会与任何哈夫曼编码匹配。这是无前缀属性决定的。站点持续该动作直到所有的比特都已被接收。图7-1的数据包含字符串ABECADBC。 下面介绍哈夫曼编码算法。创建一个哈夫曼编码可分为以下几个步骤： (1) 为每一个字符制定一个包含一个节点的二叉树。把字符的频率指派给对应的树，我们称之为树的权。 (2) 寻找权最小的两棵树。如果多于两棵，就随机选择。然后把这两棵合并成一棵带有新的根节点的树，其左右子树分别是我们所选择的那两棵树。 (3) 重复前面的步骤直到只剩下最后一棵树。 图7-2说明了怎样创建表7-3中的哈夫曼编码。其中，图(a)显示了五棵带权的单节点树。字母B和C对应的树权最小，因此我们把它们合并起来，从而得到图(b)。关于第二次合并有两种可能：把新生成的树与D合并起来，或者把A和D合并起来。我们随意地选择第一种，图(c)显示了结果。持续该过程最终将产生图(e)中的树。 7.1.2 行程编码 1．相同比特的行程 比如说，假设用4个比特表示序列的长度。考虑图7-3(a)所示的比特流。图7-3(b)显示了被发送出去的压缩流。原始流以14个0开始，因此压缩流的前4个比特为1110(14的二进制表示)。压缩流中接下来的4个比特为1001(9的二进制表示，对应第二个长度为9的序列)。在此之后有两个连续的1。然而这种技术将它们当作两个独立的1，中间隔着长度为0的零序列。因此第三组4个比特就是0000。 第四个序列有20个0，但20无法用4个比特表示。这种情况下的序列长度用两组4?bit来表示。然后把两个4 bit数字加起来得出序列的长度。在图7-3(b)中，1111(15的二进制表示)和0101(5的二进制表示)合起来表示序列的长度为20。 2．不同字符的行程 知道待处理的是相同的比特，事情就简单了，因为只知道发送序列的长度就可以了。但如果碰到不同的比特甚至字符序列，那该怎么办？在这种情况下，需要在序列长度后面发送实际的字符，例如，字符串如下： AAAAAAAAASSSSSSDDDDDDDDDDDLLLLLLLLLLMMMMMMMMMMMMMM 可以用数字和字符交替的形式发送出去，即9A6S11D10L14M。 7.1.3 相对编码 图7-4显示了其工作过程。这里用一个二维的整数数组来表示一个帧。它们是毫无意义的；只不过画起来比视频信号简单而已。第一个帧包含一些整数，第二个帧与第一个帧差别极小。 图中在第二个帧下面给出了一个包含0、1和?1的二维数组。任何位置上的0表示该位置上的元素与前一个帧相同位置上的元素相同。一个非0值表示具体的差值。因此1意味着帧的这个位置上的元素比前一个帧相同位置上的元素大1，?1则表示小1。当然，也可以用1和?1之外的值。重要的是发送出去的帧包含许多零序列，使得它们可以使用行程编码技术。 7.1.4 LZW编码 LZW压缩算法的基本思路为： (1) 为原始文本文件中的每个字母分配一个代码并存储到一个代码表中。 (2) 设置一个循环，每次从文件中获取一个字符。我们将使用一个缓冲字符串，把从文件中取出的字符连接在一起