标记匹配：为什么这不在每个正则表达式引擎中？

# 标签匹配：为何未普及至所有正则引擎？ | 伊凡·埃里克·瓦拉塔鲁 来源：https://iev.ee/blog/categorize-everything-all-at-once/ 沉寂数月后，我再度归来！近期一直在休憩，想来是时候重新执笔了。 本文将展示我热爱计算机科学的一个例证——一项正则表达式的奇妙技巧。它融合了些许神秘理论与抽象思维，但对任何理论都至关重要的是回答：**"这有何意义？"**。因此这门"神秘技艺"确有其实用价值，拥有**诸多实际应用**，远比单纯炫技更令人振奋。 正如标题所示，我们将进行**标注与分类**……即命名实体识别，或任何你想用的术语。我将展示其简便性，以及如何用更少的电力、电池消耗、发热和风扇噪音实现它。事实上，通过预计算几乎可以免费获得此功能，其后开销不高于单词搜索。我已将其整合至resharp (https://github.com/ieviev/resharp) 中。 我们可以实现类似如下的效果： `在[日期]2024-01-15，[人名]爱丽丝[副词]小心地[动词]发送了[金额]$12.50至[邮箱][email protected]，附带[形容词]慷慨的[百分比]30%小费，通过[链接]https://pay.example.org/x完成[数词]3[形容词]件美妙事项的支付。` 现在，让我们为一些正则表达式模式分配标签，并与spaCy (https://github.com/explosion/spaCy) 的`en_core_web_sm`模型进行命名实体识别的小规模（非科学）基准测试。 | 线程数 | 1线程 | 8线程 | |--------|-------|-------| | spaCy 3.8，仅NER组件 | 0.09 MB/s | 0.43 MB/s | | resharpcategorize_all，10种模式 | 0.36 GB/s | **1.92 GB/s（快4500倍）** | 这确实是苹果与橘子的对比，但我认为这并未削弱我们每秒1.92太字节的惊人速度。我认为两者具有可比性。 ## 为何我认为二者具有可比性？ `组织 34.1%` `日期 55.1%` `快照 2024-01-15 已还原` 我们真的需要55.1%的把握确认这是日期吗？是否应该咨询专家混合模型来判断何为日期？开发AI加速工作流来掷几次骰子？不必如此。 在上一篇文章（https://iev.ee/blog/what-262715-regex-questions-havent-answered-pt-2/）中，我曾讨论正则表达式常被用作"大致够用"的近似工具，其表达能力不足以解析HTML。 而本次，`yyyy-MM-dd`属于**正则语言**。这意味着我们可以用正则表达式可靠、精确地判定某内容是否为日期，甚至包含闰年。 `反转操作` 我们无需近似任何东西。看看神经网络需要付出多少努力，才能复制我们这强大、确定性、百分百正确的精准能力的一小部分。 这正是本工具的用途——当你不需要或不希望引入随机因素时。 ## 正则模式 以下是第一个示例中使用的模式： - `日期` `\[0\-9\]\{4\}\-\[0\-9\]\{2\}\-\[0\-9\]\{2\}` - `金额` `\\$\[0\-9\]\+\(?:\\\.\[0\-9\]\{2\}\)?` - `百分比` `\[0\-9\]\+\(?:\\\.\[0\-9\]\+\)?%` - `邮箱` `\[a\-z\.\]\+@\[a\-z\]\+\\\.\[a\-z\]\+` - `链接` `https?://\[^ \]\+` - `数词` `\[0\-9\]\+` - `人名` `\[A\-Z\]\[a\-z\]\+\\b&~\(On\|In\|At\|To\|For\|Of\|The\|An\|And\|Via\|Was\|Is\)` - `动词` `\[a\-z\]\+ing\\b` - `形容词` `\[a\-z\]\+\(?:ful\|less\|ous\|ive\)\\b` - `副词` `\[a\-z\]\+ly\\b` 在`人名`模式中，我们使用`&`表示交集，`~`表示补集。若你不熟悉这些概念，请先阅读此文（https://iev.ee/blog/what-262715-regex-questions-havent-answered/），但它们应该足够直观。可将它们理解为"与"和"非"运算符，从而排除"On"、"In"等词被误判为名字。如果其中某个词碰巧是你的名字，我表示歉意！ ```regex [A-Z][a-z]+\b&~(On|In|At|To|For|Of|The|An|And|Via|Was|Is) ``` ## 不要低估正则语言的表达能力 我们可以在正则语言范畴内实现条件逻辑而无需离开该领域，例如： `二月？是` `日<=29` `日<=31` `(IF 二月 & THEN 日<=29) | (IF NOT ~二月 & THEN 日<=31)` 这仍可用纯正则表达式表示。无论你需要链式还是嵌套多少条件，均可通过**布尔代数**实现。 模式会变得难以阅读，但对RE#而言，它不过是构造状态机的公式。借助JavaScript字符串技巧，我们可以从可组合的小片段构建它们。 ```javascript const ifThenElse = (cond: string, a: string, b: string) => `((${cond}&${a})|(~(${cond})&${b}))`; const yyyymmdd = "[0-9]{4}-[0-9]{2}-[0-9]{2}"; const february = "[0-9]{4}-02-_*"; const upTo29 = "_*-(0[1-9]|[12][0-9])"; const upTo31 = "_*-(0[1-9]|[12][0-9]|30[01])"; const date = `${yyyymmdd}&${ifThenElse(february, upTo29, upTo31)}`; ``` 展开后成为 ```regex [0-9]{4}-[0-9]{2}-[0-9]{2}&(([0-9]{4}-02-_*&_*-(0[1-9]|[12][0-9]))|(~([0-9]{4}-02-_*)&_*-(0[1-9]|[12][0-9]|30[01]))) ``` 编译后生成如下状态机（见下文），排除了2月30日。26个DFA状态并不算多。RE#默认支持最多65536个状态。 `二月状态机` `二月匹配结果` 我们还有更多技巧确保其在更大模式下也能正常工作！让我们实现完整日历：1月至12月，2月通常28天（闰年29天），四个月30天，其余31天。 ```javascript const ifThenElse = (cond: string, a: string, b: string) => `((${cond}&${a})|(~(${cond})&${b}))`; const month = (mm: string) => `[0-9]{4}-${mm}-_*`; const yyyymmdd = "[0-9]{4}-(0[1-9]|1[0-2])-[0-9]{2}"; const upTo28 = "_*-(0[1-9]|1[0-9]|2[0-8])"; const upTo29 = "_*-(0[1-9]|[12][0-9])"; const upTo30 = "_*-(0[1-9]|[12][0-9]|30)"; const upTo31 = "_*-(0[1-9]|[12][0-9]|3[01])"; const february = month("02"); const thirtyDays = month("(04|06|09|11)"); const isLeap = (y: number) => (y % 4 === 0 && y % 100 !== 0) || y % 400 === 0; const leapYears = [...Array(10000).keys()].filter(isLeap) .map(y => String(y).padStart(4, "0")); const leapYear = `(${leapYears.join("|")})-_*`; const date = `${yyyymmdd}&${ifThenElse(february, ifThenElse(leapYear, upTo29, upTo28), ifThenElse(thirtyDays, upTo30, upTo31))}`; ``` 该模式是巨大的闰年（https://iev.ee/categorize-everything-all-at-once/date-full-union.txt）与条件逻辑的混合体，但模式庞大不代表状态机必然庞大。 猜猜这个24504字符长的模式会编译成多少个状态？ `完整日期-联合模式` 它有32个DFA状态。 `完整yyyy-MM-dd自动机，32个状态` 即使DFA开始变得像银河系般复杂，记住状态图的大小具有误导性。如同大脑突触，我们只使用实际任务所需的连接。我甚至不知道如果整个大脑同时激发会发生什么——会晕厥吗？（更新：那是癫痫发作。） 总而言之，我们只编译访问过的状态，通常只是你所见的一小部分。 `惰性编译` 这意味着我们可以构建庞大甚至无限的状态机，而不必承受相应后果。状态机只是抽象概念，一种缓存技术。 另一个细节：这个24504字符的日历模式在内部处理并重新输出后会小得多。 ```rust let node = parse_ast(&mut b, "<24504 chars>")?; let small = b.simplify(node); ``` 现在它只有599字符，并且副作用是自动发现了闰年规则。这就是完整的公历： ```regex ([0-9]{4}\-(0[1-9]|1[0-2])\-[0-9]{2}&((~([0-9]{4}\-02\-_*)&(([0-9]{4}\-(1{2}|0[469])\-_*&_*\-(0[1-9]|30|[12][0-9]))|(~([0-9]{4}\-(1{2}|0[469])\-_*)&_*\-(0[1-9]|[12][0-9]|3[01]))))|([0-9]{4}\-02\-_*&((_*\-(0[1-9]|[12][0-9])&([13579]([013-57-9](0[48]|[13579][26]|[2468][048])|[26]([13579][26]|[02468][048]))|[02468]([1-35-79](0[48]|[13579][26]|[2468][048])|[048]([13579][26]|[02468][048])))\-_*)|(_*\-(0[1-9]|1[0-9]|2[0-8])&~(([13579]([013-57-9](0[48]|[13579][26]|[2468][048])|[26]([13579][26]|[02468][048]))|[02468]([1-35-79](0[48]|[13579][26]|[2468][048])|[048]([13579][26]|[02468][048])))\-_*)))))) ``` 现在试着不用补集或交集来定义它……正是此处，若仅使用并集和连接（如常规正则引擎）会导致正则表达式大小产生双指数级膨胀（https://dl.acm.org/doi/10.1145/2071368.2071372）。 ## 关于分类 从状态机角度看，工作原理相当简单。例如考虑这两个模式的并集： - `数词` `\[0\-9\]\+` - `百分比` `\[0\-9\]\+\(?:\\\.\[0\-9\]\+\)?%` `标签` 在终结状态附加标签：状态#2=数字，状态#1=百分比。这基本上不增加状态机执行的额外成本——仅需从状态到标签的数组查询。 状态机的方式是预先支付昂贵部分，使执行极其快速。我最喜欢的是它与RE#常规工作方式几乎没有区别，我们免费获得SIMD加速、简化等所有其他特性。仿佛它天生就该如此。 代数意义上，标签是美化后的空字符串，是每个匹配成员末尾的标记——不匹配任何内容，不改变并集的性质，但进入导数后成为接受状态上的元数据。好奇的话可查看代码（https://github.com/ieviev/resharp/blob/main/resharp-algebra/src/lib.rs）。 ## 很酷，如何使用？ 它位于resharp (https://github.com/ieviev/resharp) 中，通过`regex_set`特性启用。 ```toml [dependencies] resharp = { version = "0.7.5", features = ["regex_set"] } ``` 用你的模式构建`RegexSet`（见下文）。枚举并非必需，但可能使使用更优雅。 ```rust use resharp::RegexSet; #[derive(Debug, Clone, Copy)] enum Entity { Date, Money, Num } const LEXICON: &[(Entity, &str)] = &[ (Entity::Date, r"[0-9]{4}-[0-9]{2}-[0-9]{2}"), (Entity::Money, r"\$[0-9]+(?:\.[0-9]{2})?"), (Entity::Num, r"[0-9]+"), ]; let set = RegexSet::new(LEXICON.iter().map(|(_, p)| *p))?; let text = b"On 2024-01-15 Alice sent $12.50 for 3 things"; for m in set.categorize_all(text)? { let (entity, _) = LEXICON[m.tag]; println!("{entity:?} {:?}", std::str::from_utf8(&text[m.start..m.end])?); } ``` ```text Date "2024-01-15" Money "$12.50" Num "3" ``` 为简化起见，若两个模式匹配完全相同的区间，仅报告索引较小的模式。返回多个重叠模式也并非难事，我仍在斟酌其应有行为。 同一集合上的两个更小操作（若不需要区间）： ```rust set.is_match(b"pay $5")?; // true set.matched(b"pay $5")?; // [1, 2], 所有在某处匹配的成员 ``` ## 重叠与包含 既然我提到了使用`enum`并为每次匹配返回一个标签，使用枚举要求它们互斥。这里有个小技巧可强制确保没有字符串匹配多个标签，从而可将其映射为枚举。 在我完成博士论文并梳理思路的过程中，我认为坚实的理论基础不应只是文字游戏，更重要的是由我们这些理解理论的人来解释如何在实践中应用它。这能简化许多原本难以推理的问题。能回溯到我们撰写的一篇论文，并说"看！理论在此汇聚！"这种感觉很棒。 `理论` 因此我们制作了世界上最快的正则表达式重叠检测器（特定领域工具），相关论文将在CAV 2025发表：《扩展RE#中的正则决策过程》（https://link.springer.com/chapter/10.1007/978-3-031-98682-6_7）。 这基于基础集合论。每个正则语言都是字符串的集合。若`A&B`为空，则它们没有重叠。你甚至可以检查`A ⊆ B`，即一个集合是否包含另一个。 ```rust let mut b = RegexBuilder::new(); let verb = parse_ast(&mut b, r"[a-z]+ing")?; let word = parse_ast(&mut b, r"[a-z]+")?; let both = b.mk_inter(verb, word); b.is_empty_lang(both); // Some(false)，它们有重叠 b.subsumes(word, verb); // Some(true)，每个动词都是单词 b.subsumes(verb, word); // Some(false) ``` 对正则模式运行此操作，可证明每个匹配恰好映射到一个枚举变体，或列出哪些对无法满足此条件。 --- 本文所有实验均发布于GitHub（https://github.com/ieviev/2026-09-ner）。 以上即为全部内容，感谢阅读！