根据数据的特征是否相交对数据进行分组

Question

假设我们有一张桌子：

id  | aliases
-------------
0   | ['a0', 'a1', 'a4', 'a11']
1   | ['a3', 'a5']
2   | ['a16', 'a18']
3   | ['a6', 'a8', 'a10']
4   | ['a7', 'a8', 'a9']
5   | ['a3', 'a12', 'a14']
6   | ['a5', 'a16', 'a17']

我想把所有映射到同一个aliases的id组合在一起；换句话说，最终结果将所有id相交的aliases分组，递归应用。在上述情况下，我们将：

• 0映射到['a0', 'a1', 'a4', 'a11']
• 1、2、5和6映射到['a3', 'a5', 'a12', 'a14', 'a16', 'a17', 'a18']
• 3和4映射到['a6', 'a7', 'a8', 'a9', 'a10']

有没有有效的方法？在我的实际用例中，我有大约15M行

有一个naï对行进行流式处理并检查每个新行中aliases的每个元素是否在到目前为止处理的aliases中的ve方法；如果是这样，则将具有匹配aliases的所有行的id集合在一起，并将它们映射到匹配的aliases的并集

然而，这种方法在计算上似乎不切实际

Answer 1

在这个表上运行一个O(n*len(groupcount)复杂代码应该不是那么难，只是我脑子里想不起来：

假设id作为id列表，aliases作为列表列表，您可以执行以下操作：

bins = []
sets = []
for i in id: # Assume from (0 - n)
    alias = aliases[i]
    in_set = False
    for j in range(len(sets)):
        if len(sets[j].intersection(set(alias))) > 0:
            sets[j].update(set(alias)) # add alias to set, if any difference
            in_set = True
            bins[j].append(i) # append id to bins
            break
    if not in_set:
        bins.append([i])
        sets.append(set(alias))

bins将包含id组，sets中的相应元素将包含alias组，您可以使用list()将这些集合转换回list。因为所有的set操作都是基于哈希的，所以这可以确保程序在O(n*groupcount)时间内运行