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

蔡春梅

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

0 引言

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

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

1 游程編碼方法簡介

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

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

2 游程編碼的編碼方法

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

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

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

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

“0”游程的平均長度：

“1”游程的平均長度：

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

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

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

3 結(jié)論

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

通過對(duì)游程編碼的分析，由于其編碼原理的限制，得出RLE 所能獲得的壓縮比有多大，最終還是主要取決于圖像本身的特點(diǎn)。如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高；反之，壓縮比就越小。對(duì)于重復(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.