[算法系列之十七]数据压缩之位图

朴灿烈づ我的快乐病毒、 2023-06-15 07:10 32阅读 0赞

**概述**

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

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

![这里写图片描述][20150207130849854]  
*从根本上来说，位图压缩保存了消息中频繁出现元素的位置！*

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

$data = array(
            0 => 1991,
            1 => 1992,
            2 => 1993,
            3 => 1994,
            4 => 1991,
            5 => 1992,
            6 => 1993,
            7 => 1992,
            8 => 1991,
            9 => 1991,
            10 => 1991,
            11 => 1992,
            12 => 1992,
            13 => 1991,
            14 => 1991,
            15 => 1992, 
            ...
    );

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

[1991,1992,1993,1994,1991,1992,1993,1992,1991,1991,1991,1992,1992,1991,1991,1992, ...]

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

$data = array(
            0 => array(1991, '1000100011100110'),
            1 => array(1992, '0100010100011001'),
            2 => array(1993, '0010001000000000'),
            3 => array(1994, '0001000000000000'),
    );

此时的JSON如下：

[[1991,"1000100011100110"],[1992,"0100010100011001"],[1993,"0010001000000000"],[1994,"0001000000000000"]]

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

**实现**

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

// too many repeating "a" characters
    $msg = 'aazahalavaatalawacamaahakafaaaqaaaiauaacaaxaauaxaaaaaapaayatagaaoafaawayazavaaaazaaabararaaaaakakaaqaarazacajaazavanazaaaeanaaoajauaaaaaxalaraaapabataaavaaab';
    
    function bitmap($message) 
    {
           $i = 0;
           $bits = $rest = '';
    
           while ($v = $message[$i]) {
                  if ($v == 'a') {
                          $bits .= '1';
                  } else {
                          $bits .= '0';
                          $rest .= $v;
                  }
                  $i++;
           }
    
           return number_format(bindec($bits), 0, '.', '') . $rest;;
    }
    
    echo bitmap($msg);
    
    // uncompressed: 
    acaaaaadaaaabalaaeaaaaganaaxakaavawamaasavajawaaaayaauaaadalanagaeaeamaarafalaazaaaiasaanaahaaazaraxaalaahaaawaaajasamahaajaakarapanaakaoakaanawalaacamauaamaal
    // compressed:
    152299251941730035874325065523548237677352452096zhlvtlwcmhkfqiucxuxpytgofwyzvzbrrkkqrzcjzvnzenojuxlrpbtvb

**应用**

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

**原文链接**

[Computer Algorithms: Data Compression with Bitmaps][Computer Algorithms_ Data Compression with Bitmaps]

[Link 1]: http://blog.csdn.net/sunnyyoona/article/details/43602449
[20150207130849854]: https://img-blog.csdn.net/20150207130849854
[Computer Algorithms_ Data Compression with Bitmaps]: http://www.stoimen.com/blog/2012/01/16/computer-algorithms-data-compression-with-bitmaps/