關(guān)于游程編碼的編碼方法探究

蔡春梅

遵義師范學(xué)院計算機(jī)與信息科學(xué)學(xué)院，貴州遵義 563002

0 引言

21 世紀(jì)是信息高度集中的時代，人們不再生活在以前那種只有文字沒有聲音的“啞巴”時代，計算機(jī)要處理聲、文、圖等大量信息，信息的海量性與廣泛性便成為了人們處理信息的當(dāng)務(wù)之急，如何將信息快速準(zhǔn)確地傳輸，成為人們關(guān)注的焦點(diǎn)，于是編碼論由此誕生。

編碼論指出：編碼的目的是為了優(yōu)化系統(tǒng)，而編碼通常是通過壓縮信源的冗余度來實現(xiàn)。香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼及游程編碼都是常用的無失真編碼方法。前三種編碼方法適用于無記憶信源，此時編碼效率較高，當(dāng)信源是有記憶信源時，采用前三種編碼方法效率并不高，此時，我們可以采用游程編碼方法。

1 游程編碼方法簡介

游程編碼（Run Length Encoding，RLE）是一種對相關(guān)信源較為有效的擴(kuò)展符號集的編碼方法，是哈夫曼編碼的改進(jìn)和應(yīng)用，主要用于只有黑、白二值灰度的文件傳真，如文件、報紙、表格、手寫體字、圖紙等。

游程編碼的基本思想：假設(shè)有要傳輸?shù)囊桓膘o態(tài)圖像，在這幅圖像中具有許多顏色相同的圖塊（如：一行上有許多連續(xù)的像素都具有相同的顏色，甚至許多行上的顏色都相同），那么在傳輸過程中存儲色彩時，對于連續(xù)相同的顏色，只需存儲一個像素的顏色，然后將具有相同顏色的像素的個數(shù)或行數(shù)存儲下來，以達(dá)到壓縮數(shù)據(jù)的目的。

2 游程編碼的編碼方法

根據(jù)游程編碼的基本思想可知，游程編碼主要用于黑白二值灰度的文件傳真。如果我們用0 來表示白，用1 來表示黑，那么對于一個黑白二值灰度的文件，每個掃描行均是有若干個連續(xù)白（0）像素序列及若干個連續(xù)黑（1）像素序列組合而成，由于色彩單一，這樣掃描完成后，同類像素連續(xù)出項的概率很大，最終這個文件的信息就可以轉(zhuǎn)化成用像素的類別加重復(fù)次數(shù)來表示，而使得傳輸?shù)臄?shù)據(jù)量大大減少。

所謂游程是指數(shù)字序列中連續(xù)出現(xiàn)的相同符號的一段，而游程長度是指重復(fù)出現(xiàn)這個符號的長度。如果連續(xù)出現(xiàn)的符號式“0”，我們稱為“0”游程，游程長度用L(0)表示；如果連續(xù)出現(xiàn)的符號是“1”，則稱為“1”游程，游程長度用L(1)表示。那么游程游程編碼的過程可描述為：首先測定“0”游程長度和“1”游程長度的概率分布，即以游程長度為元素，構(gòu)造一個新的信源，然后在對這個新信源進(jìn)行哈夫曼編碼。

設(shè)二元獨(dú)立序列中“0”符號和“1”符號出現(xiàn)的概率分別是p0和p1，則“0”游程長度L(0)的概率為：

則“0”游程長度序列的熵：

“0”游程的平均長度：

“1”游程的平均長度：

根據(jù)編碼效率的定義和以上計算得到的該二元序列游程編碼的編碼效率為：

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

綜上所述，在游程編碼的過程中，當(dāng)“0”游程與“1”游程的編碼效率都比較高時，這個序列的編碼效率也會比較高，至少不會低于兩個游程中編碼較低的那個效率。所以要想游程的整體編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程的編碼效率。

3 結(jié)論

在編碼理論中，游程編碼是一種常用的統(tǒng)計編碼方法，其編碼過程是是將一串連續(xù)的相同數(shù)據(jù)轉(zhuǎn)化為特定的格式達(dá)到壓縮數(shù)據(jù)量的目的。通過本文分析，游程編碼是一種實現(xiàn)起來簡單、還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同的無損壓縮技術(shù)。同時，游程編碼是一種連續(xù)精確地編碼，在傳輸過程中，如果其中一位符號發(fā)生錯誤，則整個編碼序列會受到影響，使得游程編碼最終無法無失真地完全恢復(fù)原始數(shù)據(jù)。

通過對游程編碼的分析，由于其編碼原理的限制，得出RLE 所能獲得的壓縮比有多大，最終還是主要取決于圖像本身的特點(diǎn)。如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高；反之，壓縮比就越小。對于重復(fù)色彩特別少的圖像，如果仍然使用RLE 編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大。

[1]陳運(yùn).信息論與編碼.北京：電子工業(yè)出版社，2009.

[2]鐘玉琢.多媒體技術(shù)基礎(chǔ)與應(yīng)用.北京：清華大學(xué)出版社，2008.

[3]傅祖蕓.信息論與基礎(chǔ).北京：電子工業(yè)出版社，2006.

[4]朱雪龍.應(yīng)用信息論基礎(chǔ).北京：清華大學(xué)出版社，2001.

[5]丁曉明.信源編碼原理.北京：人民郵電出版社，2003.