algorithm - 快速检查交叉点是否设置为空(误报是可以的)

Question

如果两个集合的交集(一个对所有检查都相同，另一个改变)是否为空，我需要做很多检查。

如果支票说(在少量支票中)它不是空的，那没关系，但它是(可以有更精确的第二个过滤步骤)，所以误报是可以的。这是不允许的，我过滤掉了肯定有非空交叉点的东西，所以漏报是不行的。

所以，只有一个场景:

{A,B,C,D} <-> {D,E,F} => true (D in intersection set)，绝不允许为假

{A,B,C} <-> {D,E,F} => false (没有交集)，也可以在少量的检查中返回true

对于单个元素，我会使用布隆过滤器，但对于一组元素我找不到类似的东西，布隆过滤器逐个元素检查是一个可能的选择，但我正在寻找更好的东西。

Answer 1

非常感谢您的回答，帮助我想出了一个很好的解决方案并解决了问题。

这个想法基本上很原始，但足够了。

我创建了两个位集，一个用于更改集，一个用于固定集。集合的每个元素都被散列为一位(例如，对于 1 到 64 中的长一位)，然后组合成一个集合(主要是 k=1 的 Bloom-Bitset)。

要检查是否存在非空交集，我只需将两个位集与位与运算结合起来，然后检查结果是否不为 0。

假阳性率会(我认为，没有计算)更糟，但对于我的情况来说已经足够了。

例子:

[A,B,C] => 0000100010100000

[B,D,F] => 0100000010000100

--------------------&

0000000010000000 != 0 => 真