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

Efficient way to find array with the largest intersection to an input array

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

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

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

[('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')]

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

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

我建议使用哈希集的 straight-forward 方法。
如果 hashset 实现得很好,有一个好的 hash 函数,那么我们可以考虑检查一个元素是否是这个集合的一部分可以在 O(1).
中完成 然后,我们可以进行以下操作:

function find_closest_arrays(A, B_1, ..., B_n) {
    result = [0, ..., 0] // array of size n
    for elem in A {
        for i in 1 ... n {
            if elem is in B_i {
                result[i] ++
            }
        }
    }
    return result
}

这个函数return一个数组resultresult[i] 包含输入数组 AB_i 之间共有的元素数。
从这里开始,获得 k 最好的是非常直接的,你所要做的就是获得 result.
k 最大数字的索引 该算法的时间复杂度为 O(n * m),输入数组的大小为 m,数组集的大小为 n

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

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

迭代

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

如果您还对数组本身进行排序,则可以利用汉明顿距离,但您不必同时对所有数组进行排序和转换,而只需从其中的一部分开始。如果您不使用 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,然后从那里用它们填充一棵树并遍历它直到没有进一步的遍历会导致更小的距离。我不知道这有多有效。