如何高效从大型列表中通过子串匹配目标字符串

我有两个各约500万条数据的列表：

• List_1：由二元字符串元组组成，例如("foo", "bar")
• List_2：长字符串列表，例如["flub", "blub", "barstool", "foo & bar: misadventures in python"]

需求是从List_2中找出包含List_1中元组组成的复合字符串（格式为"{元组第一个元素} & {元组第二个元素}"）的条目。

当前实现逻辑是遍历List_1，对每个元组生成复合串后，在List_2中逐个查找匹配项。单次List_2查找耗时约1秒，但遍历完整List_1需要近1000小时，效率极低。曾尝试用集合交集匹配，但该方法仅支持整串匹配，不符合需求。

当前代码示例：

list_1 = [] # 填入数据
list_2 = [] # 填入数据

for search_term in list_1:
    compound_string = "{search_first} & {search_second}".format(search_first=search_term[0], search_second=search_term[1])
    result = next((s for s in list_2 if compound_string in s), None) # 短路查找，无需遍历整个列表
    if result:
        # 后续处理逻辑

方法1：反向处理，从List_2提取复合串匹配List_1 #

将List_1转换为复合串集合（或字典），再遍历List_2提取所有符合格式的子串进行匹配，仅需遍历List_2一次，效率大幅提升。

步骤代码：

# 预先生成List_1的复合串集合，实现O(1)查找
compound_set = {f"{a} & {b}" for a, b in list_1}

import re
# 预编译正则，匹配"X & Y"格式（X、Y为不含&的非空字符串）
pattern = re.compile(r'([^&]+) & ([^&]+)')

matches = []
for s in list_2:
    # 提取当前字符串中所有符合格式的子串
    found_pairs = pattern.findall(s)
    for a, b in found_pairs:
        compound = f"{a} & {b}"
        if compound in compound_set:
            matches.append((s, (a, b)))
            break  # 找到匹配项后停止当前字符串的后续查找

方法2：用Aho-Corasick多模式匹配算法 #

针对大规模多模式匹配场景，使用Aho-Corasick自动机可以一次性将所有复合串作为匹配模式，批量在List_2中查找，时间复杂度接近线性。

需借助第三方库pyahocorasick实现：

import ahocorasick

# 初始化自动机
automaton = ahocorasick.Automaton()

# 将所有复合串加入自动机，值关联原元组
for a, b in list_1:
    compound = f"{a} & {b}"
    automaton.add_word(compound, (compound, (a, b)))

automaton.make_automaton()

matches = []
for s in list_2:
    # 在当前字符串中查找所有匹配的复合串
    for end_idx, (compound, term) in automaton.iter(s):
        matches.append((s, term))
        break  # 找到匹配项后停止当前字符串的后续查找

方法3：预处理List_2建立倒排索引 #

若需多次执行此类查询，可给List_2建立倒排索引：将每个长字符串拆分为所有符合格式的"X & Y"子串作为键，对应值为包含该子串的字符串列表。后续查询List_1的复合串时，直接通过索引获取结果，查询速度为O(1)。

注：该方法会占用较多内存，需根据实际资源情况评估使用。

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