行程編碼壓縮實驗

陳凱

行程編碼的原理很容易理解，在一幅圖像中，常常有連續出現相同顏色像素的情況，所以可以用一個數字值代表連續出現該顏色像素的個數，再用一個值代表顏色。舉一個簡單的例子，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個字節，效果相當明顯。

當然，利用電子表格，將以上行程編碼還原為原始圖像也完全沒有問題，有興趣的朋友可以自己試試。