Golomb-Rice编码集（GCS）

假设Alice想要将一组数字发送给Bob。简单的方法是直接将整个数字列表发送给他：

849

653

476

900

379

但是有一种更有效率的方法。首先，Alice将列表按数字顺序排列：

379

476

653

849

900

然后，Alice发送第一个数字。对于剩余的数字，她发送该数字与前一个数字的差异。例如，对于第二个数字，她发送 97（476 - 379）；对于第三个数字，她发送 177（653 - 476）；依此类推：

379

97

177

196

51

我们可以看到，有序列表中两个数字之间的差异产生的数字比原始数字要短。收到这个列表后，Bob可以通过将每个数字与其前一个数字相加来重建原始列表。这意味着我们节省了空间而没有丢失任何信息，这称为无损编码。 如果我们在固定值范围内随机选择数字，那么我们选择的数字越多，平均差异（均值）的大小就越小。这意味着我们需要传输的数据量并不像列表长度增加得那么快（直到某个点）。 更有用的是，列表中随机选择的数字的长度自然倾向于较小的长度。考虑从1到6选择两个随机数；这相当于掷两个骰子。两个骰子有36个不同的组合：

1 1 1 2 1 3 1 4 1 5 1 6

2 1 2 2 2 3 2 4 2 5 2 6

3 1 3 2 3 3 3 4 3 5 3 6

4 1 4 2 4 3 4 4 4 5 4 6

5 1 5 2 5 3 5 4 5 5 5 6

6 1 6 2 6 3 6 4 6 5 6 6

让我们找到两个数字中较大的数字与较小的数字之间的差异：

0 1 2 3 4 5

1 0 1 2 3 4

2 1 0 1 2 3

3 2 1 0 1 2

4 3 2 1 0 1

5 4 3 2 1 0

如果我们统计每个差异发生的频率，我们会发现较小的差异比较大的差异更有可能发生：

差异	频率
0	6
1	10
2	8
3	6
4	4
5	2

如果我们知道可能需要存储大数（因为即使它们很少，大的差异也可能发生），但通常需要存储小数，我们可以使用一种系统对每个数字进行编码，对小数使用较少的空间，并为大数提供额外的空间。从平均意义上讲，这种系统的性能会比对每个数字使用相同数量的空间好。

Golomb 编码提供了这种功能。Rice 编码是 Golomb 编码的一个子集，在某些情况下更方便使用，包括 Bitcoin 块过滤器的应用。