如何从百万级序列列表中筛选仅单位置A/B替换的序列对？

问题描述 #

给定百万级规模的序列列表，示例如下：

List = ["ASHAOSHZO", "BSHZOSHZO", "ASHBOSHZO","EIBDEDIED", "EIBDEDIEA",  "IJZUHDIZUDB", "JLZOAUUIGIZ"]

需求为筛选出仅在同一位置存在单个字符（A/B互换）差异的序列对，示例结果如下：

res = [("ASHAOSHZO", "BSHZOSHZO"), ("ASHAOSHZO", "ASHBOSHZO")]

需解决该需求的优化实现问题。

常规方法的局限性 #

如果采用双重循环两两比对所有序列，时间复杂度为O(n²)，对于百万级数据来说，计算量会达到万亿级别，完全无法在合理时间内完成，必须通过哈希表优化来降低时间复杂度。

优化思路 #

核心思路是通过预生成变体键+哈希表存储，将比对操作从O(n²)降到O(n*L)（L为单条序列的长度）：

• 对每条序列，生成所有可能的"A/B互换变体"：遍历序列的每个位置，若该位置是A则换成B，是B则换成A，得到对应的"变体键"。
• 用哈希表（字典）存储每个变体键对应的原始序列列表：当处理当前序列时，如果某个变体键已存在于字典中，说明当前序列与该键对应的所有序列都符合"单位置A/B互换"的条件。
• 通过集合存储结果，避免重复记录反向配对（如(A,B)和(B,A)只保留一次）。

实现代码 #

def find_ab_swap_pairs(sequences):
    from collections import defaultdict
    variant_map = defaultdict(list)
    result = set()

    for seq in sequences:
        seq_len = len(seq)
        for idx in range(seq_len):
            current_char = seq[idx]
            # 只处理A/B字符的位置
            if current_char not in ('A', 'B'):
                continue
            # 生成A/B互换后的变体键
            swapped_char = 'B' if current_char == 'A' else 'A'
            variant_key = seq[:idx] + swapped_char + seq[idx+1:]
            # 匹配已存在的序列，生成有效配对
            if variant_map[variant_key]:
                for matched_seq in variant_map[variant_key]:
                    # 排序确保配对唯一，避免重复
                    sorted_pair = tuple(sorted((seq, matched_seq)))
                    result.add(sorted_pair)
            # 将当前序列加入对应变体键的列表
            variant_map[variant_key].append(seq)
    
    return list(result)

# 测试示例
sample_sequences = ["ASHAOSHZO", "BSHZOSHZO", "ASHBOSHZO","EIBDEDIED", "EIBDEDIEA",  "IJZUHDIZUDB", "JLZOAUUIGIZ"]
print(find_ab_swap_pairs(sample_sequences))

方案优势 #

1. 时间效率：总操作数为O(n*L)，百万级数据配合常规长度的序列（如10-50位），可在数秒内完成计算。
2. 空间可控：哈希表仅存储变体键对应的序列列表，大部分变体键不会重复，空间开销处于合理范围。
3. 自动去重：通过集合和排序配对，避免了重复记录反向配对的问题。

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