如何用Python在含正则键的大型字典中快速查找最优匹配项

核心问题分析 #

原有实现时间复杂度为O(N*M)（N为单词数量，M为正则规则数量），且每次匹配都隐式编译正则，双重开销导致速度极慢。同时遍历所有规则后才能确定最长匹配，存在大量无效计算。

优化方案 #

方案1：预编译正则+长度倒序优先匹配（改动最小，收益最高） #

预处理阶段仅执行一次，完成正则预编译和排序，匹配时找到第一个命中的规则即可停止遍历，直接得到最长最优匹配。
预处理代码：

import re

# 仅需执行1次的预处理逻辑
sorted_rules = sorted(
    [(re.compile(reg_str), value, len(reg_str)) for reg_str, value in dictionary.items()],
    key=lambda x: -x[2]  # 按正则字符串长度倒序排列，长规则优先匹配
)

匹配逻辑代码：

matched_results = []
for word in textTokens:
    for pattern, val, _ in sorted_rules:
        # 需完全匹配单词用fullmatch，仅需前缀匹配用match即可
        if pattern.fullmatch(word):
            matched_results.append((word, val))
            break  # 已找到最长匹配，直接跳出循环无需遍历剩余规则

注：该方案可将平均匹配次数降低一个数量级，加上正则预编译的开销节省，整体速度可提升50~100倍。

方案2：同长度正则合并匹配（适用于正则数量过万的场景） #

将相同长度的正则合并为一个组合正则，一次匹配即可完成同长度所有规则的校验，进一步减少循环次数。
预处理代码：

from collections import defaultdict

reg_groups = defaultdict(list)
for reg_str, val in dictionary.items():
    reg_groups[len(reg_str)].append((reg_str, val))

# 按长度倒序排列规则组，同组内正则合并
sorted_group_rules = []
for length in sorted(reg_groups.keys(), reverse=True):
    reg_list = reg_groups[length]
    combined_reg = "|".join(f"({reg})" for reg, val in reg_list)
    sorted_group_rules.append(
        (re.compile(combined_reg), [val for reg, val in reg_list])
    )

匹配逻辑代码：

matched_results = []
for word in textTokens:
    for pattern, val_list in sorted_group_rules:
        match_res = pattern.fullmatch(word)
        if match_res:
            # 定位命中的子正则，取对应数值
            hit_idx = next(i for i, group in enumerate(match_res.groups()) if group is not None)
            matched_results.append((word, val_list[hit_idx]))
            break

方案3：增加匹配缓存（适用于语料重复率较高的场景） #

对已经匹配过的单词结果做缓存，重复出现的单词无需再次执行正则匹配：

match_cache = {}
matched_results = []
for word in textTokens:
    if word in match_cache:
        matched_results.append((word, match_cache[word]))
        continue
    # 复用上述任意一种匹配逻辑
    for pattern, val, _ in sorted_rules:
        if pattern.fullmatch(word):
            match_cache[word] = val
            matched_results.append((word, val))
            break

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