Python 字典之间的传递性

Question

我在Python中有一个像下面这样的列表（实际上这个列表很大，我不能仅仅通过查看它来处理）：

original1=[['email', 'tel', 'fecha', 'descripcion', 'categ'],
          ['a@gmail.com', '1', '2014-08-06 00:00:06', 'MySpace a', 'animales'],
          ['b@gmail.com', '1', '2014-08-01 00:00:06', 'My Space a', 'ropa'],
          ['a@gmail.com', '2', '2014-08-06 00:00:06', 'My Space b', 'electronica'],
          ['b@gmail.com', '3', '2014-08-10 00:00:06', 'Myace c', 'animales'],
          ['c@gmail.com', '4', '2014-08-10 00:00:06', 'Myace c', 'animales']]

我把数据和名字分开，以便处理数据：

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

我需要做一个字典，把所有重复的项放在一起，考虑到邮箱和电话，但我需要应用传递性：因为第0行和第2行如果考虑邮箱是相等的，但第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(, {'a@gmail.com': [0, 2],'b@gmail.com': [1, 3], 'c@gmail.com': [4]})

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

我不知道怎么根据传递性来合并这些项。我需要得到类似这样的结果：

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

谢谢！

Answer 1

这是另一种方法：

当你在创建 email_to_indices 这个字典时，可以把每一行的电话号码作为值存储，然后在 phone_to_indices 中保存这一行的索引。这样，我们就建立了一个从 email_to_indices 到 phone_to_indices 再到行索引的映射关系。

通过这样的修改和一些基本的集合操作，我能够准确地得到你想要的结果：

from collections import defaultdict

email_to_indices = defaultdict(list)
phone_to_indices = defaultdict(list)
combined = defaultdict(set)

original=[['email', 'tel', 'fecha', 'descripcion', 'categ'],
          ['a@gmail.com', '1', '2014-08-06 00:00:06', 'MySpace a', 'animales'],
          ['b@gmail.com', '1', '2014-08-01 00:00:06', 'My Space a', 'ropa'],
          ['a@gmail.com', '2', '2014-08-06 00:00:06', 'My Space b', 'electronica'],
          ['b@gmail.com', '3', '2014-08-10 00:00:06', 'Myace c', 'animales'],
          ['c@gmail.com', '4', '2014-08-10 00:00:06', 'Myace c', 'animales']]


for idx, row in enumerate(original[1:], start=1):
    email = row[0].lower()
    phone = row[1]
    email_to_indices[email].append(phone) # Here is what I changed
    phone_to_indices[phone].append(idx)

random_key = 0
for idx, row in enumerate(original[1:], start=1):
    grouped_rows = []
    if row[0].lower() in email_to_indices:
        for phone_no in email_to_indices[row[0].lower()]:
            grouped_rows.extend(phone_to_indices[phone_no])

    if len(combined[random_key]) > 0 and len(set(grouped_rows).intersection(combined[random_key])) > 0:
        combined[random_key].update(set(grouped_rows))
    elif len(combined[random_key]) > 0:
        random_key += 1
        combined[random_key].update(set(grouped_rows))
    else:
        combined[random_key].update(set(grouped_rows))

print combined

这样就得到了：

defaultdict(<type 'set'>, {0: set([1, 2, 3, 4]), 1: set([5])})

Answer 2

这里有一个图，或者更准确地说，是一个二分图。这个图里的节点有两种类型：邮箱和电话。如果有记录显示某个邮箱和某个电话是关联的，那么这两个节点就连在一起。我们甚至可以说，这条记录本身就是连接这两个节点的边。

我们的任务是找到这个图的连通分量。通过链接你可以找到一些算法，它们可以在很短的时间内完成这个任务。

当然，也可以想出一些简单粗暴的解决方案，如果你的数据集足够小，这些方案甚至可以被认为是合适的。

你可以在这里找到一些Python的实现：Python连通分量

更新：下面是一个如何构建这个图的例子：

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，我把它们做成字符串只是为了好看）和一个值。这个图是一个字典，节点作为键，连接的节点集合作为值。