信息管理和信息系统第4章.pptVIP

Huffman编码Huffman编码时采取从后向前推，即以概率最小的向概率大的方向进行编码处理，最后建立一颗Huffman编码树。各个符号作为二叉树的叶结点，每个节点有一个权，它是符号出现的概率。信息编码*信息编码建立Huffman编码树的步骤描述如下：将信息集合中的各信息元素按概率依次从大到小排列。使概率最小的二组信息元素分别对应于０码和１码。将这两个信息元素的概率相加，作为另一组信息元素出现的概率。再一次重新依次按概率大小排序。重复以上步骤，直到剩下最后一个元素，并将其作为树根。4.1、信息编码第四章*Huffman编码举例下面几个图可以看到Huffman编码的构造过程是一个反复比较的过程，它总是选择两个使用频率较小的结点进行合并，生成出一个树，这个树经过编码后就会得到Huffman编码。在上图中各点中的数字代表各点的使用次数，您可以把这几个方块想成A，B，C，D，它们在某一文章中的使用频率为7次，5次，1次等等。信息编码选择使用率小的两个点1，3构成新点4。信息编码在状态1图中选择5，4（也是两个最小的，注意不是1，3，因为1，3现在已经归在4里面了）进行合并。信息编码信息编码第四章*在状态2表中的最小两个点已经变为7，6了，这时合并它们两个生成新点13。只剩两个点了，不管多少它们也是最小的了，合并了算了。信息编码信息编码请注意这个编码，每个点下面有两个分枝，分别编码为0，1。至此编码结束，所得到编码即从最上面的点延线下行，至所要编码的点，将沿路经过的0和1记录下来就是了。71161050030111010信息编码01Huffman编码所以能获得高效编码，原因就在于高概率的信息元素总是取短码。由此也可以得出结论，即信源中各信息元素的概率分布越是不均匀，Huffman编码的有效性越能发挥出来。而一旦信息元素发生的概率趋于平衡，Huffman编码有效性也将随之势去。02信息压缩技术第四章*文本信息压缩技术空格压缩技术其压缩思路是压缩文本信息中连续出现的空格。具体的处理过程是扫描待压缩的原始信息，统计出其中连续出现的空格，并用一个特殊的字符和数字表示这一串连续空格，其压缩格式为：压缩指示字符用来标明在该处发生了空格压缩，而连续空格计数则表示所压缩的空格数量，这样，可以用两个字符表示原始信息中的连续空格。位图压缩技术信息压缩技术第四章*位图压缩方法是在文件中建立位图来标志某个字符的存在与否。凡在位图中标明为有效字符的位置，在压缩的文件中对应位置有相应的字符出现。在压缩后输出文件中，这个无效字符不出现，释放时再把这些无效字符按实际位置加到文件中。用位图方法压缩数据，首先要确定数据流中出现概率最大的一个字符。继而要对源数据流中字符建立位图字符，利用它标志出事先所确定的、以最大概率出现的字符位置，并将其压缩掉。信息压缩技术第四章*游程编码技术在游程编码中需要标出被压缩的字符，也即要占用3B；第一个字节是压缩指示字符；第二个字节纪录连续出现的字符；第三个字节纪录重复字符出现的次数。信息压缩技术第四章*主要用于有序信息中存在大量重复字符串的情形。前端压缩技术，即当下一个字段中有若干字符与上个字段中有重复时，则在下一个字段开头用一个数字表示重复字符数。前端/后端压缩编码技术半字压缩编码技术信息压缩技术第四章*1半字压缩是由位映像派生出来的一种压缩方法。它对数字字符串的压缩非常有效。2ASCII码的数字字符编码的前4位完全相同，也就是说，在存储数值型数据时，每个字节中有4位并不表示具体数值。利用这个特性，就可以把占2B的数字字符压缩到1B中去，即压缩掉1B中的4位，这就是半字压缩。3半字压缩也需要压缩指示字符作为标志，并有计数加以控制。*信息压缩技术多媒体信息压缩技术图像信息压缩技术概述游程长度压缩：将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。霍夫曼编码压缩，其基本原理是频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码长度各不相同。信息压缩技术数据流压缩技术COS（capacityoptimizedstorage）压缩技术的基本思想是：将数据流像积木一样，分解为一个个组件，再分解的同时产生组件组装的指令。重复的组件只保留一份，这样很多重复的数据块便被剔除，因此可以节省大量的存储空间。01024.4.1数据压缩技术概述（三）多媒体数据压缩方法的分类（1）按照压缩方法是否产生失真分类根据解码后数据与原始数据是否完全一致进行分类，压缩方法可被分为有失真编码和无失真编码两（2）按