Web应用程序比较正整数的集合对。每一组只能有唯一的值，不大于210 000 000(适合28位)。
比较集合A &B，需要三个结果集:" A唯一" " B唯一" " A共有"B"。具体任务是回答一个问题"数字N是否出现在集合S中?"
到目前为止，项目在共享主机的有限资源中运行，在LAMP堆栈下。我想到的快速解决方案是将工作外包给托管的MySQL，它有更多的资源。对于每个临时表集，唯一有数字的列是主索引。很少设置足够小，以适应引擎=内存，这是快速的。它可以工作，但是太慢了。
寻找一种方法将这样的集合保存在内存中，有效地执行搜索特定数字的任务。保持尽可能低的内存占用
我想到了一个想法，将每个集合编码为2^28位(32 Mb)的位掩码。出现在集合中的数字= 1位集合。5个MLN数= 5个MLN位从2.1亿个中取出。多0 ==能有效压缩吗?
好像我在发明一辆自行车。请给我一个"众所周知"的解决方案来解决这个特殊的二进制压缩问题。我读过霍夫曼编码，这似乎不是正确的解决方案，因为它的重点是缩小尺寸，而我的任务需要在压缩集上进行多次搜索。
乌利希期刊指南。刚刚找到一篇关于Golomb编码的文章，以及它在运行长度编码中的应用示例。
有一种标准的压缩技术可用于表示一个范围内的大型整数集，它允许有效的迭代(因此它可以轻松地进行交集，并集，集差等)，但不允许随机访问(因此它不利于"is N in S")。对于这个特定的问题，它将把数据集减少到每个大约7位，对于大小为5,000,000的集，大约是8MB。如果它有用，我将在下面描述它。
210,000,000位(每个大约26MB)的位向量在计算上是高效的，既可以回答"is N in S"的查询，也可以进行位运算，因为你可以在现代处理器上使用矢量化指令快速完成它们;这可能和500万元素的交集计算一样快。它会消耗很多内存，但是如果你有那么多内存，那就去做吧。
如果集合是指定大小的均匀分布的随机样本，则压缩技术是简单的，并且是最优的，压缩技术如下:
-
对集合进行排序(或确保它已排序)。
-
设置"当前值"为0
-
对于集合中的每个元素，按顺序:
。从元素中减去"当前值";
b。当该差值至少为32时，输出单个
1位并从差值中减去32;c。输出单个
0位，后跟5位编码的差值。d。将"current value"设置为比
元素大一个
为了证明我的说法，压缩将导致每个元素大约7位:
很明显，每个元素将占用6位(0加上5位增量);此外，我们必须考虑步骤3b中的1位。注意，所有增量的和恰好是集合中最大的元素，它不能大于210,000,000，因此，我们不能执行步骤3b超过210,000,000/32次。步骤3b。将占不到700万比特，而步骤3c将占6 * 5,000,000比特，总计3700万，或每个元素7.4比特(在实践中，它通常会比这个少一点)。