algorithm - 需要具有标签集的元素的数据结构，并且可以有效地找到其标签是输入集的子集的所有元素

Question

我在集合 A 中有一些元素具有集合 B 中的一组标签。是否有支持这些操作的数据结构？

1. 构造，给定一组所有可能的标签和所有元素。 (在进行任何查找之前，我会知道所有标签和元素)
2. 给定一组标签，高效地找到其标签是输入集子集的所有元素。

我在 Lua 中执行此操作，因此我可以访问具有恒定(足够)时间插入和删除以及线性时间遍历的可变表。

天真的方法是保留所有元素的列表并遍历每个元素并查看其标签是否是输入的子集。这具有时间复杂度 O(nw)，其中 n 是元素的数量，w 是元素具有的最大标签数。 w 可能永远不会超过 10，所以这个时间复杂度可以被认为是线性的。

是否有一种数据结构可以在次线性时间内为我提供这种查找？

这是一个简单的化学 react 系统的上下文:化学 react 列出了 react 物，每当化学容器改变其内容时，我需要找到所有适用的 react ，这些 react 的 react 物都在容器。这个问题可以推广到当一组事情完成时你需要做某事的任何事情。

Answer 1

在最坏的情况下，次线性是不可能的，因为如果给定的标签集包含所有标签，则必须返回所有元素。但这里的算法在一般情况下可以是次线性的。

对于每个元素，使用一个 128 位整数(2 x 64 位整数，如果必须的话)来表示 100 个左右可能的标签(即每个位代表一个不同的标签:如果元素有标签，则为 1，否则为 0。)

然后根据 128 位整数表示对数组进行排序。

给定一个标签列表，将其转换为 128 位整数表示，以便您可以使用按位运算来确定元素是否具有给定标签的子集。 (使用OR运算，然后统计结果中1的个数。)

实际加速(除了使用位运算的加速)解释如下。为此，让我们将输入简化为 8 位。

假设标签列表为 01001100 .

然后你可以搜索00000100在 O(logn) 中的元素列表中时间，因为列表已排序，并获取元素列表直到 00000101到达了。然后你可以跳转到00001000 , 又在 O(logn)时间，然后在那里搜索直到找到 00001101 , 然后跳转到 01000000 , 等等。

最终结果是您跳过了大量元素，代价是花费了O(tlogn)。对于跳跃，其中 t是输入标签集中的标签数。

你可以通过跳得更多来进一步推进这个想法。即跳转到 00000100 , 然后跳转到 00001000 , 然后到 00001100 , 然后到 01000000 , 然后到 01000100 ， 等等。这导致支出 O(2^tlogn)是时候跳来跳去了，但如果 t << n 这可能是值得的和 2^t易于管理。