计算机算法:数据压缩之位图(2)

概述

在之前的文章中,我们知道了如何压缩一段重复元素组成的数据。这种压缩称为“游程编码”,该算法在无损数据压缩传输时非常方便。但问题是数据必须遵循特定格式。比如,字符串“aaaaaaaabbbbbbbb”可以被压缩成“a8b8”。此时,16个字符的字符串被压缩成4个字符,没有丢失任何信息,而长度却只有原始长度的25%。但当字符(元素)以不同方式分散时,问题就会出现。如果字符不变,但是没有连续出现,会是什么情况?如果字符串是“abababababababab”会如何?长度一样,字符一样,但是我们不能使用游程编码!确实,使用游程算法在最优情况下只能得到相同的字符串。

然而在这种情况下,我们看到另一个事实。该字符串有太多重复元素组成,尽管不是一个接着另一个。我可以使用位图压缩该字符串。也就是说我们可以使用序列中的位来保存给定元素出现的位置,这个序列可以简单地转换成一个十进制值。上例中的字符串“abababababababab”可以压缩成“1010101010101010”,即十进制数43690,甚至表示成十六进制的AAAA更好。由此这个长字符串就被压缩了。当解压(解码)消息时,我们再从十进制/十六进制转化成二进制,匹配字符的出现次数。当然,上面这个例程非常简单,假设只有一个重复字符,其余组成字符不同,像这样:“abacadaeafagahai”。那么,我们可以使用对字符“a”使用位图-“1010101010101010”,压缩后为“AAAA bcdefghi”。正如你所看到的,所有例子字符串只有16字符,这是一个限制。对变长数据使用位图有些棘手,它的解码不太容易。

从根本上来说,位图压缩保存了消息中频繁出现元素的位置!

此外,位图压缩不仅适用于字符串。也能压缩数组,对象以及任何数据。我之前帖子中的例程就很合适。我们需要使用JSON从服务器传输一个很大的数组到客户机(浏览器)。该数据非常适合于“游程编码”。假设数据不一样——不同年份的集合,这些时间以不同方式分散。

JSON将会对消息进行编码,编码后的消息如下(一个简单但很大的javascript数组)。

然而,如果使用位图压缩,我们将得到一个更短的数组。

此时的JSON如下:

很明显,随着待压缩数据增加,压缩率会变得越来越好。事实上,大部分人都是从图像了解了位图压缩,因为该算法主要用于图像压缩。可想而知,在压缩黑白图像时效果会多么好(因为黑色和白色可以视为0和1)。实际上,它也被用于超过两种颜色(例如256色),压缩的程度就非常高。

实现

下面基于PHP的实现仅仅是为了阐明位图压缩算法。这个算法适用于任何数据结构。

应用

当数据中有元素频繁出现时,该算法效果很好,所以你需要研究待压缩数据的本质。实际上因为这个原因,该算法通常用于PNG8或GIF图像的压缩。

1 收藏 评论

关于作者:汤晓

(新浪微博:<a href="http://weibo.com/u/2151517721">@ashiontang</a>) 个人主页 · 我的文章 · 10

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部