algorithm - 存储精确集合成员的最有效方式？

Question

我有N插槽。有M插槽已占用。

我希望能够准确地告诉每个插槽是否被占用。 (请不要回答布隆过滤器。)

为 M << N 存储此信息的绝对最节省存储空间的方式是什么？ ？

• 猜测 0:N 的位图位。
• 猜测 1:已占用位置的数组。相当适合小型 M .
• 猜测 2:p0 + (M-1)p1 + (M-1)(M-2)p2 + ...其中 pX 是已占用插槽在剩余未占用插槽中的位置。这比猜测 1 的效率略高，因为随着插槽被填充，未占用插槽的选择范围变窄。

猜测2还有很多废料；它包括填充槽的顺序，这是不需要的信息。

什么方法比猜测 2 更有效？

Answer 1

如果 M 和 N 已知，那么实现最佳压缩的一种方法是存储 index of the combination .

有 t= N!/((N-M)!*M!) 种方法可以选择要填充的 M 个槽位，因此您始终至少需要 log2(t) 位来表示此信息。

存储组合的索引允许您精确地使用 ceil(log2(t)) 位。