存储精确集合成员的最有效方式？
Most efficient way of storing exact set membership?
我有 N 个位置。已占用 M 个插槽。
我希望能够准确地判断每个插槽是否被占用。 （请不要回答布隆过滤器。）
什么是存储 space 最有效的存储 M << N 信息的方法？
- 猜测 0：
N 位的位图。
- 猜想一：被占用的槽位位置数组。对小
M. 还算不错
- 猜想2：
p0 + (M-1)p1 + (M-1)(M-2)p2 + ... 其中pX是已占用槽位在剩余未占用槽位中的位置。这比猜测 1 稍微更有效，因为随着插槽被填充，未占用插槽的选择范围变窄。
猜测2还有很多废料；它包括插槽填充的顺序，这是不需要的信息。
哪种方法比猜2更有效率？
如果 M 和 N 已知，则实现最佳压缩的一种方法是存储 index of the combination。
有 t= N!/((N-M)!*M!) 种方法可以选择要填充的 M 个槽位，因此您始终至少需要 log2(t) 位来表示此信息。
存储组合的索引可以让您正好使用 ceil(log2(t)) 位。
假设没有关于值分布的其他信息（即，每个可能的 M 值样本都是等概率的），那么最佳压缩技术是 ，即简单地使用可能样本集合中样本枚举的序数。
但是，计算起来并不容易，因为枚举需要对非常大的数字进行算术运算。
相反，可以使用 Golomb 压缩的变体，对压缩率的影响很小。
假设样本中的数字是有序的。我们从计算连续差异开始。因为我们永远不会有两个相等的数字，所以差值序列永远不会包含 0；为了获得微小的额外压缩，我们从比样本的第一个元素多一个开始，而不是第一个元素本身——这意味着序列从不包含 0——然后从每个值中减去一个。我们现在 select 一些方便的位数 k，并将序列中的每个值 δ 编码如下：
当δ > 2k时，发送一个1位并从δ中减去2k
现在δ可以写成k位。发送 0 后跟 δ
我们可以选择k为⌊log<sub>2</sub>(N/M)⌋，也就是说N < 2<sup>k+1</sup>M。 （取上限是另一种可能性。）因此，在上述算法的第 1 步的所有迭代中发送的 1 位数小于 2M（因为每个 1占级数累计和的2k，小于N)。每个步骤 2 发送恰好 k + 1 位，并且步骤 2 恰好执行 M 次，样本中的每个值一个。因此，发送的总位数介于 M × (k + 1) 和 M × (k + 2) 之间。但是既然我们知道k < log<sub>2</sub>(N/M) + 1，传输的总大小肯定小于M log<sub>2</sub> N - M log<sub>2</sub> M + 3M)。 （我们还必须发送参数 k 和 M，所以有一点开销。）
现在，让我们考虑一下最佳传输大小。有 N choose M 个可能的样本，因此枚举索引的大小（以位为单位）将为 log<sub>2</sub>（N 选择 M）。如果 N > M，我们可以将N choose M近似为N<sup>M</sup>/M!，然后利用Stirling's approximation我们得到：
log(N choose M) ≈ M log N − M log M + M
（这实际上有点高估，但它是渐近正确的。）
因此，压缩序列与信息论极限之间的差异小于每个值 2 位。 （实际中，一般是一个bit左右一个值，因为step 1执行的次数远远少于最大次数。）
我有 N 个位置。已占用 M 个插槽。
我希望能够准确地判断每个插槽是否被占用。 （请不要回答布隆过滤器。）
什么是存储 space 最有效的存储 M << N 信息的方法？
- 猜测 0：
N位的位图。 - 猜想一：被占用的槽位位置数组。对小
M. 还算不错
- 猜想2：
p0 + (M-1)p1 + (M-1)(M-2)p2 + ...其中pX是已占用槽位在剩余未占用槽位中的位置。这比猜测 1 稍微更有效，因为随着插槽被填充，未占用插槽的选择范围变窄。
猜测2还有很多废料；它包括插槽填充的顺序，这是不需要的信息。
哪种方法比猜2更有效率？
如果 M 和 N 已知，则实现最佳压缩的一种方法是存储 index of the combination。
有 t= N!/((N-M)!*M!) 种方法可以选择要填充的 M 个槽位，因此您始终至少需要 log2(t) 位来表示此信息。
存储组合的索引可以让您正好使用 ceil(log2(t)) 位。
假设没有关于值分布的其他信息（即，每个可能的 M 值样本都是等概率的），那么最佳压缩技术是
但是，计算起来并不容易，因为枚举需要对非常大的数字进行算术运算。
相反，可以使用 Golomb 压缩的变体，对压缩率的影响很小。
假设样本中的数字是有序的。我们从计算连续差异开始。因为我们永远不会有两个相等的数字，所以差值序列永远不会包含 0；为了获得微小的额外压缩，我们从比样本的第一个元素多一个开始，而不是第一个元素本身——这意味着序列从不包含 0——然后从每个值中减去一个。我们现在 select 一些方便的位数 k，并将序列中的每个值 δ 编码如下：
当δ > 2k时，发送一个
1位并从δ中减去2k现在δ可以写成k位。发送
0后跟 δ 的 k 位值
我们可以选择k为⌊log<sub>2</sub>(N/M)⌋，也就是说N < 2<sup>k+1</sup>M。 （取上限是另一种可能性。）因此，在上述算法的第 1 步的所有迭代中发送的 1 位数小于 2M（因为每个 1占级数累计和的2k，小于N)。每个步骤 2 发送恰好 k + 1 位，并且步骤 2 恰好执行 M 次，样本中的每个值一个。因此，发送的总位数介于 M × (k + 1) 和 M × (k + 2) 之间。但是既然我们知道k < log<sub>2</sub>(N/M) + 1，传输的总大小肯定小于M log<sub>2</sub> N - M log<sub>2</sub> M + 3M)。 （我们还必须发送参数 k 和 M，所以有一点开销。）
现在，让我们考虑一下最佳传输大小。有 N choose M 个可能的样本，因此枚举索引的大小（以位为单位）将为 log<sub>2</sub>（N 选择 M）。如果 N > M，我们可以将N choose M近似为N<sup>M</sup>/M!，然后利用Stirling's approximation我们得到：
log(N choose M) ≈ M log N − M log M + M
（这实际上有点高估，但它是渐近正确的。）
因此，压缩序列与信息论极限之间的差异小于每个值 2 位。 （实际中，一般是一个bit左右一个值，因为step 1执行的次数远远少于最大次数。）