在一系列集合中查找出现在至少N个集合中的所有子集

Question

我正在研究一种通过搜索引擎中相同网址数量对关键词进行分组的算法。每个分组代表一个网址，每个值是该网址在SERP中出现的关键词的ID。

---

我有一个分组列表：

groups = [
    [1],
    [1, 2 ,3],
    [1, 2, 3, 4, 5],
    [1, 2, 3 ,4], 
    [2, 3],
    [4, 5, 6],
    [4, 5, 7]
]

我需要获取所有至少在N个组中出现的项目集，并按“大小”递减的顺序排列：

例如，对于N=3，我们有两个子集： [1，2，3]和[4，5]

如何获取它： 迭代1：找到至少出现3次的最大集合（它是[1，2，3]），并从其出现的所有集合中删除。

迭代后，我们有：

groups = [
        [1],
        [4, 5],
        [4], 
        [2, 3],
        [4, 5, 6],
        [4, 5, 7]
    ]

第二轮迭代：找出至少出现3次的最大值（它是[4, 5]）

迭代后我们得到：

groups = [
        [1],
        [4], 
        [2, 3],
        [6],
        [7]
    ]

算法结束：因为没有更多的集合在组中至少出现3次。

---

你有任何获取它们的算法想法吗？

N 在1到10之间。

p.s. 组列表非常大，从1000到10000个项目。数字是数据库中对象的ID。

- Alex T

---

为什么 [1, 2, 3] 是一个组，但 [1]、[1, 2] 或 [1, 2, 3, 4] 不是？ - mcmlxxxvi

表述不清楚，问题不明确。请更精确地定义群组约束条件。虽然我认为我理解了想法，但更详细的说明会更有帮助。 - sascha

说真的... 你现在的编辑让描述更糟了。我可以给你一个简单的算法，与你描述的兼容，但它并不能真正解决你的问题，因为我不知道你的问题具体是什么。你所说的排除最大子集是什么意思？当你说物品的子集时：[1]是一个物品的子集，并且出现>=N次。 - sascha

为什么[4, 5]是一组而[2, 3]不是？ - Yury Tarabanko

好吧，如果有多达10000个集合和高达10的N，那么我的itertools想法可能行不通。二项式系数C（10000,10）大约为2.7 x 10 ** 33。交集所有的10组集合的暴力方法行不通。所有组的联合有多大？（在您的示例中，它有7个项目）。如果与组的数量相比这个数字很小（如果存在许多重复），则有一些可以使用的想法。 - John Coleman

Answer 1

一个第一版的方法/黑客，结合了递归、伪函数式编程和我自己的一些破事。有很多可以改进的地方，特别是关于迭代器/列表。也许这甚至可以称为意大利面条代码 :-).

警告：请参见@John Coleman关于二项式系数的评论。我们在每次迭代中生成所有可能的剩余值子集。如果使用惰性生成器，则可能会得到改进（但对于大量唯一数字的集合仍将不可行）。

import itertools

groups = [
    [1],
    [1, 2 ,3],
    [1, 2, 3, 4, 5],
    [1, 2, 3 ,4],
    [2, 3],
    [4, 5, 6],
    [4, 5, 7]
]

def solve(groups, N, sol=[]):
    if len(groups) == 0:
        return sol

    rem_vals = list(set(itertools.chain(*groups)))
    combs = list(itertools.product(range(2), repeat=len(rem_vals)))
    combs_ = [[rem_vals[ind] for ind, i in enumerate(combs[comb]) if i] for comb in range(len(combs))]

    for cand in reversed(sorted(combs_, key=lambda x: len(list(itertools.chain(x))))):
        if len(cand) == 0:
            continue
        else:
            counter = 0
            inds = []
            for ind, g in enumerate(groups):
                if set(cand).issubset(g):
                    counter += 1
                    inds.append(ind)

            if counter >= N:
                sol.append(cand)
                for i in inds:
                    for j in cand:
                        groups[i].remove(j)
                return solve(groups, N, sol)

    return sol

print(solve(groups, 3))

输出

[[1, 2, 3], [4, 5]]

- sascha

---

针对200个短语和1880个链接（即len(groups)），在10秒内程序的内存使用量超过了12GB，因此我无法在真实数据上使用您的解决方案 :) - Alex T

我认为有人询问了你集合中唯一值的数量，但你没有回应。当然，如果这个集合很大，它是行不通的。John Coleman的解决方案也是如此。你可以将列表转换为生成器以改善内存使用，但时间性能不会改变。 - sascha

John Coleman的解决方案是可行的，但需要几分钟才能得到结果。我会寻找另一种解决这个问题的方法。 - Alex T

我指出了这些方法的不同之处。只需要进行一些修改。其中一个使用更多的内存，速度更快，另一个则较慢但需要更少的内存。由你来选择。 - sascha

抱歉，我错过了关于唯一值的问题。对于1880个集合，有180个唯一值。就是这样。 - Alex T

Answer 2

这里是使用 itertools 的方法来完成您所称的 迭代 1 的第一部分。如果有可能运行它，那么您可以在循环中反复运行它，在每个阶段删除找到的项。正如我在评论中指出的那样，它只适用于小的 n。

import itertools

def intersect(sets):
    #forms the intersection of all s in sets
    #assumes that there is at least one

    I = sets[0].copy()
    for s in sets[1:]:
        I = I & s
    return I

def largestIntersection(sets,n):
    maxSize = 0
    maxSets = [set()]
    for groupCombo in itertools.combinations(sets,n):
        I = intersect(groupCombo)
        if len(I) > maxSize:
            maxSize = len(I)
            maxSets = [I]
        elif len(I) == maxSize:
            maxSets.append(I)
    return maxSets

例如：

>>> groups = [
    [1],
    [1, 2 ,3],
    [1, 2, 3, 4, 5],
    [1, 2, 3 ,4],
    [2, 3],
    [4, 5, 6],
    [4, 5, 7]
]
>>> groups = [set(group) for group in groups]
>>> largestIntersection(groups,3)
[{1, 2, 3}]

编辑：以下修改可能有所帮助——取决于组中数字的分布和组的大小：

def guessSize(sets,n,trials):
    return max(len(intersect(random.sample(sets,n))) for trial in range(trials))

def maxIntersection(sets,n,trials = 100000):
    k = guessSize(sets,n,trials)
    filteredSets = [s for s in sets if len(s) >= k]
    return largestIntersection(filteredSets,n)

首先，想法是在尝试遍历交集之前先减少组的数量。例如：

#stress test:

import random
nums = list(range(1,101))
testGroups = [set(random.sample(nums,random.randint(1,100))) for n in range(1000)]
foundGroups = maxIntersection(testGroups,3)

如果我直接使用largestIntersection(testGroups)，计算foundGroups需要几分钟，但只需几秒钟。另一方面，如果随机参数选择不同，则时间节省变得微不足道。

进一步编辑: 也许您可以更加积极地过滤：

import collections
def maxIntersection(sets,n,trials = 100000):
    k = guessSize(sets,n,trials)
    filteredSets = [s for s in sets if len(s) >= k]
    counts = collections.Counter()
    for s in filteredSets:
        for x in s:
            counts[x] +=1
    t = {x for x,c in counts.items() if c >= k}
    filteredSets = [s & t for s in filteredSets if len(s & t) >= k]
    return largestIntersection(filteredSets,n)

- John Coleman

---

它能运行，但速度真的很慢...使用集合是个坏主意。谢谢。 - Alex T

这与集合作为数据结构本身无关。它涉及到我们需要尝试的组合。 - sascha

@sascha，当然是的。我的意思是解决问题的一般方法。 - Alex T

@AlexT 看起来这是一个算法上的难题。看看编辑中的优化是否有帮助。 - John Coleman