遊程編碼

遊程編碼(RLC, Run Length Coding),又稱“運行長度編碼”或“行程編碼”,是一種統計編碼,該編碼屬於無損壓縮編碼,是柵格數據壓縮的重要編碼方法。對於二值圖有效。

遊程編碼,又稱行程長度編碼或變動長度編碼法,是一種與資料性質無關的無損數據壓縮技術。

變動長度編碼法為一種“使用固定長度的碼來取代連續重複出現的原始資料”的壓縮技術。

基本介紹

  • 中文名:遊程編碼
  • 外文名:RLC, Run Length Coding
  • 又稱:運行長度編碼
  • 屬性:是一種統計編碼
基本原理,4位元表示法,8位元表示法,壓縮策略,壓縮,解壓縮,套用,

基本原理

行程編碼的基本原理是:用一個符號值或串長代替具有相同值的連續符號(連續符號構成了一段連續的“行程”。行程編碼因此而得名),使符號長度少於原始數據的長度。只在各行或者各列數據的代碼發生變化時,一次記錄該代碼及相同代碼重複的個數,從而實現數據的壓縮。
常見的遊程編碼格式包括TGA,Packbits,PCX以及ILBM。
例如:5555557777733322221111111
行程編碼為:(5,6)(7,5)(3,3)(2,4)(1,7)。可見,行程編碼的位數遠遠少於原始字元串的位數。
並不是所有的行程編碼都遠遠少於原始字元串的位數,但行程編碼也成為了一種壓縮工具。
例如:555555 是6個字元 而(5,6)是5個字元,這也存在壓縮量的問題,自然也會出現其他方式的壓縮工具。
在對圖像數據進行編碼時,沿一定方向排列的具有相同灰度值的像素可看成是連續符號,用字串代替這些連續符號,可大幅度減少數據量。
遊程編碼記錄方式有兩種:①逐行記錄每個遊程的終點列號:②逐行記錄每個遊程的長度(像元數)
第一種方式:
A
A
A
B
B
A
C
C
C
A
這個柵格圖形就記為:
A,3,B,5
A,1,C,4,A,5
第二種就記作:
A,3,B,2
A,1,C,3,A,1
行程編碼是連續精確的編碼,在傳輸過程中,如果其中一位符號發生錯誤,即可影響整個編碼序列,使行程編碼無法還原回原始數據。
遊程長度在柵格加密時,數據量沒有明顯增加,壓縮效率較高,且易於檢索、疊加合併等操作,運算簡單,適用於機器存儲容量小,數據需大量壓縮,而又要避免複雜的編碼和解碼運算,增加處理和操作時間的情況。
舉例來說,一組資料串"AAAABBBCCDEEEE",由4個A、3個B、2個C、1個D、4個E組成,經過變動長度編碼法可將資料壓縮為4A3B2C1D4E(由14個單位轉成10個單位)。
簡言之,其優點在於將重複性高的資料量壓縮成小單位;然而,其缺點在於─若該資料出現頻率不高,可能導致壓縮結果資料量比原始資料大,例如:原始資料"ABCDE",壓縮結果為"1A1B1C1D1E"(由5個單位轉成10個單位)。

4位元表示法

顧名思義,利用4個位元來儲存整數,以符號C表示整數值。其可表現的最大整數值為15,因此,若資料重複出現次數超過15,便以“分段”方式處理。
假設某資料出現N次,則可以將其分成(N/15)+1段落來處理,其中N/15的值為無條件捨去。例如連續出現33個A:
原始資料:
AAAAAAAAAAAAAAA AAAAAAAAAAAAAAA AAA
壓縮結果:
15A 15A 3A
內部儲存碼:
1111 01000001 1111 01000001 0011 01000001
15 A 15 A 3 A

8位元表示法

同4位元表示法的概念,其能表示最大整數為255。假設某資料出現N次,則可以將其分成(N/255)+1段落來處理,其中N/255的值為無條件捨去。

壓縮策略

壓縮

先使用一個暫存函式Q讀取第一個資料,接著將下一個資料與Q值比,若資料相同,則計數器加1;若資料不同,則將計數器存的數值以及Q值輸出,再初始計數器為,Q值改為下一個資料。以此類推,完成資料壓縮。
以下為簡易的算法:
input: AAABCCBCCCCAA
for i=1:size(input) if (Q = input(i)) 計數器+1 else output的前項=計數器的值, output的下一項=Q值, Q換成input(i), 計數器值換成0 endend

解壓縮

其方法為逐一讀取整數(以C表示)與資料(以B表示),將C與B的二進制碼分別轉成十進制整數以及原始資料符號,最後輸出共C次資料B,即完成一次資料解壓縮;接著重複上述步驟,完成所有資料輸出。

套用

  • 大量白色或黑色的區域單色影像圖
  • 電腦生成的同色區塊的彩色圖像(如建築繪圖紙)
  • TIFF files
  • PDF files

相關詞條

熱門詞條

聯絡我們