關于游程編碼的編碼方法探究

蔡春梅

遵義師范學院計算機與信息科學學院，貴州遵義 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.