algorithm - 查找与输入数组具有最大交集的数组的有效方法

Question

假设我有一大组数组(大小可达数百万)，我想确定(最好是准确地，虽然近似是好的)这个集合中与输入有最大交集的数组，什么将是最有效的方法吗？我会在底部列出一些我想到的解决方案，将其简化为另一个问题，但我不确定它们是否一定是最好的。

这组数组可以存储在任何数据结构中，数组可以按任何方式排序存储。这个想法是在这里优化查询时间。

示例:假设我的数组集是(为方便起见，以类似基数的方式排序，可以以任何选择的方式排序):

[('a', 'b'), ('a', 'e', 'f'), ('b', 'f', 'g'), ('b', 'j', 'z'), ('d', 'l', 'f'), ('x', 'y', 'z')]

我的输入数组是:

('a', 'f')

那么各自的交集是:

[('a'), ('a', 'f'), ('f'), (), ('f'), ()]

因此输出将是 ('a', 'f')，具有大小为 2 的最大交集。作为奖励，拥有最大的 K 会更好 这些，所以在这里，如果 K = 3，输出将是(以任何顺序):

[('a', 'f'), ('f'), ('a')]

我想到的一些可能的解决方案:

• 我的域的大小受到限制，(因为它可能是 a-z 或数字 1-70 等)所以我可以将它们表示为二进制字符串，现在的挑战变成了找到最小的汉明顿距离，我现在可以用像局部散列这样的东西来做？例如 ('a', 'f') 可以表示为 10000100000000000000000000
• 还利用域受限制的事实，我可以创建一些域中的项目指向不同的倒排索引集合中的数组，然后为输入数组中的每个项目与这些结果(至少一些)相交——尽管我觉得这样会非常低效(特别是如果十字路口转弯出很小)- 类似于谷歌搜索的工作方式，虽然我不知道他们算法的全部细节

感谢您对正确方向的任何回应或指示!

Answer 1

一些事先由于缺乏声誉而无法通过评论提出的问题:

1. 所有数组都是唯一的，但每个数组本身都是一个集合吗？
2. 如果多个数组共享最大的交集大小，您是否需要将它们全部列出？
3. 您的输入可能比给定的最长数组长？

迭代

如果没有 hashset，我会按长度对数组进行排序，并从最长的数组开始，最后可能会通过找到一个大于或等于较短数组大小的交集大小来跳过较短的数组。

如果您还对数组本身进行排序，则可以使用 Hammington 距离，但您不必同时对所有数组进行排序和转换，而只需从它们的一部分开始。如果您不使用 Hammington 请记住，如果您将输入与输入大小为 + 1 的数组进行比较，则只需进行比较，直到遇到输入的最后一个元素小于当前数组的第一个比较元素。

a f

a c k z // since k > f we don't need to compare f and z

我认为这种方式会归结为 O(n lg n) 的复杂度，因为按大小对数组排序是 O(n lg n)，计算大小 n * O(1) 并进行内基数排序 O(n)。比较本身将是 O(n lg n)(对此不太确定)所以总数将是 O(n lg n) * 2 + 2 * O(n) => O(n lg n)。

树

只是一个粗略的想法:您可以使用 Radix 对所有数组进行排序并将它们转换为 Hemmington，然后从那里用它们填充一棵树并遍历它直到没有进一步的遍历会导致更小的距离。我不知道这有多有效。

https://stackoverflow.com/a/6390606/9758920