高效算法：检查子集是否在一系列集合中

Question

高效算法：检查子集是否在一系列集合中

5

我浏览了一些关于确定一个集合 A 是否是另一个集合 B 的子集的帖子，但我发现很难确定要使用哪个算法。以下是问题的概述：

我有一个字符串数组 A，它在程序开始时被接收。对该结构不了解太多信息。数组中的每个字符串可以是任意长度，条目数没有限制，尽管通常可以假定数组中的条目数不会过多（<100）。
然后我遍历长度为 n 的对象列表。
每个 n 个对象也将具有一个字符串数组 B，即将有 n 个 B 数组。一旦程序运行，B 就会固定下来，即在运行时它们不会发生变化。
我想确定对于每个对象，A 是否是 B 的子集。

现在，我考虑使用哈希表。但是，我认为它们只有在只有一个 B 和许多 A 的情况下才有效。然后我可以为 B 制作一个哈希表，并针对我的哈希表检查每个对象的每个字符串数组。但是这并不是情况，因为只有一个 A，但有 n 个 B。有什么有效的算法可以做到这一点吗？

示例：

A:  ["A", "G", "T"]
B1: ["C", "G"]
B2: ["K", "A", "U", "T", "G"]
.
.
.
Bn: ["T", "I", "G", "O", "L"]

这里的A是B2的子集，但不是B1或者Bn的子集。

- lord.garbage

你需要多久检查一次A中的某个字符串是否是B的子字符串？在程序运行期间，您是否需要多次检查相同的字符串列表A（可能已更改）是否为B？ - Glubus

在程序运行的每一次，A始终固定在开头。B也在程序运行时固定不变，并且它们不会改变。但是有很多个B存在。 - lord.garbage

你能告诉我们关于字符串长度的分布情况吗？（在你的例子中，它们都是1。） - user1196549

@YvesDaoust，那只是为了简单起见。每个数组中的字符串可以具有任意长度。 - lord.garbage

1

抱歉，我对这个答案不满意。这些字符串是短的、长的还是非常长的（1兆字符）？全部都是吗？... - user1196549

显示剩余3条评论

3个回答

1

如您所知，如果提前了解A，您可以设计一个无冲突哈希函数来哈希A的所有元素。

然后，在搜索步骤中仅对哈希进行操作，而不是字符串。对于B的每个元素，计算其哈希值，然后使用它来查找A的一个元素。如果找到一个元素，则表示哈希匹配；然后您还需要比较字符串以检测它是真正的正例还是仅仅是偶然匹配。

计算匹配数。当该数字等于A的大小时，请停止并返回一个正结果。如果已处理完所有B的元素且匹配数小于A的大小，则返回一个负结果。

- kfx

如果B中的元素是A的严格超集，你如何检测A是否为B中元素的子集？它们的哈希值不会相同，对吗？ - Glubus

@Glubus 哦，我误读了问题。现在更新答案，描述简单的算法。我认为可能有更好的方法。 - kfx

1

是的，我现在明白你的意思了，这更有道理。不过，我确实喜欢CiaPan提出的二分查找的想法，如果A比某个B要小得多，那么这种搜索可能比遍历整个列表更有效率。 - Glubus

1

作为第一步，我会预先计算集合的一些通用属性，这些属性（希望）能够让您快速过滤一些B。例如：

字符串数量-如果A包含的元素比B多，则A肯定不能是B的子集；
最长字符串的长度-如果A中最长的字符串比B中最长的字符串更长，则A肯定不是B的子集；
字符串长度之和。

为了更容易地检查，您可能需要要求每个集合按字母顺序排序。这将允许在两组字符串的线性扫描中针对单个B检查A。

对于小的A和大的B集合，使用二分搜索查找B中的字符串可能比使用线性扫描更有效率；这也需要对B进行预排序。

- CiaPan

1

所有这些预先计算都应该在实际算法以某种启发式形式运行时完成，因为在运行某些算法之前进行它们需要对潜在的大输入进行多次循环。此外，如果A比B中的任何元素小得多，则二分查找将非常方便。 - Glubus

@Glubus 所有这些参数都只需要扫描每个集合一次，并且对每个字符串进行一次长度测试，因此它具有严格的线性时间成本和最小的内存成本（每个字符串集合存储三个整数）。// 是的，正如我上面所说，对于大小远小于大小 B 的情况，二分查找是有意义的。对于可比较的大小，半并行线性扫描会更容易。但是，二分查找需要将 B 中的字符串排序，这可能会增加排序的额外成本。 - CiaPan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Accepted Answer

一种高效的方法是将集合A表示为一棵Trie树。这样可以在线性时间内检查给定字符串是否属于A。

然后，没有比对所有Bi和Bi中所有字符串进行彻底检查更好的方法来确定它们是否属于A。当所有A中的字符串都被匹配（找到一个字符串时标记它）时，搜索停止。

运行时间最坏情况下将与所有B中所有字符串中的字符总数成比例。在实践中，会跳过相当大比例的字符，因为：

- 不在A中的字符串的搜索可以提前终止； - 子集测试可以得出肯定的结论，即使Bi中还有字符串； - 当A中未匹配的字符串比Bi中剩余的字符串多时，子集测试可以得出否定的结论。

这种方法在最坏情况下肯定是最优的，因为每个字符只读取一次，并且每个字符执行恒定数量的操作。