自定义规则下大规模字符串模糊分组的算法优化与结果修正

你的代码现在有两个核心问题：

1. 分组结果不符合预期：原fuzzyMatch规则会把单个词（如misha）和带前缀的同尾词（如m misha）归为一组，这和你想要的分组逻辑不符。
2. 大规模数据处理慢：原fuzzyGroup用双重循环遍历所有已有组，还额外做了全局存在性检查，时间复杂度是O(n²)，数据量一大就会卡顿。

1. 修正相似性匹配规则 #

调整fuzzyMatch的逻辑，让单个词和带前缀的同尾词得分低于阈值（0.5），同时保证同类型（都是带相同前缀的多词/都是单字词）的同尾词能正确匹配：

def fuzzyMatch(w1, w2):
    score = 0
    parts1 = w1.split()
    parts2 = w2.split()
    
    lastword1 = parts1[-1]
    lastword2 = parts2[-1]
    
    # 最后一个单词不同直接返回0
    if lastword1 != lastword2:
        return 0
    
    score += 0.5
    
    # 单字词和多字词直接判定不匹配（得分低于0.5）
    if len(parts1) != len(parts2):
        return 0.4
    
    # 多字词之间，检查前缀首字母是否一致
    init1 = parts1[0][0]
    init2 = parts2[0][0]
    
    if init1 == init2:
        score += 0.1
    else:
        score -= 0.1
    
    return score

2. 优化分组算法提升速度 #

放弃原有的双重循环，改用字典分组+分层处理的思路：

• 第一步：先按最后一个单词做第一层分组，把不同尾词的句子彻底分开，避免无效比较。
• 第二步：在每个尾词组内，根据句子类型（单字词/多字词+前缀首字母）生成唯一key，用字典快速分组，时间复杂度降到O(n)，处理大规模数据时效率提升明显。

优化后的分组函数：

def fuzzyGroup(words):
    # 第一层：按最后一个单词分组，缩小后续处理范围
    lastword_map = {}
    for word in words:
        last_word = word.split()[-1]
        if last_word not in lastword_map:
            lastword_map[last_word] = []
        lastword_map[last_word].append(word)
    
    output = []
    # 第二层：对每个尾词组内的句子细分
    for group in lastword_map.values():
        subgroup_map = {}
        for word in group:
            parts = word.split()
            # 生成分组key：单字词用自身做key，多字词用(尾词+前缀首字母)做key
            if len(parts) == 1:
                key = word
            else:
                key = (parts[-1], parts[0][0])
            
            if key not in subgroup_map:
                subgroup_map[key] = []
            subgroup_map[key].append(word)
        
        output.extend(subgroup_map.values())
    
    return output

把修正后的函数替换原代码，运行后就能得到你想要的结果：

def fuzzyMatch(w1, w2):
    score = 0
    parts1 = w1.split()
    parts2 = w2.split()
    
    lastword1 = parts1[-1]
    lastword2 = parts2[-1]
    
    if lastword1 != lastword2:
        return 0
    
    score += 0.5
    
    if len(parts1) != len(parts2):
        return 0.4
    
    init1 = parts1[0][0]
    init2 = parts2[0][0]
    
    if init1 == init2:
        score += 0.1
    else:
        score -= 0.1
    
    return score

def fuzzyGroup(words):
    lastword_map = {}
    for word in words:
        last_word = word.split()[-1]
        if last_word not in lastword_map:
            lastword_map[last_word] = []
        lastword_map[last_word].append(word)
    
    output = []
    for group in lastword_map.values():
        subgroup_map = {}
        for word in group:
            parts = word.split()
            if len(parts) == 1:
                key = word
            else:
                key = (parts[-1], parts[0][0])
            
            if key not in subgroup_map:
                subgroup_map[key] = []
            subgroup_map[key].append(word)
        
        output.extend(subgroup_map.values())
    
    return output

input_list= ['okushka', 'm misha', 'p valeri', 'm misha', 'o misha', 'p a valeri', 'o okushka', 'o olya', 'olya olya', 'o ol olya', 'misha', 'j okushka']

sorted_list = sorted(input_list,key=lambda x: x.split()[-1])

grouped_list = fuzzyGroup(sorted_list)

print('grouped:', grouped_list)

运行输出：

grouped: [['m misha', 'm misha'], ['o misha'], ['misha'], ['okushka'], ['o okushka'], ['j okushka'], ['o olya', 'olya olya', 'o ol olya'], ['p valeri', 'p a valeri']]

完全符合你的期望输出。

如果之后需要调整相似性规则，只需要同步修改fuzzyMatch和fuzzyGroup中生成key的逻辑即可，保证两者的判定逻辑一致，就能维持分组的准确性和效率。

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