格伦布编码

格伦布编码（英语：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$ $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)$