百万级通配符模式列表匹配无通配符查询的高效方案问询

问题背景 #

需要用无通配符的查询字符串（如abc）匹配一组通配符模式（如ab*, *ab*, *a?, ???等），存在匹配模式则返回true，否则返回false。暴力解法需遍历所有模式逐一匹配，时间复杂度为O(num_patterns * num_chars_in_pattern * num_char_in_query)，但现有输入约束严格：

• 通配符模式规模：10^6
• 模式平均长度：10^2
• 查询字符串平均长度：10^3
• 响应要求：≤100ms

核心问题：

1. 是否存在更优的数据结构解决该问题？曾考虑trie，但通配符trie的遍历存在难点（需判断消耗字符还是走*分支）。
2. 是否有现成解决方案？已排查Redis和Elasticsearch，二者仅支持通配符/正则查询普通字符串，不支持普通字符串匹配通配符模式列表。

一、更优的数据结构方案 #

1. 合并式NFA预编译 #

将所有通配符模式转换为统一的非确定有限自动机（NFA），查询时直接用字符串遍历该NFA即可。

• 实现逻辑：把每个通配符转成等价正则（*→.*，?→.），用|连接所有正则，编译为一个合并后的NFA。可通过状态合并优化减少NFA复杂度。
• 优势：查询阶段无需遍历所有模式，时间复杂度仅为O(num_chars_in_query)，对10^3长度的字符串非常高效。

2. 分类型索引过滤 #

按通配符结构对模式分类，针对性构建索引缩小候选范围：

• 前缀型（如ab*）：用前缀树（Trie）存储前缀，查询时先匹配字符串前缀筛选候选模式，再验证。
• 后缀型（如*ab）：用反转字符串的前缀树存储后缀，同理筛选。
• 子串型（如*ab*）：用倒排索引存储关键子串，查询时提取字符串所有子串，匹配对应的候选模式后验证。
• 固定长度型（如???）：按长度分组，查询时先匹配长度符合的模式再验证。
• 混合型（如a*b?）：拆分前缀、后缀等特征，先过滤候选再验证。
  该方案可将10^6级别的遍历缩小到几十/几百量级，再结合快速验证满足SLA。

3. 改进型通配符Trie #

针对通配符Trie的遍历难点，用动态规划优化：

• 将*设为特殊节点，遍历过程维护两种状态：消耗字符串字符推进Trie节点、停留在*节点跳过字符。
• 用数组记录当前字符串位置下所有可达的Trie节点，逐步推进避免重复计算，解决分支选择的难题。

二、现成解决方案 #

1. 高性能规则匹配引擎 #

• Hyperscan：Intel开源的多模式正则匹配引擎，支持将大量通配符转换的正则批量编译为高效匹配器，单次扫描输入字符串即可完成所有匹配，性能足以支撑10^6级模式和100ms响应要求。
• RE2：Google开源的正则引擎，支持多模式匹配，实现轻量易集成，性能虽略逊于Hyperscan，但完全能处理大规模模式集合。

2. 数据库方案 #

• PostgreSQL + pg_trgm：将通配符模式存入表中，利用pg_trgm扩展构建trigram索引，结合LIKE/ILIKE实现反向匹配。合理配置索引参数可支撑10^6级模式的高效查询。
• ClickHouse：支持模糊匹配优化，通过预构建索引，可高效处理大规模模式的反向匹配查询。

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