哥伦布（Golomb）压缩编码

Golomb

哥伦布（Golomb）编码是一种无损的数据压缩方法，由数学家Solomon W.Golomb在1960年代发明。Golomb编码只能对非负整数（unsigned int）进行编码。当待编码符号表中的符号出现的概率符合几何分布（Geometric Distribution）时，使用Golomb编码可以取得最优效果，也就是说Golomb编码比较适合小数字比大数字出现概率高的场景编码。它使用较短的码长编码较小的数字，较长的码长编码较大的数字。

Golomb编码是一种分组编码，需要一个正整数参数m。用m对待编码的数字（n）进行求商（q=int(n/m)）和余（r=n%m），然后对商做一元编码，对余做固定长度的二进制编码（用固定bit数来表示余数）。对余数（r）的编码，有个细节要注意。整体如下图：

下图是wiki上的一个case：

m=10，余数从0到9，让一部分余数用3个bit表示，一部分用4个bit表示，能够其它压缩的效果（比全部都用4个bit强）。

有了m，通过bitstream，得到q和r，就能解码。

Rice–Golomb

Rice-Golomb是Golomb编码的一个变种，它给Golomb编码的参数m添加了个限制条件，m必须是2的次幂。这样有两个好处：

• 求余更简单：r = N & (m-1)
• 对余数的编码，由于m是2的幂，编码也简单了

>>> 8%4
0
>>> 8 & (4-1)
0
>>> 55%4
3
>>> 55 & (4-1)
3

Exp-Golomb

Exp-Golomb编码的变化较大，我觉得它只是有点Golomb编码的形式，编解码的方式完全不一样。

Exp-Golomb的码元结构是：[M zeros prefix] [1] [Offset]

Exp-Golomb编码中，有一个阶的概念，K。不同K值的选择，编码长度不太一样。看图吧：

当k=0时，解码：

>>> k=0
>>> 2**0 - 1
0
>>> 2**1 - 1 + 0
1
>>> 2**1 - 1 + 1
2
>>> 2**2 - 1 + 0
3
>>> 2**2 - 1 + 1
4
>>> 2**2 - 1 + int('10',2)
5
>>> 2**2 - 1 + int('11',2)
6
>>> 2**3 - 1 + int('000',2)
7
>>> 2**3 - 1 + int('001',2)
8
>>> 2**3 - 1 + int('010',2)
9
>>> 2**3 - 1 + int('011',2)
10
>>> 2**3 - 1 + int('100',2)
11
>>> 2**3 - 1 + int('101',2)
12
>>> 2**3 - 1 + int('110',2)
13
>>> 2**3 - 1 + int('111',2)
14
>>> 2**4 - 1 + int('0000',2)
15

k不为0时，编解码方式不一样。

AVC和HEVC，都是用0阶Exp-Golomb编码。

-- EOF --

相关文章

• Shannon-Fano算法
• 霍夫曼（Huffman）压缩编码算法