格倫布編碼

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

編碼的建立

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

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

計算 $u$ 與 $b$ 。

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

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

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

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

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

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

使用符號整數

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

萊斯編碼

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

性質

范氏霍夫曼編碼

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

演算法

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

範例

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

商數編碼
q	輸出位元
0	0
1	10
2	110
3	1110
4	11110
5	111110
6	1111110
$\vdots$	$\vdots$
N	$\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會被拆成 $q=4$ 及 $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 （页面存档备份，存于互联网档案馆）