面向条件标签标注的最优数据结构选型及效率优化方案问询

背景概述 #

现有应用需根据配置文件对批量Item数据做条件标签标注，当前全配置遍历校验的方式每日耗时超1小时，急需优化。此前尝试树结构方案但存在一个节点对应多个标签的问题，寻求可行的解决思路。

配置文件规则 #

• 每条记录对应一个Item类别，Label+Value组合唯一，重复组合为无效配置。
• 其余字段对应Item属性，值为null或内部校验规则，Item需通过对应规则才能匹配该类别标签。
  示例配置：

Label Value
A     1
A     2

匹配逻辑示例 #

配置：

Label Value FileName
A     1     <some_regex>
A     2

• 若Item的FileName通过正则校验，标注为A1；
• 否则标注为A2。

当前问题 #

全配置遍历校验效率极低；尝试将Item属性作为树层级、校验规则作为节点的DFS匹配方案，但无法保证末层节点唯一对应单个Label-Value组合，存在一个节点指向多个标签的问题。

核心思路 #

利用规则优先级+前缀匹配树的组合，把配置规则按属性校验的严格程度排序，构建一棵带优先级的决策树，确保每个路径最终指向唯一的Label-Value标签，同时在匹配时一旦找到符合条件的标签就终止，避免无效遍历。

数据结构设计：带优先级的决策树 #

1. 树的层级：以Item的属性（如FileName、Size等）作为树的层级节点，层级顺序对应规则的校验优先级（比如先校验FileName，再校验Size）。
2. 节点类型：
   • 中间节点：存储属性的校验规则（如正则表达式、数值范围等），每个节点下的子节点对应不同的规则分支；
   • 叶子节点：存储唯一的Label-Value组合，确保每个叶子节点仅对应一个标签。
3. 规则预处理：
   • 对所有配置规则按校验条件的数量排序：条件越多（越严格）的规则优先级越高，排在树的上层分支；
   • 无属性条件的规则（如示例中的A2）作为树的"兜底"叶子节点，放在所有分支的最后。

算法匹配步骤 #

1. 预处理配置：
   • 先去除无效的重复Label-Value组合；
   • 按规则的严格程度（条件数从多到少）排序规则；
   • 遍历排序后的规则，依次插入到决策树中：
     • 每条规则根据其携带的属性校验条件，沿树的对应层级节点向下走，不存在的节点则新建；
     • 走到路径末端时，将该规则的Label-Value作为叶子节点存入（若该路径已有叶子节点，说明规则冲突，直接抛出配置错误）。
2. Item匹配流程：
   • 从树根开始，依次按层级校验Item的对应属性；
   • 若当前属性符合某个子节点的规则，进入该子节点继续匹配；
   • 走到叶子节点时，直接返回对应的Label-Value标签，终止匹配；
   • 若当前层级没有符合的子节点，进入该层级的"默认分支"（对应属性条件为null的规则），继续向下匹配；
   • 最终走到兜底叶子节点，返回对应的标签。

额外优化点 #

• 规则缓存：提前编译正则表达式等校验规则，避免每次匹配时重复编译；
• 批量复用：对属性相同的Item，一次性完成匹配并复用结果；
• 并行处理：将Item数据分成多个批次，并行进行匹配（需注意线程安全）。

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