简介
无论现在计算机和网络的速度有多快，用户始终要求更快速的体验。为了降低传输数据的容量，我们通常会对数据进行压缩。这就是计算机科学领域一直是研究和发展的焦点的原因。
数据压缩算法有很多，有些是无损的，有些是有损的，但是它们的主要目标都是降低存储空间和传输量。对于两个远距离节点之间的数据传输，这些压缩算法非常有用。也许最直观的例子就是web服务器和浏览器之间的数据传输。
在过去的几年里做了很多关于文件压缩的研究，这些研究基于客户端实现的。这样的文件有javascript、css、html和图像。实际上，服务器和客户端都具备一些数据压缩技术，例如GZIP的使用极大地降低了数据传输量。此外，还有很多的工具和技巧能够降低数据大小。
事实上，当文件在客户的虚拟机上执行时，程序员不必理会文件的具体格式如何。如此一来空格、水平制表符和换行符对于文件上下文的理解没有任何意义。这就是YUI Compressor、Google Closure Compiler等压缩工具移除那些符号的原因。当然，为了提高压缩率文件还能被进一步压缩。本篇文章暂不讨论这一点，但这表明了数据压缩算法的重要性。
如果我们使用一些数据压缩工具，效果会更好。不幸的是，事实并非如此，压缩率通常取决于数据本身。很明显，数据压缩算法的选择主要取决于数据，我们必须首先对数据进行研究。
这里我将讨论“游程编码”，它是一种十分简单的无损数据压缩算法，在某些情况下非常有用。
概述
该算法的实现是用当前数据元素以及该元素连续出现的次数来取代字符串中连续出现的数据部分。具体实现我们通过一个字符串实例来说明。
| 1 | aaaaaaaaaabbbaxxxxyyyzyx |
|---|---|
字符串长度为24，我们可以看到字符串中有很多的重复部分。使用游程算法，我们用较短的字符串后加一个计数值来替换游程对象。
| 1 | a10b3a1x4y3z1y1x1 |
|---|---|
此时字符串长度为17，大约是初始字符串长度的70%。很明显，这并不是压缩给定字符串的最佳方式。例如当字符仅出现一次时，我们并不需要其后添加“1”。在某些情况下，这种方式会增加初始字符串的长度，而这违反了我们的初衷。这样我们得到的字符串如下。
| 1 | a10b3ax4y3zyx |
|---|---|
此时字符串长度为13，是初始长度的54%！上面例子的一个变种是不对字符保持计数，而是对位置进行计数。这样原始字符串可以被压缩成下面这样。
| 1 | a0b10a13x14y18z21y22x23 |
|---|---|
使用这两种方式中的哪一个取决于我们的目标。第二种情况下，我们能够实现二分查找的优化。
显然，这个算法不仅适用于字符串。对数组也能取得很好的结果。一个典型的例子是服务器和客户机之间字符对象(JSON)的传输。特别是如果有大量重复数据序列的存在，我们能获取很好的压缩结果。
实现
下面的实现是假设我们要使用PHP编写程序对字符串进行压缩。但是这个算法本质上并没有限制我们只能压缩字符串。正如我前面所说，只要略微修改，我们就能将其用于其他数据结构。理解游程算法适用于大量重复元素序列非常重要，不管是字符元素还是数组元素。
| 12345678910111213141516171819202122232425262728293031 | $message = 'aaaaaaaaaabbbaxxxxyyyzyx';function ` run_length_encode($msg){ $i = $j =0; $prev =’’; $output =’’; while` ` ($msg[$i]) { if` ` ($msg[$i] != $prev) { if` ` ($i) $output .= $j; $output .= $msg[$i]; $prev = $msg[$i]; $j =0; } $j++; $i++; } $output .= $j; return` ` $output;}// a10b3a1x4y3z1y1x1echo run_length_encode($message);` |
|---|---|
略微优化。
| 1234567891011121314151617181920212223242526272829303132 | $message = 'aaaaaaaaaabbbaxxxxyyyzyx';function ` run_length_encode($msg){ $i = $j =0; $prev =’’; $output =’’; while` ` ($msg[$i]) { if` ` ($msg[$i] != $prev) { if` ` ($i && $j >1) $output .= $j; $output .= $msg[$i]; $prev = $msg[$i]; $j =0; } $j++; $i++; } if` ` ($j >1) $output .= $j; return` ` $output;}// a10b3ax4y3zyxecho run_length_encode($message);` |
|---|---|
最后一个小变化——现在我们存储字符位置。
| 12345678910111213141516171819202122232425 | $message = 'aaaaaaaaaabbbaxxxxyyyzyx';function ` run_length_encode($msg){ $i =0; $prev =’’; $output =’’; while` ` ($msg[$i]) { if` ` ($msg[$i] != $prev) { $output .= $msg[$i] . $i; $prev = $msg[$i]; } $i++; } return` ` $output;}// a0b10a13x14y18z21y22x23echo run_length_encode($message);` |
|---|---|
复杂性和数据压缩
我们习惯使用时间复杂度来衡量时间，通常希望能找到最快的实现方式，比如查找算法。在这里快速压缩数据并不特别重要，重要的是尽可能的无损压缩，使得输出尽可能的小。游程编码的优点在于该算法容易实现。
应用程序
在很多情况下，我们可以使用游程编码。它常用于图像压缩，特别是用于黑白图片处理时是效果非常好。这里，我将介绍上面提及的另一种应用情况。假设我们要使用JSON将大量数组数据传给我们的Ajax程序。假设这些传输数据是一些年份，例如电影首映的年份。一年内有很多电影首映，虽然数据已被排序，但实际上我们没有得到任何好处。更要命的是有大量的数据序列。这里我们可以使用游程编码。
| 1234567891011 | $data = array( 0 ` => 1991, 1 => 1991, … 2223 => 1991, 2224 => 1992, … 19298 => 1995, 19299 => 1996, …``);` |
|---|---|
正如你看到的，传输整个数组将会是一个噩梦，特别是如果网络的速度很慢。最好对数据进行压缩(例如使用PHP的json_encode)。
| 12 | // {"0":1991,"1":1991, ..., "2223":1991,"2224":1992, ..., "19298":1995,"19299":1996, ...}echo json_encode($data); |
|---|---|
运行游程编码之后，我们得到结果像以下数组一样（注意这些只是样本数据，最佳存储数据格式取决于你）。
| 123456 | $data = array( 0 ` => array(1991, 2224), 1 => array(1992, 3948), 2 => array(1995, 2398), 3 => array(1996, 3489),``);` |
|---|---|
JSON输出
| 12 | // [[1991,2224],[1992,3948],[1995,2398],[1996,3489]]echo json_encode($data); |
|---|---|
注意如果是已排序数据，我们能够获得更好的压缩结果！！！这种方式能够用于图像，图形或者地图坐标的压缩。
这是数据压缩在日常工作中有用的唯一例子。尽管服务器和客户机之间的通信可以优化和压缩，我们能够改善它。换句话说我们不能够保证对方是否支持压缩。
那么，相应的客户端必须对数据进行解压，这个过程很缓慢。在第一种情况下，我们只有时间去传输，如下面的流程图所示。
未压缩数据传输时间！
第二种情况，我们应该累加压缩，传输和解压的时间。
压缩数据传输时间！
所有这些都很重要，但总的来说数据压缩在我们日常生活中的多数情况下都很方便。
概述
在之前的文章中，我们知道了如何压缩一段重复元素组成的数据。这种压缩称为“游程编码”，该算法在无损数据压缩传输时非常方便。但问题是数据必须遵循特定格式。比如，字符串“aaaaaaaabbbbbbbb”可以被压缩成“a8b8”。此时，16个字符的字符串被压缩成4个字符，没有丢失任何信息，而长度却只有原始长度的25%。但当字符（元素）以不同方式分散时，问题就会出现。如果字符不变，但是没有连续出现，会是什么情况？如果字符串是“abababababababab”会如何？长度一样，字符一样，但是我们不能使用游程编码！确实，使用游程算法在最优情况下只能得到相同的字符串。
然而在这种情况下，我们看到另一个事实。该字符串有太多重复元素组成，尽管不是一个接着另一个。我可以使用位图压缩该字符串。也就是说我们可以使用序列中的位来保存给定元素出现的位置，这个序列可以简单地转换成一个十进制值。上例中的字符串“abababababababab”可以压缩成“1010101010101010”，即十进制数43690，甚至表示成十六进制的AAAA更好。由此这个长字符串就被压缩了。当解压（解码）消息时，我们再从十进制/十六进制转化成二进制，匹配字符的出现次数。当然，上面这个例程非常简单，假设只有一个重复字符，其余组成字符不同，像这样：“abacadaeafagahai”。那么，我们可以使用对字符“a”使用位图-“1010101010101010”，压缩后为“AAAA bcdefghi”。正如你所看到的，所有例子字符串只有16字符，这是一个限制。对变长数据使用位图有些棘手，它的解码不太容易。
从根本上来说，位图压缩保存了消息中频繁出现元素的位置！
此外，位图压缩不仅适用于字符串。也能压缩数组，对象以及任何数据。我之前帖子中的例程就很合适。我们需要使用JSON从服务器传输一个很大的数组到客户机（浏览器）。该数据非常适合于“游程编码”。假设数据不一样——不同年份的集合，这些时间以不同方式分散。
| 12345678910111213141516171819 | $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数组）。
| 1 | [1991,1992,1993,1994,1991,1992,1993,1992,1991,1991,1991,1992,1992,1991,1991,1992, ...] |
|---|---|
然而，如果使用位图压缩，我们将得到一个更短的数组。
| 123456 | $data = array( 0 ` => array(1991, '1000100011100110'), 1 => array(1992, '0100010100011001'), 2 => array(1993, '0010001000000000'), 3 => array(1994, '0001000000000000'),``);` |
|---|---|
此时的JSON如下：
| 1 | [[1991,"1000100011100110"],[1992,"0100010100011001"],[1993,"0010001000000000"],[1994,"0001000000000000"]] |
|---|---|
很明显，随着待压缩数据增加，压缩率会变得越来越好。事实上，大部分人都是从图像了解了位图压缩，因为该算法主要用于图像压缩。可想而知，在压缩黑白图像时效果会多么好（因为黑色和白色可以视为0和1）。实际上，它也被用于超过两种颜色（例如256色），压缩的程度就非常高。
实现
下面基于PHP的实现仅仅是为了阐明位图压缩算法。这个算法适用于任何数据结构。
| 123456789101112131415161718192021222324252627 | // 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图像的压缩。