匹配集的数据结构

我有一个应用程序，其中有很多组。一套可能是
{4, 7, 12, 18}
唯一编号且全部小于 50。

然后我有几个数据项：
1 {1, 2, 4, 7, 8, 12, 18, 23, 29}
2 {3, 4, 6, 7, 15, 23, 34, 38}
3 {4, 7, 12, 18}
4 {1, 4, 7, 12, 13, 14, 15, 16, 17, 18}
5 {2, 4, 6, 7, 13, 15}

数据项 1、3 和 4 与集合匹配，因为它们包含集合中的所有项目。

I need to design a data structure that is super fast at identifying whether a data item is a member of a set includes all the members that are part of the set (so the data item is a superset of the set). My best estimates at the moment suggest that there will be fewer than 50,000 sets.

我当前的实现将集合和数据作为无符号 64 位整数并将集合存储在列表中。然后为了检查数据项，我遍历列表进行 ((set & data) == set) 比较。它可以工作，并且空间效率高，但速度很慢（O(n)），我很乐意用一些内存来换取一些性能。有人对如何组织这个有更好的想法吗？

Edit:非常感谢所有的答案。看来我需要提供有关该问题的更多信息。我先获取集合，然后逐一获取数据项。我需要检查数据项是否与其中一组匹配。
这些集合很可能是“块状”的，例如对于给定的问题 1、3 和 9 可能包含在 95% 的集合中；我可以在某种程度上提前预测这一点（但不是很好）。

对于那些建议记忆化的人：这是记忆化函数的数据结构。这些集合代表已经计算出的通用解，数据项是函数的新输入。通过将数据项与通用解决方案相匹配，我可以避免大量处理。

我看到另一个与您的解决方案双重的解决方案（即针对每个集合测试数据项），并且使用二叉树，其中每个节点测试是否包含特定项目。

例如，如果您有集合 A = { 2, 3 } 和 B = { 4 } 和 C = { 1, 3 } 您将拥有以下树

                      _NOT_HAVE_[1]___HAVE____
                      |                      |            
                _____[2]_____          _____[2]_____
                |           |          |           |
             __[3]__     __[3]__    __[3]__     __[3]__
             |     |     |     |    |     |     |     |
            [4]   [4]   [4]   [4]  [4]   [4]   [4]   [4]
            / \   / \   / \   / \  / \   / \   / \   / \
           .   B .   B .   B .   B    B C   B A   A A   A
                                            C     B C   B
                                                        C

制作树后，您只需进行 50 次比较，或者一组中可以有多少个项目。

例如，对于 { 1, 4 }，您通过树进行分支：右（集合有 1）、左（没有 2）、左、右，然后得到 [ B ]，这意味着仅包含集合 B在 { 1, 4 } 中。

这基本上称为“二元决策图”。如果您对节点中的冗余感到不满（您应该如此，因为 2^50 是很多节点......）那么您应该考虑简化形式，称为“简化的有序二元决策图”并且是一种常用的数据结构。在此版本中，节点冗余时会被合并，并且您不再拥有二叉树，而是有向无环图。

The ROBBD 的维基百科页面 http://en.wikipedia.org/wiki/ROBDD可以为您提供更多信息，以及为各种语言实现此数据结构的库的链接。