python - 如何使用第一次出现的键作为起点对字典中的所有链接进行分组？

Question

我有这样一本字典，

matches = {'2-8-7 Yaesu, Chuo-Ku': ['Chuo Ward, Yaesu 2-8-7'],
           'Chuo Ward, Yaesu 2-8-7': ['2-8-7 Yaesu, Chuo-Ku'],
           'Fukuoka Bldg 10Th Floor': ['Fukuoka Building, 9Th -10Th Flr.'],
           'Fukuoka Bldg. 8-7 Yaesu Chome': ['2-8-7 Yaesu, Chuo-Ku', 
                                             'Fukuoka Building, 8-7, Yaesu 2 Chome, Chuo-Ku'],
           'Fukuoka Bldg. 9Th Fl': ['Fukuoka Building 9Th Floor'],
           'Fukuoka Building 9Th Floor': ['Fukuoka Bldg. 9Th Fl', 
                                          'Fukuoka Building, 9Th -10Th Flr.']}

我想通过查找链接(带有键或值)将它们组合在一起，键可以是任何东西(或)只是您遇到的第一个键，这是起点。

这是我期待的期望输出，

{'2-8-7 Yaesu, Chuo-Ku': ['Chuo Ward, Yaesu 2-8-7',
                          '2-8-7 Yaesu, Chuo-Ku',
                          'Fukuoka Building, 8-7, Yaesu 2 Chome, Chuo-Ku',
                          'Fukuoka Bldg. 8-7 Yaesu Chome'],
 'Fukuoka Bldg 10Th Floor': ['Fukuoka Building, 9Th -10Th Flr.',
                             'Fukuoka Bldg. 9Th Fl',
                             'Fukuoka Building 9Th Floor',
                             'Fukuoka Bldg. 9Th Fl']}

我试过了，

unique_lst = set()
merged_matches = dict()
for key, values in matches.items():
    if key not in unique_lst:
        values_lst = []
        for v in values:
            output = matches.get(v)
            for subkeys, subvals in matches.items():
                if key != subkeys and v != subkeys:
                    keyvals = [subkeys] + list(subvals)
                    if v in keyvals:
                        values_lst.extend(keyvals)
            if output:
                values_lst.extend(output)
            values_lst.append(v)

        values_lst = [i for i in values_lst if i != key]
        values_lst = values_lst + [key]
        for v in values_lst:
            unique_lst.add(v)
            
        merged_matches[key] = values_lst

这是我得到的输出，

# print(merged_matches)

{'Fukuoka Bldg. 9Th Fl': ['Fukuoka Building, 9Th -10Th Flr.',
                          'Fukuoka Building 9Th Floor',
                          'Fukuoka Bldg. 9Th Fl'],
 'Fukuoka Bldg. 8-7 Yaesu Chome': ['Chuo Ward, Yaesu 2-8-7',
                                   '2-8-7 Yaesu, Chuo-Ku',
                                   'Chuo Ward, Yaesu 2-8-7',
                                   '2-8-7 Yaesu, Chuo-Ku',
                                   'Fukuoka Building, 8-7, Yaesu 2 Chome, Chuo-Ku',
                                   'Fukuoka Bldg. 8-7 Yaesu Chome'],
 'Fukuoka Bldg 10Th Floor': ['Fukuoka Building 9Th Floor',
                             'Fukuoka Bldg. 9Th Fl',
                             'Fukuoka Building, 9Th -10Th Flr.',
                             'Fukuoka Building, 9Th -10Th Flr.',
                             'Fukuoka Bldg 10Th Floor']}

Answer 1

IMO，问题归结为查找由字典导出的图的连通分量。您可以这样做的一种方法是使用 UnionFind 数据结构来获取由键和值构造的不相交集的列表。

然后我们可以通过选择一个元素作为键，其余元素作为值，从合并的集合中构造一个字典。

from networkx.utils.union_find import UnionFind
c = UnionFind()
for k, lst in matches.items():
    c.union(*[k, *lst])

out = {k: v for k, *v in map(list, c.to_sets())}

输出:

{'Chuo Ward, Yaesu 2-8-7': ['2-8-7 Yaesu, Chuo-Ku',
  'Fukuoka Bldg. 8-7 Yaesu Chome',
  'Fukuoka Building, 8-7, Yaesu 2 Chome, Chuo-Ku'],
 'Fukuoka Building 9Th Floor': ['Fukuoka Bldg 10Th Floor',
  'Fukuoka Bldg. 9Th Fl',
  'Fukuoka Building, 9Th -10Th Flr.']}