格倫布編碼

格倫布編碼是一種無失真資料壓縮方法，由數學家所羅門·格倫布在1960年代提出。其優點為易於編碼與解碼，另外對於擁有機率分布為幾何分佈${\displaystyle G(p),p=0.5,}$的資料，格倫布編碼是最佳的前綴碼，且能無限逼近該資料的熵，目前廣泛用於無損影像壓縮。

編碼的建立

 

令輸入值為正整數${\displaystyle n}$ ，參數值為正整數 ${\displaystyle M}$ ，輸出之格倫布碼為 ${\displaystyle c}$ ，其中 ${\displaystyle c}$  由兩種編碼組合而成，

${\displaystyle c=(u,b)}$ ，${\displaystyle u}$ ：一进制編碼，${\displaystyle b}$ ：截斷二進制編碼。

計算 ${\displaystyle u}$  與 ${\displaystyle b}$ 。

${\displaystyle q=\left\lfloor {\frac {n}{m}}\right\rfloor ,}$  ${\displaystyle r=n-q}$ 。

將 ${\displaystyle q}$  做一进制編碼，${\displaystyle r}$  做截斷二進制編碼即可得到${\displaystyle (u,b)}$ 。

格倫布-萊斯編碼中的商數${\displaystyle q}$ 指示了所在區塊，而${\displaystyle r}$ 指示所在區塊內部的位置。如上圖，對整數 ${\displaystyle N}$  做格倫布-萊斯編碼，${\displaystyle q}$  代表區塊、${\displaystyle r}$  表示區塊內部位置、${\displaystyle M}$  為參數，每個區塊的大小皆相等且長度為 ${\displaystyle M}$ ，特別注意當編碼方式為格倫布-萊斯編碼時，即 ${\displaystyle M}$  為 ${\displaystyle 2}$  的整數次方，所有${\displaystyle r}$ 的編碼長度相等。

參數 ${\displaystyle M}$  是伯努利過程的函數，其中伯努利過程的參數 ${\displaystyle p}$  定義為 ${\displaystyle p=P(X=0)}$ ，則 ${\displaystyle M}$  的所在區間為此伯努利過程的中位數-1到中位數+1之間。如下式：

${\displaystyle (1-p)^{M}+(1-p)^{M+1}\leq 1<(1-p)^{M-1}+(1-p)^{M}.}$ 

當 ${\displaystyle M}$  足夠大時，我們可以將其表示成，${\displaystyle M=\left\lfloor {\frac {-1}{\log _{2}(1-p)}}\right\rfloor }$ 。

使用符號整數

格倫布編碼主要是針對非負整數進行編碼，但也可以使用重疊(Overlap)與交錯(Interleave)擴展至對所有整數進行編碼。令一串用於編號的數列，(0,1,2,...)，給予非負整數偶數編號，給予負整數奇數編號，使得排列方式如下，(0,-1,1,-2,2,...)，即非負整數 ${\displaystyle x}$  映射至 ${\displaystyle \{x^{\prime }|x^{\prime }=2|x|,x\geq 0\}}$ ，負整數 ${\displaystyle y}$  映射至 ${\displaystyle \{y^{\prime }|y^{\prime }=2|y|-1,y<0\}}$ 。

萊斯編碼

萊斯編碼（Rice coding，由Robert F. Rice所提出），為一種前綴碼，歸屬於格倫布編碼的子集合，參數 ${\displaystyle M}$  為 ${\displaystyle 2}$  的整數次方，即 ${\displaystyle M=2^{R},R\in N}$ 。此種特例未必是所有格倫布編碼中的最佳編碼方式，但由於目前電腦為二進位運算，萊斯編碼能快速且有效地以二進位運算實現。

性質

范氏霍夫曼編碼

格倫布編碼為一種范氏霍夫曼編碼。

演算法

1. 選擇參數 ${\displaystyle M}$ 
2. 待編碼數值為 ${\displaystyle n}$ ，計算：
   1. 商數： ${\displaystyle q=\left\lfloor {\frac {n}{m}}\right\rfloor ,}$ 
   2. 餘數： ${\displaystyle r=n-q}$ 。
3. 編碼
   1. 商數編碼，對 ${\displaystyle q}$  進行一进制編碼，得到 ${\displaystyle u}$ 。
   2. 餘數編碼，對 ${\displaystyle r}$  進行截斷二進制編碼，得到 ${\displaystyle b}$ 。
   3. 合併，${\displaystyle c=(u,b)}$ 。
4. 輸出 ${\displaystyle c=(u,b)}$ 

範例

設 M = 10。則 ${\displaystyle b=\lceil \log _{2}(10)\rceil =4}$ . ${\displaystyle 2^{b}-M=16-10=6}$ 

商數編碼 q 輸出位元 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 ${\displaystyle \vdots }$  ${\displaystyle \vdots }$  N ${\displaystyle \underbrace {111\cdots 111} _{N}0}$

餘數編碼 r 偏移 二進位 輸出位元 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

選擇42作為編碼時，42會被拆成 ${\displaystyle q=4}$  及 ${\displaystyle r=2}$ ，編碼為11110010，而商數編碼尾數必為0，能標示商數編碼位元的結束。

參考來源

• Golomb, S.W. (1966). , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 （页面存档备份，存于互联网档案馆）
• R. F. Rice (1971) and R. Plaunt, , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp. 889–897, Dec. 1971. （页面存档备份，存于互联网档案馆）
• R. F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques, " Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, Mar. 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 ISBN 1-55860-570-3
• David Salomon. "Data Compression",ISBN 0-387-95045-1.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines （页面存档备份，存于互联网档案馆）. MIT Press, Cambridge MA, 2010.
• https://en.wikipedia.org/wiki/Golomb_coding （页面存档备份，存于互联网档案馆）