行程编码压缩实验

陈凯

行程编码的原理很容易理解，在一幅图像中，常常有连续出现相同颜色像素的情况，所以可以用一个数字值代表连续出现该颜色像素的个数，再用一个值代表颜色。举一个简单的例子，aaabbcccccdeee可以表示为3a2b5c1d3e，这里用一个ASCII码的十进制数表示连续符号的个数，用另一个ASCII码表示颜色，至于具体是什么颜色，当然还需要另外规定。本文以XPM格式的图片作为行程编码压缩实验的对象，这样做的好处是：第一，因为XPM格式图像是使用ASCII码符号编制而成的，在实施压缩实验时，得以回避二进制数据的存储问题；第二，在XPM图像文件中，可规定不使用数字符号来代表颜色，这样在解压缩时就不会产生混淆，如888a一定代表了888个a，而不是8个“8”和8个“a”；第三，可以直接用写字板观察编码调整的效果。

与上一期的文章一样，本文仍使用二色的XPM格式的蒙娜丽莎图片来做压缩实验，用写字板打开XPM格式的蒙娜丽莎图片文件，抽出《蒙娜丽莎》图像文件点阵中的某一行来说明问题，其实与上一期文章所处理的数据完全相同：“`````````````````................``````..```.....````````````````````````````............................”（如图1）。

但这次并不是纯手工压缩，而是要体验计算机对数据自动化进行行程编码的过程。例如，这串符号一开始是17个反引号，可以表示为“17`”，其后是16个点，可以表示为“16.”，以此类推，对应的行程编码是“17`16.6` 2.3`5.28`28.”。那么，怎么才能让计算机自动把17个反引号变成“17`”，把16个点变成“16.”呢？

● 最主流的方法——编写程序

很容易想到，可以编写一个计算机程序，将符号串转化为行程编码，完全自己编写代码有点耗时间，不过可以在rosettacode.org网站上搜索“Run-length_encoding”，找到各种主流程序语言下的行程编码代码。其中比较有意思的是Ruby语言，该语言本身就提供了行程编码的函数，所以要编写出行程代码的程序，只需要寥寥数行（如图2）。

如图3所示，在Ruby语言环境中实现行程编码，结果被保存在一个二维的数组中，www.tutorialspoint.com/execute_ruby_online.php网页提供了在线运行Ruby的环境。

● 最偷懒的方法——网络在线行程编码生成器

比编写程序更省事的办法，是直接使用在线的编码生成工具。例如，网址为www.mathcelebrity.com/runlencode.php的在线编码生成工具，编码速度可以说是秒杀级的（如图4）。

甚至还可以使用一款叫做look and say的小游戏来帮助实现行程编码，因为look and say的游戏规则其实和行程编码完全一致，若想知道“look and say”是什么意思，不妨到http：//www.se16.info/js/looknsay.htm网页上在线玩一回。

● 最烧脑也最锻炼思维的方法——借助电子表格

还可以借助电子表格。例如，用Excel将符号串转化为行程编码，具体实现的办法有很多种，所谓八仙过海，各显神通，十分具有探索性，下面笔者给出一个比较简单的方法：①首先把整个符号串复制到Excel中的第一行第二列，即B1单元格，注意空出第一列；②在第二行第二列，即在B2单元格中输入数字1，C2单元格中输入2，利用Excel的自动填充功能，自动生成该行后续的自然数，多一些也没关系；③在第三行第一列，即在A3单元格中输入数字1；④在第三行第二列，即在B3单元格输入公式“=IF（MID（$B1，B2，1）=MID（$B1，C2，1），A3+1，1）”，然后利用自动填充功能，自动生成该行后续单元格中的数据，公式的功能是判断相邻符号是否相同，如果相同则做累加，如不同则累加器清零；⑤在B4单元格中输入公式“=IF（B3=1，A3&MID （$B1，B2，1），""）”，将后续单元格自动填充即可（如图5）；⑥此时电子表格的第五行数据，其实就是图像的行程编码，但这些编码分散在电子表格的各列上。为了看得更清楚，可以将这一行数据复制粘贴到Word文档中，最后实施合并单元格操作并用“查找”“替换”功能删除段落符号后，就得到了图像的行程编码“17`16.6`2.3`5.28`28.”，这么一来，105个字节被压缩到了仅有20个字节，效果相当明显。

当然，利用电子表格，将以上行程编码还原为原始图像也完全没有问题，有兴趣的朋友可以自己试试。