2

Web 应用程序比较成对的正整数集。每个集合只有唯一的值，不大于 210 000 000（适合 28 位）。每组最多 5 000 000 个值。

比较集合 A 和 B，需要三个结果集：“A 唯一”、“B 唯一”、“A 和 B 通用”。具体任务是回答一个问题“数字 N 是否存在于集合 S 中？”

到目前为止，该项目在 LAMP 堆栈下的共享主机的有限资源中运行。我想出的 Quick'n'dirty 解决方案是将工作外包给托管的 MySQL，它拥有更多的资源。每个集合的临时表，唯一带有数字的列是主索引。很少有集合足够小以适合引擎=内存，这很快。它可以工作，但是太慢了。

寻找一种将这样的集合保存在内存中的方法，对于在其中搜索特定数字的任务有效。尽可能降低内存占用。

我想到了将每个集合编码为 2^28 位 (32 Mb) 的位掩码的想法。集合中存在的数字 = 1 位集合。500 万个数字 = 2.1 亿个中的 500 万个比特。许多零==可以有效压缩？

好像我在发明一辆自行车。请指导我找到针对这种二进制压缩特殊情况的“众所周知”的解决方案。我读到了霍夫曼编码，这似乎不是正确的解决方案，因为它的重点是减小大小，而我的任务需要对压缩集进行多次搜索。

更新。刚刚找到一篇关于Golomb 编码的文章及其在运行长度编码中的应用示例。

4

1 回答 1

3

有一种标准的压缩技术可用于表示范围内的大型整数集，它允许有效的迭代（因此它可以轻松地进行交集、并集、集差等）但不允许随机访问（所以它对“在 S 中是 N”）。对于这个特定的问题，它将数据集减少到每个大约 7 位，对于大小为 5,000,000 的集合，这将是大约 8MB。如果它有用，我将在下面描述它。

大小为 210,000,000 位（每个大约 26MB）的位向量在计算上是高效的，既可以回答“S 中的 N”查询，也可以用于位运算，因为您可以使用现代处理器上的向量化指令快速完成它们；它可能与 5,000,000 个元素的交集计算一样快。它消耗大量内存，但如果你有那么多内存，那就去吧。

如果集合是指定大小的均匀分布的随机样本，则压缩技术很简单并且几乎是最佳的，如下所示：

  1. 对集合进行排序（或确保已排序）。

  2. 将“当前值”设置为 0。

  3. 对于集合中的每个元素，按顺序：

    一种。从元素中减去“当前值”；

    湾。虽然该差至少为 32，但输出1一位并从差中减去 32；

    C。输出一个0位，然后是编码为五位的差异。

    d。将“当前值”设置为比元素多一

为了证明我的说法，即压缩将导致每个元素大约 7 位：

很明显，每个元素将占用 6 位（0加上 5 位增量）；此外，我们必须考虑1步骤 3b 中的位。但是请注意，所有增量的总和恰好是集合中最大的元素，它不能超过 210,000,000，因此，我们执行步骤 3b 的次数不能超过 210,000,000/32 次。所以步骤 3b。将占不到 700 万位，而步骤 3c 将占 6 * 5,000,000 位，总共 3700 万或每个元素 7.4 位（实际上，通常会比这少一点）。

于 2013-02-28T01:39:46.160 回答