格伦布编码（英语：Golomb coding）是一种无失真资料压缩方法，由数学家所罗门·格伦布在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 （页面存档备份，存于互联网档案馆）