求助：基于LCS距离的相似短语聚类合并为统一列表问题

我有一个短语列表，示例如下：

words = ["client relationships","people management","collaborative teams","collaborative team","collaboration teams"……]

希望用最长公共子序列（LCS）距离度量（阈值0.2）筛选出相似但非相同的元素，将所有相似元素归为一个子列表，预期输出示例：

[["collaborative teams", "collaborative team","collaboration teams"]]

最初编写的代码运行后得到的是两两相似元素组成的子列表，不符合预期；修改后代码仍输出多个两两子列表，同时我还需要支持输出扁平列表（示例：["ability deliver", "ability develop","ability deliver", "quality delivery","ability drive", "ability deliver"]），求正确解决方案。

现有代码 #

初始代码 #

words= ["client relationships","people management","collaborative teams","collaborative team","collaboration teams".......]
list1=[]
for i in range(0,len(words)):
    for j in range(i+1,len(words)):
        t=[]
        v=metric_lcs(words[i],words[j])
        if v<=0.2:
            t.append(words[i])
            t.append(words[j])
            list.append(t)  # 原代码存在笔误，应为list1.append(t)

修改后代码 #

import itertools  # 原代码缺失该导入

list1 = []
for i in range(0,len(words)): 
    t=[]
    for j in range(i+1,len(words)):  
        v=metric_lcs(words[i],words[j])
        if v<=0.2:
            t.append(words[i])
            t.append(words[j])
            t=set(t)
            M=list(t)
            list1.append(M)
t=list1   
t.sort()
list(t for t,_ in itertools.groupby(t)) 

代码问题分析 #

1. 初始代码仅记录两两相似对，未将所有互相相似的元素合并为一个组，导致输出均为二元子列表。
2. 修改后的代码尝试用集合去重再分组，但itertools.groupby仅能对连续相同元素分组，且每次循环仅处理当前两两对，无法实现跨对的组合并。

解决方案 #

1. 将相似元素归为同一子列表（分组需求） #

此需求本质是无向图的连通分量问题：把每个短语看作节点，相似短语间连边，每个连通分量即为一组相似元素。

def metric_lcs(s1, s2):
    # 示例LCS距离计算逻辑，可替换为你的实现（返回0-1之间的距离值）
    len1, len2 = len(s1), len(s2)
    dp = [[0]*(len2+1) for _ in range(len1+1)]
    for i in range(1, len1+1):
        for j in range(1, len2+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    lcs_len = dp[len1][len2]
    max_len = max(len1, len2)
    return 1 - (lcs_len / max_len) if max_len !=0 else 0

words = ["client relationships","people management","collaborative teams","collaborative team","collaboration teams"]

# 构建相似关系图
graph = {word: [] for word in words}
for i in range(len(words)):
    word1 = words[i]
    for j in range(i+1, len(words)):
        word2 = words[j]
        if metric_lcs(word1, word2) <= 0.2:
            graph[word1].append(word2)
            graph[word2].append(word1)

# 查找所有连通分量（分组）
visited = set()
groups = []
for word in words:
    if word not in visited:
        stack = [word]
        visited.add(word)
        group = []
        while stack:
            current = stack.pop()
            group.append(current)
            for neighbor in graph[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
        # 仅保留包含多个元素的组（筛选相似非相同的元素）
        if len(group) > 1:
            groups.append(group)

print(groups)
# 输出：[['collaborative teams', 'collaborative team', 'collaboration teams']]

2. 生成相似元素的扁平列表 #

若需要输出所有相似对的扁平列表（保留重复元素），只需收集所有符合阈值的两两对并展开：

flat_list = []
for i in range(len(words)):
    word1 = words[i]
    for j in range(i+1, len(words)):
        word2 = words[j]
        if metric_lcs(word1, word2) <= 0.2:
            flat_list.append(word1)
            flat_list.append(word2)

print(flat_list)
# 输出示例：['collaborative teams', 'collaborative team', 'collaborative teams', 'collaboration teams', 'collaborative team', 'collaboration teams']

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