Python如何高效移除列表中逆序重复的bigram、trigram元素

核心结论 #

• 不需要为bigrams、trigrams分别编写独立的逆序去重逻辑，一套通用实现可以适配任意长度的n-gram场景
• 基于哈希集合的去重方案时间复杂度为O(n)，处理1万条以上数据耗时在毫秒级，完全满足性能要求，写法简洁符合Python编码习惯

原有代码问题说明 #

你之前尝试的代码用set处理分词后的词组存在两个致命问题：

1. set是无序且自动去重的结构，一旦n-gram内存在重复词（比如trigram come come go）会直接丢失词序、词数信息，判断逻辑完全失效
2. 逻辑中没有做正序/逆序的匹配校验，本质上没有实现逆序重复的判断能力，自然无法输出正确结果

通用高效实现 #

核心逻辑：对每个n-gram字符串分词后，取正序词元组、逆序词元组的较小值作为唯一去重标识——互为完全逆序的两个词组，生成的这个标识是完全一致的。遍历列表时只保留第一次遇到对应标识的原字符串，后续重复标识直接跳过即可。

def remove_reverse_duplicates(ngram_list):
    seen = set()
    res = []
    for item in ngram_list:
        words = item.split()
        # 生成全局唯一的去重key，逆序对的key完全相同
        dedup_key = min(tuple(words), tuple(reversed(words)))
        if dedup_key not in seen:
            seen.add(dedup_key)
            res.append(item)
    return res

# 测试验证
L1 = ['worry not', 'be happy', 'very good', 'not worry', 'good very', 'full stop']
L2 = ['take into account', 'always be happy', 'stay safe friend', 'happy be always']

print(remove_reverse_duplicates(L1))
# 输出：['worry not', 'be happy', 'very good', 'full stop']
print(remove_reverse_duplicates(L2))
# 输出：['take into account', 'always be happy', 'stay safe friend']

性能说明 #

• 整套逻辑仅做单次列表遍历，集合的key查找、插入操作平均时间复杂度为O(1)，单条字符串的分词、元组对比都是常数级操作，10万条级别的n-gram数据也可以在极短时间内处理完成
• 用元组作为key而非集合、字符串拼接等结构，既可以完整保留词序、词数信息，避免带重复词的n-gram出现误判，也比字符串拼接的生成速度更快，内存占用更低
• 逻辑默认保留第一次出现的原始字符串顺序，和你给出的预期输出规则完全一致

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