Python实现列表相似项合并：保留独立相似词对

给定包含相似词（用|分隔）和独立词的列表：

input = ["car | cat", "cat | caat", "car | caar", "dog", "ant | ants"]

需要合并所有关联的相似项，得到目标输出：

output = ["car | cat | caat | caar", "dog" , "ant | ants"]

现有代码会将ant | ants拆分为独立元素，不符合需求，需修正Python实现。

原代码问题分析 #

原代码通过统计词频判断合并逻辑，但ant和ants仅在同一条目内出现，词频均为1，因此被误判为独立词拆分。核心缺陷是未识别同一条目内的关联关系，仅依赖词频无法区分内部关联的独立条目。

修正后的实现 #

from collections import defaultdict

def merge_related_groups(input_list):
    # 初始化并查集父节点字典
    parent = {}
    
    def find(x):
        # 查找根节点，路径压缩优化
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        # 合并两个节点的连通关系
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            parent[root_y] = root_x
    
    # 遍历所有条目，建立词的连通关系
    for item in input_list:
        words = item.split(" | ")
        # 为每个词初始化父节点
        for word in words:
            if word not in parent:
                parent[word] = word
        # 合并当前条目内的所有词
        if len(words) > 1:
            base_word = words[0]
            for word in words[1:]:
                union(base_word, word)
    
    # 按根节点分组所有词
    groups = defaultdict(list)
    for word in parent:
        groups[find(word)].append(word)
    
    # 整理成目标格式的结果列表
    result = [" | ".join(group) for group in groups.values()]
    return result

# 测试示例
input_data = ["car | cat", "cat | caat", "car | caar", "dog", "ant | ants"]
print(merge_related_groups(input_data))
# 输出: ['car | cat | caat | caar', 'dog', 'ant | ants']

代码说明 #

• 并查集（Union-Find）：高效管理词的连通关系，同一|分隔的词、跨条目关联的词都会被合并到同一连通组。
• 路径压缩：优化find方法，提升后续查找效率。
• 分组整理：所有词按连通组聚合，最终转换为|分隔的字符串格式，完美匹配需求。

内容的提问来源于stack exchange，提问作者y_e