关于游程编码的编码方法探究

蔡春梅

遵义师范学院计算机与信息科学学院，贵州遵义 563002

0 引言

21 世纪是信息高度集中的时代，人们不再生活在以前那种只有文字没有声音的“哑巴”时代，计算机要处理声、文、图等大量信息，信息的海量性与广泛性便成为了人们处理信息的当务之急，如何将信息快速准确地传输，成为人们关注的焦点，于是编码论由此诞生。

编码论指出：编码的目的是为了优化系统，而编码通常是通过压缩信源的冗余度来实现。香农编码、费诺编码、哈夫曼编码及游程编码都是常用的无失真编码方法。前三种编码方法适用于无记忆信源，此时编码效率较高，当信源是有记忆信源时，采用前三种编码方法效率并不高，此时，我们可以采用游程编码方法。

1 游程编码方法简介

游程编码（Run Length Encoding，RLE）是一种对相关信源较为有效的扩展符号集的编码方法，是哈夫曼编码的改进和应用，主要用于只有黑、白二值灰度的文件传真，如文件、报纸、表格、手写体字、图纸等。

游程编码的基本思想：假设有要传输的一副静态图像，在这幅图像中具有许多颜色相同的图块（如：一行上有许多连续的像素都具有相同的颜色，甚至许多行上的颜色都相同），那么在传输过程中存储色彩时，对于连续相同的颜色，只需存储一个像素的颜色，然后将具有相同颜色的像素的个数或行数存储下来，以达到压缩数据的目的。

2 游程编码的编码方法

根据游程编码的基本思想可知，游程编码主要用于黑白二值灰度的文件传真。如果我们用0 来表示白，用1 来表示黑，那么对于一个黑白二值灰度的文件，每个扫描行均是有若干个连续白（0）像素序列及若干个连续黑（1）像素序列组合而成，由于色彩单一，这样扫描完成后，同类像素连续出项的概率很大，最终这个文件的信息就可以转化成用像素的类别加重复次数来表示，而使得传输的数据量大大减少。

所谓游程是指数字序列中连续出现的相同符号的一段，而游程长度是指重复出现这个符号的长度。如果连续出现的符号式“0”，我们称为“0”游程，游程长度用L(0)表示；如果连续出现的符号是“1”，则称为“1”游程，游程长度用L(1)表示。那么游程游程编码的过程可描述为：首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源，然后在对这个新信源进行哈夫曼编码。

设二元独立序列中“0”符号和“1”符号出现的概率分别是p0和p1，则“0”游程长度L(0)的概率为：

则“0”游程长度序列的熵：

“0”游程的平均长度：

“1”游程的平均长度：

根据编码效率的定义和以上计算得到的该二元序列游程编码的编码效率为：

从上式分析，如果η0＞ η1，那么可得：η0＞ η ＞η1

综上所述，在游程编码的过程中，当“0”游程与“1”游程的编码效率都比较高时，这个序列的编码效率也会比较高，至少不会低于两个游程中编码较低的那个效率。所以要想游程的整体编码效率尽可能高，应尽可能提高熵值较大的游程的编码效率。

3 结论

在编码理论中，游程编码是一种常用的统计编码方法，其编码过程是是将一串连续的相同数据转化为特定的格式达到压缩数据量的目的。通过本文分析，游程编码是一种实现起来简单、还原后得到的数据与压缩前的数据完全相同的无损压缩技术。同时，游程编码是一种连续精确地编码，在传输过程中，如果其中一位符号发生错误，则整个编码序列会受到影响，使得游程编码最终无法无失真地完全恢复原始数据。

通过对游程编码的分析，由于其编码原理的限制，得出RLE 所能获得的压缩比有多大，最终还是主要取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高；反之，压缩比就越小。对于重复色彩特别少的图像，如果仍然使用RLE 编码方法，不仅不能压缩图像数据，反而可能使原来的图像数据变得更大。

[1]陈运.信息论与编码.北京：电子工业出版社，2009.

[2]钟玉琢.多媒体技术基础与应用.北京：清华大学出版社，2008.

[3]傅祖芸.信息论与基础.北京：电子工业出版社，2006.

[4]朱雪龙.应用信息论基础.北京：清华大学出版社，2001.

[5]丁晓明.信源编码原理.北京：人民邮电出版社，2003.