algorithm - 确定集合是否是集合集合中任何成员的子集

Question

我有一个由集合组成的集合 A，需要确定 A 中的每个集合是否等于 A 中的任何其他集合或者是任何其他集合的子集。

我的直觉是按如下方式进行:对 A 中的每个集合 i 进行排序，然后将其值与一些保留字符连接起来，并确定该组合键是否存在于 HashMap 。如果不是，则将复合键添加到 HashMap 中。然后，对于 i 中的每个成员组合，还对这些值进行排序并将其连接到一个复合键中，并将该键插入 HashMap 中。然后继续 A 中的下一组。

这种方法的问题是空间需求很大，因为我在 A 中有大约 2500 万组，有些有很多成员。我想在主内存中完成上述操作，但不能在 16GB RAM 中完成。

有没有一种更节省空间的方法来完成这项任务？如果其他人可以就此问题提供任何见解，我将不胜感激。

Answer 1

根据您有多少不同的元素，inverted index可能有道理。

基本思想是，对于每个元素 e，您构建一个包含 e 的集合的集合 ID 列表。然后，对于每个集合 i，您将 i 中所有元素的列表相交(这可以优化，例如，通过对集合 ID 进行排序)以获得包含 i 的所有元素的所有集合。

示例:

set 1: A, C
set 2: B, C, E
set 3: A, C, E

倒排索引:

A -> 1, 3
B -> 2
C -> 1, 2, 3
E -> 2, 3

然后对于集合 1，您查询 A & C 的倒排索引，并在删除集合 1 后将产生 1 和 3 的列表相交(作为 self 命中)您最终得到包含第 1 组的第 3 组。继续其他组。

类似 Apache Lucene 的库或 Elastic Search有效地支持这个想法。可能还有内存中的倒排索引可以在 RAM 中执行此操作。