如何实现词库与多正则表达式的最快匹配优化？

需求背景 #

需要将大型词库中的每个单词与所有小写字母有序双组合（如ab、ba等）对应的正则表达式.*{let1}.*{let2}.*进行匹配，最终建立双组合到对应匹配单词的映射。

现有实现及性能 #

首次尝试（低效） #

%%time
mapping = {f'{k1}{k2}':[] for k1 in string.ascii_lowercase for k2 in string.ascii_lowercase}

for word in word_list[:1000]:
    for let1,let2 in mapping:
        if re.search(rf'.*{let1}.*{let2}.*', word):
            mapping[let1+let2].append(word)

耗时：Wall time: 22.2 s

优化后实现 #

%%time
mapping = {f'{k1}{k2}':
                [word for word in word_list[:1000] if re.search(rf'.*{k1}.*{k2}.*', word)] 
          for k1,k2 in itertools.product(string.ascii_lowercase, string.ascii_lowercase)}

耗时：Wall time: 608 ms

进一步优化方案 #

方案1：预编译正则表达式 #

原优化版每次生成正则时都会隐式编译，预编译所有正则可避免重复编译的开销，进一步提速：

import string
import itertools
import re
from nltk.corpus import words
import time

word_list = words.words()[:1000]

# 预编译所有双字母组合对应的正则
regex_cache = {}
for k1, k2 in itertools.product(string.ascii_lowercase, string.ascii_lowercase):
    regex_cache[f"{k1}{k2}"] = re.compile(rf'.*{k1}.*{k2}.*')

# 构建映射
start = time.time()
mapping = {
    key: [word for word in word_list if regex_cache[key].search(word.lower())]
    for key in regex_cache
}
end = time.time()

print(f"耗时: {end - start:.3f} s")

优化点：提前编译所有正则，避免循环中重复编译；统一转小写处理，确保大小写不影响匹配结果。

方案2：抛弃正则，用字符位置判断（最优） #

正则匹配本身有一定开销，我们可以直接通过分析单词中字符的出现顺序来替代正则逻辑，完全规避正则开销：

import string
import itertools
from nltk.corpus import words
import time

word_list = words.words()[:1000]

# 初始化映射字典
mapping = {f"{k1}{k2}": [] for k1, k2 in itertools.product(string.ascii_lowercase, string.ascii_lowercase)}

start = time.time()

for word in word_list:
    word_lower = word.lower()
    # 记录单词中每个字符的位置（仅保留小写字母）
    char_pos = [(char, idx) for idx, char in enumerate(word_lower) if char in string.ascii_lowercase]
    # 生成所有符合let1在let2之前的有序对
    for i in range(len(char_pos)):
        let1, pos1 = char_pos[i]
        for j in range(i, len(char_pos)):
            let2, pos2 = char_pos[j]
            key = f"{let1}{let2}"
            mapping[key].append(word)

# 对每个列表去重（避免单词因重复字母被多次添加）
for key in mapping:
    mapping[key] = list(set(mapping[key]))

end = time.time()
print(f"耗时: {end - start:.3f} s")

优化点：

• 完全脱离正则，用纯字符串遍历和位置判断实现匹配逻辑，速度远超正则方案
• 仅处理单词中的有效小写字母，减少无效计算
• 最后对列表去重，保证每个单词在对应键下只出现一次

方案3：批量处理与向量化（针对超大规模词库） #

如果词库规模极大（百万级以上），可以结合pandas进行向量化处理，利用底层优化进一步提升效率：

import string
import itertools
import pandas as pd
from nltk.corpus import words

word_list = words.words()[:1000]
df = pd.DataFrame({"word": word_list})
df["word_lower"] = df["word"].str.lower()

mapping = {}
for k1, k2 in itertools.product(string.ascii_lowercase, string.ascii_lowercase):
    # 用pandas的str.contains实现批量匹配
    mask = df["word_lower"].str.contains(rf'.*{k1}.*{k2}.*')
    mapping[f"{k1}{k2}"] = df.loc[mask, "word"].tolist()

优化点：利用pandas的向量化字符串操作，底层基于C实现，批量处理效率更高。

复现代码 #

import nltk
nltk.download('words')
from nltk.corpus import words
word_list = words.words()

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