Labeled matches: why is this not in every regex engine?
Labeled matches: why is this not in every regex engine?
带标签的匹配：为什么不是每个正则表达式引擎都有这个功能？
This time I have an example of what I love about computer science, a little regex party trick. It comes with a bit of voodoo and abstract theory, but it has a good response to the most important question of any theory, “Why should I care?”. So the voodoo has some purpose, and many useful applications, which is way more exciting than voodoo without it. 这次我带来了一个关于计算机科学的例子，展示了我为何热爱这门学科——一个正则表达式的小技巧。它带有一点“巫术”色彩和抽象理论，但它对任何理论中最重要的问题——“我为什么要关心这个？”——给出了很好的回答。因此，这些“巫术”是有目的的，并且有许多实际应用，这比毫无用处的“巫术”要令人兴奋得多。
As the title says we will be doing some labeling, categorizing.. named entity recognition or however you wish to call it. And I’ll show you how it’s easy, and how to do it with less electricity, battery drain, heat, fan noise. In fact you get it essentially for free by computing something up front, after which it’s no more expensive than searching for a word. And I built it into resharp as well. 正如标题所言，我们将进行一些标记、分类……或者命名实体识别，随你怎么称呼它。我将向你展示它是多么简单，以及如何用更少的电力、更低的电池消耗、更少的热量和风扇噪音来实现它。事实上，通过预先计算，你可以几乎“免费”获得这个功能，之后它的开销并不比搜索一个单词更高。我也把它集成到了 resharp 中。
We can do something that looks like the following: Now let’s assign a few labels to some regex patterns and compare it to spaCy en_core_web_sm model for named entity recognition for a little (unscientific) benchmark. 我们可以做如下的事情：现在让我们为一些正则表达式模式分配几个标签，并将其与 spaCy 的 en_core_web_sm 模型进行命名实体识别的（非科学）基准测试对比。
| 1 thread | 8 threads | |
|---|---|---|
| spaCy 3.8, NER component only | 0.09 MB/s | 0.43 MB/s |
| resharp categorize_all, 10 patterns | 0.36 GB/s | 1.92 GB/s (4500x faster) |
This is an apples-to-oranges comparison, yes, but I don’t think it diminishes our whopping 1.92 gorillion bytes a second. I’d argue that the two are comparable. Why do I think these are comparable? Are we 55.1% sure this is a date? Should we consult a mixture of experts on what is and isn’t a date? Develop an AI accelerated workflow to roll a few dice? No. 这确实是“苹果与橘子”的比较，但我认为这并没有削弱我们每秒 1.92 GB 的惊人速度。我认为两者是可以比较的。为什么我认为它们可比？难道我们要以 55.1% 的把握确定这是一个日期吗？我们是否应该咨询专家混合模型来判断什么是日期什么不是？或者开发一个 AI 加速的工作流来掷骰子？不。
Last post I was talking about how regex is often used as an approximative “good enough” tool, and how its expressivity is not enough to parse HTML. This time, yyyy-MM-dd is a regular language. Meaning we can reliably, precisely, tell if something is a date or not using regex, even leap years included. So we are not approximating anything, and look how much work the neural net has to do, to replicate a fraction of our awesome, deterministic, correct 100% of the time, power. And that’s what this tool is for, when you don’t need or want to involve dice rolls. 上一篇文章中，我谈到了正则表达式通常被用作一种近似的“足够好”的工具，以及它的表达能力不足以解析 HTML。而这一次，yyyy-MM-dd 是一个正则语言。这意味着我们可以使用正则表达式可靠、精确地判断某物是否为日期，甚至包括闰年。所以我们不是在进行任何近似，看看神经网络需要做多少工作，才能复制我们那强大、确定性、100% 正确的能力的一小部分。这就是这个工具的用途——当你不需要也不想涉及“掷骰子”式的概率判断时。
The patterns
模式
Below are the patterns used for the first example: 以下是第一个示例中使用的模式：
DATE [0-9]{4}-[0-9]{2}-[0-9]{2}
MONEY \$[0-9]+(?:\.[0-9]{2})?
PERCENT [0-9]+(?:\.[0-9]+)?%
EMAIL [a-z.]+@[a-z]+\.[a-z]+
URL https?://[^ ]+
NUM [0-9]+
NAME [A-Z][a-z]+\b&~(On|In|At|To|For|Of|The|An|And|Via|Was|Is)
VERB [a-z]+ing\b
ADJ [a-z]+(?:ful|less|ous|ive)\b
ADV [a-z]+ly\bIn the NAME pattern we use & for intersection and ~ for complement, if you’re not familiar with them, read this post first, but they should be intuitive enough. Think of them as AND and NOT operators, which let us exclude “On”, “In”… from being falsely detected as names. If any of these do happen to be your name, I apologize!
在 NAME 模式中，我们使用 & 表示交集，~ 表示补集。如果你不熟悉它们，请先阅读这篇文章，但它们应该足够直观。把它们想象成 AND 和 NOT 运算符，这让我们能够排除 “On”, “In”… 等词被错误地识别为名字。如果这些词恰好是你的名字，我深表歉意！
Don’t underestimate the expressivity of regular languages
不要低估正则语言的表达能力
You can do if-then-else on regex without leaving the domain of regular languages, meaning: 你可以在不脱离正则语言范畴的情况下在正则表达式中实现 if-then-else，这意味着：
((cond & a) | (~(cond) & b))
Is still expressible in pure regex. This works however many if-then-elses you wish to chain or nest, it is a boolean algebra. The pattern becomes unreadable spaghetti, but for RE# it is nothing but a formula for how to construct a state machine. 这在纯正则表达式中仍然是可表达的。无论你想链式调用还是嵌套多少个 if-then-else，它都能工作，这就是布尔代数。模式会变得像意大利面一样难以阅读，但对于 RE# 来说，这仅仅是构建状态机的公式。
Using a bit of JavaScript string magic, we can build these from small composable pieces. 利用一点 JavaScript 字符串魔法，我们可以用小的可组合片段构建这些模式。
const ifThenElse = (cond: string, a: string, b: string) => `((${cond}&${a})|(~(${cond})&${b}))`;
// ... (code omitted for brevity)The pattern becomes an enormous monstrosity of leap years and if-then-elses, but just because the pattern is large, doesn’t mean the state machine has to be. Guess how many states this 24504 characters long pattern compiles into: It has 32 DFA states. 这个模式变成了一个由闰年和 if-then-else 组成的庞大怪物，但模式大并不意味着状态机也必须很大。猜猜这个 24504 字符长的模式会编译成多少个状态：它只有 32 个 DFA 状态。
And in the event that the DFA does start to resemble the Milky Way, remember that the size of the state graph is misleading. Like a synapse in your brain, we only make use of the connections that are actually necessary for the task at hand. I don’t even know what would happen if your whole brain fired at the same time, would you pass out or what? (UPDATE: it’s a seizure.) That’s all to say we only compile states that we visit, often a tiny fraction of what you see here. 如果 DFA 开始变得像银河系一样复杂，请记住状态图的大小是具有误导性的。就像你大脑中的突触一样，我们只利用当前任务实际需要的连接。我甚至不知道如果你的整个大脑同时放电会发生什么，你会晕倒吗？（更新：那是癫痫发作。）总之，我们只编译我们访问过的状态，这通常只是你所见的一小部分。
Which means we can get away with massive, even infinite state machines, without necessarily suffering the consequences. The state machine is just an abstraction, a caching technique. 这意味着我们可以处理庞大甚至无限的状态机，而不必承担相应的后果。状态机仅仅是一种抽象，一种缓存技术。