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 块过滤器的应用。
Last updated