119摘要:为了使大容量的多媒体数据在网络上有效的传输,必须对多媒体数据进行压缩。
对多媒体数据压缩中的几种无损压缩方法进行了比较,并对每种方法用一个例子说明。
关键词:数据压缩;霍夫曼树;LZW;二叉树引言随着网络发展的速度越来越快,视频,音频的广泛应用使得大数据量的传输显得尤为重要,如何更快、更多、更好地传输与存储数据成为数据信息处理的首要问题。
在压缩算法中分为无损压缩和有损压缩。
相对于有损压缩来说,无损压缩的占用空间大,压缩比不高,但是它100%的保存了原始信息,没有任何信号丢失并且音质高,不受信号源的影响,这点是有损压缩不可比拟的。
而且随着时间的推移,限制无损格式的种种因素将逐渐被消除,比如说硬盘容量的急剧增长以及低廉的价格使得无损压缩格式的前景无比光明。
1、无损压缩的原理以及几种常见算法本质上压缩数据是因为数据自身具有冗余性。
数据压缩是利用各种算法将数据冗余压缩到最小,并尽可能地减少失真,从而提高传输效率和节约存储空间。
常见的无损压缩算法有,游长编码;香浓-凡诺算法;霍夫曼算法;LZW算法;下面详细介绍这些算法或编码步骤,并比较其优缺点。
2、游长编码也叫行程编码,它是数据压缩中最简单的一种方法。
它的思想是:将图像一行中颜色值相同的相邻象素用一个计数值和该颜色值来代替。
例如:aabbbccccdddddeeeeee对其进行游长编码可得2a3b4c5d6e,可见其效率很高。
但它有两个致命缺点。
一:如果图象中每两个相邻点的颜色都不同,用这种算法不但不能压缩,反而数据量会增加,例如对abcdeabcde进行编码得1a2b3c4d5e1a2b3c4d5e,可见数据量反而增加了1倍。
二:容错性差。
还是以aabbbccccdddddeeeeee为例,如果在第二位a出错,例如丢失了a,那么编码后结果为1a3b4c5d6e,虽然只有一位发生了错误,但是在恢复数据时,将和原始数据完全不同。
所以说游长编码在要压缩信息源中的符号形成连续出现片段时才有效,并且它不是一种自适应的编码方式。
3、香浓-凡诺算法香浓-凡诺算法由贝尔实验室的Shannon 和MIT的Robert Fano开发的。
它的编码步骤如下:一:根据符号出现的频率对符号进行排序二:递归的把符号分成两部分,每一部分中的符号具有相似的频率,直到所有的部分只有一个符号为止。
这样,就得到一颗二叉树,我们把树中的左支赋为0,把树中的右支赋为1。
那么从根节点到节点的路径即为它的编码。
例如:对字符串abcccd编码。
进行排序后为cabd。
递归过程图1-图3。
应当指出香浓-凡诺算法的编码结果并不是唯一的,例如在图1的时候可以交换左右子树的位置,在图3的时候也可以交换b,d的位置。
香浓-凡诺算法是一种自顶向下的,非自适应的编码算法。
4、霍夫曼编码霍夫曼编码主要是一个构造霍夫曼树的过程,算法见参考文献[6],它是一种自下向上的,非自适应的编码算法,其编码过程主要有读取字符串,统计各字符出现次数并排序,构造霍夫曼树以及赋值这3个步骤。
例如对字符串aabccbb进行编码,先进行统计字符出现次数并排序得,a2,c2,b3构造霍夫曼树过程见图5和图6,赋值见图7。
通过霍夫曼树的构造可见,编码的结果多媒体数据处理中几种无损压缩算法的比较文◎毕永成(苏州科技学院网络与教育技术中心江苏苏州也不是唯一的。
另外因为符号的出现频率不能预知,需要统计和编码两次处理,所以速度较慢,无法实用。
继而推出了自适应霍夫曼编码算法。
5、自适应霍夫曼编码在自适应霍夫曼编码算法中,统计字符是随着数据流的到达而动态收集和更新的, 字符出现的次数是基于到目前为止实际收到的字符数。
在这种方式下,随着数据流的不断变化,符号的编码也会不停的改变,直到完全接收完为止,我们把这种方式叫做自适应。
其编码过程主要经过初始化,读取字符和构造自适应霍夫曼树三个部分。
初始化主要是分配一些开始时候的编解码双方达成的共同的码字,比如所ACSII码。
在构造自适应霍夫曼树的时候,最采用的是自顶向下的方式。
构造自适应霍夫曼树主要是将字符出现的次数+1,然后更新树。
更新树要保持一原则,即“兄弟特性”。
它指的是:树所有节点都要按照以字符出现次数的多少,从左到右,从下到上的顺序排列。
如果违反了“兄弟特性”就要进行交换。
交换的原则是:具有计数N 的最远的节点将会和计数刚刚增加到N+1的节点交换。
如果 N不是节点,是根节点的话,那么将整个子树进行交换。
我们还是以上述字符串aabccbb为例按照自顶向下的构树方式,进行自适应霍夫曼树的构建,图7给出了在构树过程中需要交换的过程。
6、LZW编码120LZW的是一种基于字典的编码方法。
它是自适应的,压缩率高,花费时间少。
LZW编码过程如下:一:初始化编译表并定义前缀current prefix为[c],初始时为null,定义当前字符串current string为[c]k,k为当前读取字符二 :读第一个字符 p , 则 c u r r e n t string=[c]p,因为[c]=null,所以current string=p三 :在编译表中查找有没有 c u r r e n t sting值,因为p为根字符,所以可以找到四:把p设为current prefix的值,继续读取下一字符,设为q,current string为[c]q,此时current sting==pq,查看编译表中有没有,当然没有,这时候要把current string(pq加到编译表的末项,并把current prefix也就是p在编译表中的索引值输出。
并修改current prefix为当前读取字符,即q, 继续五:如果在编译表中可以查到current string的值([c]k,则把current string的值([c]k赋予current prefix,如果找不到,则添加current string的值([c]k到编译表,把current prefix的值([c]在编译表中对应的索引值输出,同时修改current prefix为k,继续,不断的重复,直到接收完字符为止。
用一个例子说明LZW的编码过程。
例如:一个字符流有四种类型的数据a,b,c,d, 现字符流为abacaba,对其进行LZW编码如下:初始化编译表为:0a,1b,2c,3d读第一个字符a,则[c]p=a,可以在编译表中找到读第二个字符b,则[c]b=ab,在编译表中找不到,则加ab到表中,此时编译表为0a,1b,2c,3d,4ab,并且输出a 的索引值0,修改[c]=b读第三个字符a,则[c]a=ba,在编译表中找不到,则加ba到表中,此时编译表为0a,1b,2c,3d,4ab,5ba,并且输出b的索引值1,修改[c]=a读第四个字符c,则[c]c=ac,在编译表中找不到,则加ac到表中,此时编译表为0a,1b,2c,3d,4ab,5ba,6ac, 并且输出a的索引值0,修改[c]=c读第五个字符a,则[c]a=ca,在编译表中找不到,则加ca到表中,此时编译表为0a,1b,2c,3d,4ab,5ba,6ac, 7ca,并且输出c的索引值2,修改[c]=a读第六个字符b,则[c]b=ab,在编译表中找到,此时[c]=ab读第七个字符a,则[c]a=aba,在编译表中找不到,则加aba到表中,此时编译表为0a,1b,2c,3d,4ab,5ba,6ac,7ca, 8aba,并且输出ab的索引值4,修改[c]=a接收结束。
编码结果为,0,1,0,2,4通过列子可见LZW 算法与其他算法相比具有自适应的特点,即可以根据压缩内容不同来建立不同字典,以减少冗余度,提高压缩比。
并且解压时这个字典无需与压缩代码同时传送,而是在解压过程中逐步建立与压缩时完全相同的字典,从而完整、准确地恢复被压缩内容。
因此,LZW算法是一种解码速度与压缩性能较好的压缩算法。
但是LZW 应用的时候应注意字典越大,代替的子串越多。
但应用中字典容量则受一定限制,要权衡利弊选择合适的字典。
当字典满时,字典的维护和更新对压缩率也是至关重要。
7、结束语需要注意的是,每种算法都有各自的优缺点,都有自己的适用范围。
在当今高要求的压缩条件下,通常的需要集成两种或者两种以上压缩算法。
例如,在winrar就应用了 LZW和霍夫曼混合编码的方法进行数据压缩。
因此,根据需要,选择合适的压缩算法至关重要。
研究在保持高压缩比,提高压缩及解压缩速度的同时保持原始数据的完整性还是一个重要的研究课题。
参考文献 [1] 许霞,马光思,鱼涛. LZW 无损压缩算法的研究与改进[J].计算机技术与发展,2009,19(4:127-127[2] Nelson M.数据压缩技术原理与范例[M].贾启东译.北京:希望出版社,1995[3] 李雷定,马铁华,尤文斌.常用数据无损压缩算法分析[J].电子设计工程, 2009,17(1:49-53[4] 闰阳,张正炳.浅谈数据压缩技术 [J].长江大学学报(自科版,2004,1(4:120-121. [5] 杨雄,李凌.数据压缩技术及其常用算法[J].软件世界,1996(9:8一l1. [6] 张广学.最优二叉树的生成及应用[J].软件技术,2008,273(10:112-114。