如何高效在多字符串系列中匹配输入值？寻求优化方案

问题背景 #

我有以下几组字符串系列：

serie_1 = ['ABC1', 'ABC2', 'AFG9']
serie_2 = ['CX1', 'CX9', 'CXL']
serie_3 = ['HOM1', 'HOM65']

需要根据输入字符串判断其所属系列并输出对应名称，例如：

• 输入HOM112343 → 输出Alpha serie（注：根据原代码逻辑此处应为Home Design，推测为示例笔误）
• 输入HOM65XL → 输出Home Design

当前实现是逐个系列遍历检查子串，但随着系列数量（serie_4、serie_5…）和关键词规模扩大，效率逐渐降低，需要更高效的匹配方案。

原实现代码：

if any(ser in INPUT.upper() for ser in serie_1):
    return "Alpha serie"
if any(ser in INPUT.upper() for ser in serie_2):
    return "Casio Extreme"
if any(ser in INPUT.upper() for ser in serie_3):
    return "Home Design"

高效解决方案 #

1. 预编译正则表达式组 #

利用正则引擎的优化逻辑，将每个系列的关键词合并为预编译的正则模式，避免逐个循环检查，匹配效率更高。

import re

# 统一管理系列与关键词的映射
series_mapping = {
    "Alpha serie": ["ABC1", "ABC2", "AFG9"],
    "Casio Extreme": ["CX1", "CX9", "CXL"],
    "Home Design": ["HOM1", "HOM65"]
}

# 预编译正则：转义关键词避免特殊字符干扰，忽略大小写
compiled_patterns = {
    name: re.compile(
        "|".join(re.escape(kw) for kw in keywords),
        flags=re.IGNORECASE
    )
    for name, keywords in series_mapping.items()
}

def get_series_name(input_str):
    for series_name, pattern in compiled_patterns.items():
        if pattern.search(input_str):
            return series_name
    # 无匹配时返回默认值
    return "Unknown Series"

2. 前缀树（Trie）实现最长匹配 #

如果需要优先匹配最长的关键词（例如同时存在HOM和HOM65时，优先匹配后者），前缀树是最优选择，时间复杂度为O(n)（n为输入字符串长度），适合大规模关键词场景。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.series_name = None

def build_trie(series_mapping):
    root = TrieNode()
    for name, keywords in series_mapping.items():
        for kw in keywords:
            current_node = root
            # 统一转为大写，避免大小写问题
            for char in kw.upper():
                if char not in current_node.children:
                    current_node.children[char] = TrieNode()
                current_node = current_node.children[char]
            # 标记当前关键词对应的系列
            current_node.series_name = name
    return root

def get_longest_match(input_str, trie_root):
    input_upper = input_str.upper()
    matched_name = None
    current_node = trie_root
    
    for char in input_upper:
        if char not in current_node.children:
            break
        current_node = current_node.children[char]
        # 更新匹配到的最长关键词对应的系列
        if current_node.series_name:
            matched_name = current_node.series_name
    return matched_name

# 构建前缀树
series_mapping = {
    "Alpha serie": ["ABC1", "ABC2", "AFG9"],
    "Casio Extreme": ["CX1", "CX9", "CXL"],
    "Home Design": ["HOM1", "HOM65"]
}
trie_root = build_trie(series_mapping)

# 使用示例
print(get_longest_match("HOM65XL", trie_root))  # 输出：Home Design
print(get_longest_match("ABC2XYZ", trie_root))   # 输出：Alpha serie

3. 滑动窗口+哈希集合（固定长度关键词场景） #

如果所有关键词长度固定，可通过滑动窗口生成输入字符串的子串，再用哈希集合快速查询，适合关键词长度统一的场景。

# 构建关键词到系列的映射
series_mapping = {
    "Alpha serie": ["ABC1", "ABC2", "AFG9"],
    "Casio Extreme": ["CX1", "CX9", "CXL"],
    "Home Design": ["HOM1", "HOM65"]
}

kw_to_series = {}
for name, keywords in series_mapping.items():
    for kw in keywords:
        kw_to_series[kw.upper()] = name

# 收集所有关键词的长度
keyword_lengths = {len(kw) for kw in kw_to_series.keys()}

def get_series_name(input_str):
    input_upper = input_str.upper()
    input_len = len(input_upper)
    
    for length in keyword_lengths:
        if input_len < length:
            continue
        # 滑动窗口遍历所有可能的子串
        for i in range(input_len - length + 1):
            substr = input_upper[i:i+length]
            if substr in kw_to_series:
                return kw_to_series[substr]
    return "Unknown Series"

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