python 字典之间的传递性

Question

我在 python 中有一个如下所示的列表(真正的列表很大，我不能仅通过查看它来做到这一点):

original1=[['email', 'tel', 'fecha', 'descripcion', 'categ'],
          ['<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="0f6e4f68626e6663216c6062" rel="noreferrer noopener nofollow">[email protected]</a>', '1', '2014-08-06 00:00:06', 'MySpace a', 'animales'],
          ['<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="ddbf9dbab0bcb4b1f3beb2b0" rel="noreferrer noopener nofollow">[email protected]</a>', '1', '2014-08-01 00:00:06', 'My Space a', 'ropa'],
          ['<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="9afbdafdf7fbf3f6b4f9f5f7" rel="noreferrer noopener nofollow">[email protected]</a>', '2', '2014-08-06 00:00:06', 'My Space b', 'electronica'],
          ['<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="d0b290b7bdb1b9bcfeb3bfbd" rel="noreferrer noopener nofollow">[email protected]</a>', '3', '2014-08-10 00:00:06', 'Myace c', 'animales'],
          ['<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="d3b093b4beb2babffdb0bcbe" rel="noreferrer noopener nofollow">[email protected]</a>', '4', '2014-08-10 00:00:06', 'Myace c', 'animales']]

我将其分为数据和名称以处理数据:

datos=original1[-(len(original1)-1):len(original1)]

我需要做一个字典，将所有重复项放在一起，考虑电子邮件和电话，但我需要应用传递性:因为如果我们考虑电子邮件，则第 0 行 = 第 2 行，如果我们考虑电话，则第 1 行也 = 第 1 行1= 第 3 行如果我们再次考虑电子邮件，我需要得到这种情况下的所有候选者都是 0,1,2 和 3，而 4 是单独的。

我创建了以下代码:

from collections import defaultdict
email_to_indices = defaultdict(list) 
phone_to_indices = defaultdict(list)

for idx, row in enumerate(datos): 
    email = row[0].lower() 
    phone = row[1]
    email_to_indices[email].append(idx) 
    phone_to_indices[phone].append(idx)

所以现在我需要应用传递性规则，将 0 到 3 组合在一起，单独组合 4。

如果你打印

print 'email', email_to_indices
print 'phone', phone_to_indices

你得到:

email defaultdict(, {'[email protected]': [0, 2],'[email protected]': [1, 3], '[email protected]': [4]})

phone defaultdict(, {'1': [0, 1], '3': [3], '2': [2], '4': [4]})

不知道如何获得那些考虑传递属性的并集。 我需要得到类似的东西:

first_group: [0, 1, 2 , 3]
second_group: [4]

谢谢!

Answer 1

这里有一个图表，或者 Bipartite graph更准确地说。节点有两种类型:电子邮件和电话。如果存在该电子邮件和电话的记录，则两个节点将连接。或者我们甚至可以说记录本身就是连接两个节点的边。

任务是找到Connected components该图的。通过点击链接，您可以找到可以在线性时间内完成此操作的算法。

当然，也可以发明一些快速而肮脏的解决方案，如果您的数据集足够小，甚至可能被认为是合适的。

您可以在这里找到一些 Python 实现:Python connected components

更新:以下是如何构建图表的示例:

graph = {};
EMAIL = "email";
PHONE = "phone";

for rec in datos:
    graph.setdefault((EMAIL, rec[0]), set()).add((PHONE, rec[1]));
    graph.setdefault((PHONE, rec[1]), set()).add((EMAIL, rec[0]));

print "\n".join("%s: %s" % (str(node), str(linkedNodes)) for (node, linkedNodes) in graph.iteritems());

所以每个节点都有一个类型(EMAIL 或 PHONE，它们实际上可以只是整数，例如 0 和 1，我将它们设置为字符串只是为了更好的打印)和一个值。图是一个字典，以节点为键，将连接的节点集作为值。