资源描述：
《多媒体数据处理中几种无损压缩算法的比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、多媒体数据处理中几种无损压缩算法的比较～!!曼星星墨蚕嗣多媒体数据处理中几种无损压缩算法的比较文◎毕永成(苏州科技学院网络与教育技术中心江苏苏州)摘要:为了使大容量的多媒体数据在网络上有效的传输,必须对多媒体数据进行压缩对多媒体数据压缩中的几种无损压缩方法进行了比较,并对每种方法用一个例子说明关键词:数据压缩;霍夫曼树;LZW;二又树引言随着网络发展的速度越来越快,视频,音频的广泛应用使得大数据量的传输显得尤为重要,如何更快,更多,更好地传输与存储数据成为数据信息处理的首要问题.在压缩算法中分为无损压缩和有损压缩.相对于有损压缩来说,无损压缩的占用空间大,￡I三缩比不高,但是它100%的保存了
2、原始信息,没有任何信号丢失并且音质高,不受信号源的影响,这点是有损压缩不可比拟的.而且随着时间的推移,限制无损格式的种种因素将逐渐被消除,比如说硬盘容量的急剧增长以及低廉的价格使得无损压缩格式的前景无比光明.1,无损压缩的原理以及几种常见算法本质上压缩数据是因为数据自身具有冗余性.数据压缩是利用各种算法将数据冗余压缩到最小,并尽可能地减少失真,从而提高传输效率和节约存储空间.常见的无损压缩算法有,游长编码:香浓一凡诺算法;霍夫曼算法;LZW算法;下面详细介绍这些算法或编码步骤,并比较其优缺点.2,游长编码也叫行程编码,它是数据压缩中最简单的一种方法.它的思想是:将图像一行中颜色值相同的相邻象素
3、用一个计数值和该颜色值来代替.例如:aabbbcCCCdddddeeeeee对其进行游长编码町得2a3b4c5d6e,l口J见其效率很高.但它育两个致命缺点.一:如果图象中每两个相邻点的颜色都不同,用这种算法不但不能压缩,反而数据量会增加,例如对abcdeabcde进行编码得1a2b3c4dSe1a2b3c4d5e,可见数据量反而增加了1倍.二:容错性差.还是以aabbbccccdddddeeeeee为例,如果在第二位a出错,例如丢失了a,那么编码后结果为la3b4c5d6e,虽然只有一位发生了错误,但是在恢复数据时,将和原始数据完全不同.所以说游长编码在要压缩信息源中的符号形成连续出现片段时
4、才有效,并且它不是.c(3)a,,d(3)图1图2编码后得:a&lO,b:llO,c:O,d:111(2)b图4图5编码后得:a:lO,b:O11一种自适应的编码方式.3,香浓一凡诺算法香浓一凡诺算法由贝尔实验室的Shannon和MIT的RobertFano开发的.它的编码步骤如下:一:根据符号出现的频率对符号进行排序二:递归的把符号分成两部分,每一部分中的符号具有相似的频率,直到所有的部分只有一个符号为止.这样,就得到一颗二叉树,我们把树中的左支赋为0,把树中的右支赋为1.那么从根节点到节点的路径即为它的编码.例如:对字符串abcccd编码.进行排序后为cabd.递归过程图卜图3.应
5、当指出香浓一凡诺算法的编码结果并不是唯一的,例如在图1的时候可以交换左右子树的位置,在图3的时候也可以交换b,d的位置.香浓一凡诺算法是一种自顶向下的,非自适应的编码算法.4,霍夫曼编码霍夫曼编码主要是一个构造霍夫曼树的过程,算法见参考文献[6],它是一种自下向上的,非自适应的编码算法,其编码过程主要有读取字符串,统计各字符出现次数并排序,构造霍夫曼树以及赋值这3个步骤.例如对字符串aabccbb进行编码,先进行统计字符出现次数并排序得,a2,c2,b3构造霍夫曼树过程见图5和图6,赋值见图7.通过霍夫曼树的构造可见,编码的结果4,d(2)c0)9,/a({)}2)o/1)d(1)图3b图6
6、也不是唯一一的.另外因为符号的出现频率不能预知,需要统计和编码两次处理,所以速度较慢,无法实用.继而推出了自适应霍夫曼编码算法.5,自适应霍夫曼编码在自适应霍夫曼编码算法中,统计字符是随着数据流的到达而动态收集和更新的,字符出现的次数是基于到目前为止实际收到的字符数.在这种方式下,随着数据流的不断变化,符号的编码也会不停的改变,直到完全接收完为止,我们把这种方式叫做自适应.其编码过程主要经过仞始化,读取字符和构造自适应霍夫曼树三个部分.初始化主要是分配一些开始时候的编解码双方达成的共同的码字,比如所ACSII码.在构造自适应霍夫曼树的时候,最采用的是自顶向下的方式.构造自适应霍夫曼树主要是将字
7、符出现的次数+1,然后更新树更新树要保持一原则,即"兄弟特性".它指的是:树所有节点都要按照以字符出现次数的多少,从左到右,从下到上的顺序排列.如果违反了"兄弟特性"就要进行交换.交换的原则是:具有计数N的最远的节点将会和计数刚刚增加到N+】的节点交换.如果N不是节点,是根节点的话,那么将整个子树进行交换.我们还是以上述字符串aabccbb为例按照自顶向下的构树方式,进行自适应霍夫曼树的构建,图7
