c - 存储压缩集的最佳方式

Question

正如title所说，我正在寻找在内存中存储集的最佳方式。我只对字节集感兴趣（从0到255的整数数组，其中顺序不重要）。不要求编码/解码速度快唯一必要的是集合需要尽可能少的内存。
我提出的第一种方法是为每个集合分配256位的数组（32字节），而位于n位置的位告诉集合中是否有n位。这种方法的问题在于，即使集合大部分是空的（只有很少的元素），它也需要相同的内存量。
我尝试的第二种方法是将集合存储为常规数组。因此，如果集合包含n元素，则需要存储n + 1字节。第一个字节表示元素的数量，其他字节表示元素但是，正如我们所知道的，集合顺序并不重要，所以有些东西强烈地告诉我，一定有办法来实现这一点。
我的第三个尝试是枚举所有可能的集合，并只存储集合的索引（整数表示它在所有可能的字节集合列表中的索引）但是，事实证明，它绝对等同于第一种方法。基本上，我仍然需要32字节来存储任何集合，因此它不是很有用。
我的第四次尝试是基于我的第二种方法我注意到这个集合包含n元素，当然，它需要n + 1字节（如果我使用第二种方法）。但是，例如，如果元素k出现在set中（实际上出现在array中，因为在我的第二次尝试中，我将集合存储为数组），那么它就不能再次出现基本上，如果k再次出现，那么它的意思一定有所不同（可能k - 1）。所以，我做了一些优化，我注意到，如果我对每个下一个元素进行不同的编码，我可以节省一些字节（例如，检验[3, 3, 5, 7]）被解释为元素的元素是3（每个下一个元素被索引降低）的集合，并且{3, 4, 5}被解释为[3, 3, 5, 6]（注意到{3, 4, 2}和cc>已经存在，所以3由4和它减少。变为6，但2存在，4存在，因此必须是4）。但是这种方法如何能真正节省字节呢我尝试并意识到我可以对数组中的元素进行排序，以便在某些情况下避免使用高位对元素进行编码，因此我为每个元素保存了3位，这大约是2个字节（即1）。
我所做的第五种方法与第二种方法类似，但它对元素数量的解释不同。如果元素数小于n / 16则它通常从内存中的以下数组读取所有元素但是，如果元素的数目大于n / 2 * 1 / 8，那么它将创建一个完整的集合，然后从内存中的以下数组中移除元素。平均来说，is节省了很多字节，但它离最优值还很远。
我的最后一次尝试（第六次尝试）是枚举一些集合（例如创建一个集合列表，该列表将包含：full set，set with only偶数，set with only odd numbers，set with elements than 128，etc），然后使用该列表中的元素和基本集合操作（并集、交集等）重建原始集合。对于我们从列表中使用的每个基集，它需要几个字节；对于并集或交集操作，它需要几个字节；当然，对于序列的长度，它需要一个字节它非常依赖于基本集合列表中应该硬编码的元素的数量，但是似乎很难预先创建和正确选择列表中的元素总之，有人告诉我，这不是一个很聪明的方法。
但什么才是最理想的方法呢有人告诉我，我的第四次尝试还不错，但我们能做得更好吗我操作的集合具有随机的元素数，因此平均每个集合的元素数都是128个，因此我正在寻找一种方法来为每个集合分配128个位（128个字节）到目前为止，我所做的最好的事情是使用第四种方法，这离我的目标很远。
再说一遍，速度并不重要。编码/解码可能非常慢，唯一重要的是集合需要尽可能少的内存当我说“在内存中”时，我的意思是在内存中编码（压缩）另外，我对尽可能少的比特感兴趣（不仅仅是字节），因为我想在硬盘上存储几十亿个压缩的数据集，所以计算每一个数据集所需的平均比特数是很重要的，这样我就知道有多少资源可用于我想实现的目标。
如果你想要一些代码（但我真的不明白你为什么要这么做），我可以在这里发布我用C语言为所有这些方法制定的解决方案不管怎样，我并不是在问如何用特定的编程语言实现它的代码或技术细节，我只是在问压缩集的方法/算法。
提前谢谢你。

Answer 1

你的第一种方法（和第三种方法是等价的）已经是最优的了。这是无法改善的。
有2256个可能的数字集你正在使用根据鸽子洞原理，你需要2256个数字来识别它们，你需要256位来表示这些数字任何识别使用少于256位的集合的方法都会留下至少一对（可能还有多对）集合共享同一标识符。