13771145f3e96008c6455ab81c7720f8
算法科普:有趣的游程编码


在这个大数据时代,我们保存的数据量有时候往往是非常庞大的,存储它将会耗费非常多的内存,读取速度也相对减慢了。

因此常常需要对数据进行压缩编码存储,等到要用到这个数据的时候再解压缩就行,这样不仅可以节约大量的存储空间,而且节省了系统读取和反应的时间。

栅格数据压缩编码的方法有很多种,包括链式编码、行程编码、块式编码和四叉树编码。今天我们就来讲一下行程编码(也叫游程编码)。

首先从一个简单的例子开始:编码一个在 5 * 5 方块上使用三种颜色绘制的图像。

图 1

图 1

根据方块不同的颜色匹配不同的字母。这里使用 Y 代表黄色,使用 G 代表绿色,使用 B 代表蓝色。

那么,根据这样的规则,图 1 的图形编码就变成了 25 个字母,如图 2 所示。

图 2]

图 2]

接下来,我们通过使用 游程编码 的方式来表示这个图像,以便使用 25 个字符以下的字符来表示。

游程编码是一种将代码和重复的次数作为一组来编码的方法。

例如,我们可以通过将第一个 “YYYY” 的部分表示未 “Y4”,这样就可以将其 缩短两个字符

按照这种操作,图 2 的 25 个字符就能缩短为 20 个字符了。

动图 3

动图 3

这样,如果我们知道每行有 5 个方块,原始图像就可以从代码中提取出来了。这种还原的操作也就是我们俗称的 解压

当然,游程编码也不是万能的,它也有它的适用性与局限性。
图 4

图 4

观察图 4 的图像与对应的代码,可以发现:虽然使用 游程编码 使得总体的字符数减少,但对于那些不具备相同颜色的部分,在进行游程编码后,字符数反而会增加。

图 5

图 5

top Created with Sketch.