algorithm - 索引集列表的高效数据结构

Question

我试图通过例子来解释:

想象一个编号元素列表 E = [elem0, elem1, elem2, ...]。

一个索引集现在可以是 {42, 66, 128} 引用 E 中的元素。这个集合中的顺序并不重要，所以 {42, 66, 128} == {66, 128, 42}，但是每个元素在任何给定的索引集中至多出现一次(因此它是一个实际的集合)。

我现在想要的是一个节省空间的数据结构，它给我另一个有序列表 M，它包含引用 E 中元素的索引集。M 中的每个索引集只会出现一次(因此 M 在这方面是一个集合)但是 M 本身必须是可索引的(因此 M 在这个意义上是一个列表，因此精确的索引并不重要)。如有必要，可以强制索引集都包含相同数量的元素。

例如，M 可能看起来像:

0: {42, 66, 128}
1: {42, 66, 9999}
2: {1, 66, 9999}

我现在可以执行以下操作:

for(i in M[2]) { element = E[i]; /* do something with E[1],E[66],and E[9999] */ }

您可能知道这是怎么回事:您现在可能有另一个映射 M2，它是指向 M 的有序集合列表，最终指向 E 中的元素。

正如你在这个例子中看到的，索引集可以相对相似(M[0] 和 M[1] 共享前两个条目，M[1] 和 M[2] 共享后两个条目)这让我认为必须有比使用集合数组的简单方法更有效的方法。但是，我可能无法想出一个良好的索引条目全局排序来保证良好的“共享”。

我能想到任何东西，从将 M 表示为一棵树(其中 M 的索引来自深度优先搜索排序或其他)到联合查找结构的 HashMap (虽然不知道它是如何工作的:)

非常欢迎为此类内容提供指向任何教科书数据结构的指针(数据库世界中有什么东西吗？)但如果您提出“自制”解决方案或只是随意的想法，我也很感激。

空间效率对我来说很重要，因为 E 可能包含数千甚至几百万个元素，(某些)索引集可能很大，至少某些索引集之间的相似性应该很大，并且可能有多层映射。

非常感谢!

Answer 1

您可以组合 M 中的所有数字并删除重复项并将其命名为 UniqueM。

所有 M[X] 集合都转换为位掩码。例如 int 值可以存储 32 个数字(为了支持无限计数，您应该存储 int 数组，如果数组大小总共为 10，我们可以存储 320 个不同的元素)。 long 类型可以存储 64 位。

E: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

M[0]: {6, 8, 1}
M[1]: {2, 8, 1}
M[2]: {6, 8, 5}

将转换为:

UniqueM: {6, 8, 1, 2, 5}
M[0]: 11100 {this is 7}
M[1]: 01110 {this is 14}
M[2]: 11001 {this is 19}

注意: 您也可以结合 my 和 ring0 方法，而不是重新排列 E 来创建新的 UniqueM 并在其中使用间隔。