发明正则表达式的人走了

来源：市场资讯

（来源：图灵人工智能）

您想知道的人工智能干货，第一时间送达

前两天我在写一个表单校验，顺手敲了一行 /^1\d{10}$/，校验手机号。这东西每天都在敲，手指比脑子快，根本没想过它从哪来的。

直到前几天看到一条消息，Michael Rabin 走了，94 岁。

名字有点耳熟，但一时没想起来这是谁。去搜了一下他的资料，才反应过来，原来每天敲的 \d+、每次 grep、每次填表单时那个「邮箱格式不对」的红字，背后那个东西，是他 26 岁那年和同门师弟在 IBM 打暑期工的时候一起搞出来的。

搞出来那会儿他们不是在发明工具。他们是在证一个数学定理。

故事从 1957 年说起。

那年夏天 Rabin 刚从普林斯顿博士毕业。他导师叫 Alonzo Church，图灵当年的那个导师。同门师弟叫 Dana Scott，比他小一届还在读博。IBM 那年给两个人各发了一份 summer research 的 offer，没定任务，就把他俩弄到研究院养着让他们想点理论问题。

他俩琢磨的是个挺偏的东西，叫有限自动机。这玩意 1950 年代在学术圈挺热，但离真实世界远得很。

这东西也不是凭空冒出来的。1943 年 McCulloch 和 Pitts 在一篇讲神经元的论文里搭了骨架，1951 年夏天数学家 Kleene 在 RAND 用三个算子描述了神经网络能识别的模式，就是正则表达式的原型（「regular expressions」这个词 5 年后才正式出现）。1957 年夏天 Rabin 和 Scott 接过来的，是 14 年的积累。

自动机可以理解成一台想象里的机器。它只会一个字符一个字符往前读，读一个跳一次状态。没内存没栈，一个状态跳来跳去的小破机器。

这东西有两种。一种叫 DFA，每一步下一个状态是唯一定死的。另一种叫 NFA，它可以同时处在好几个状态里，像量子的影子。按直觉 NFA 应该比 DFA 强，毕竟能同时走几条路嘛。

Rabin 和 Scott 证了一件事，NFA 和 DFA 等价。任何 NFA 能识别的字符串集合，都可以改造成一个 DFA 来识别。反过来也成立。

一个看上去更强的东西，和那个看上去更弱的一样。

这论文 1959 年发在 IBM 自己家的刊物上，叫《Finite Automata and Their Decision Problems》。学术圈的人读了觉得有意思。工业界没人搭理。

这论文后来给两个人拿了 1976 年图灵奖。

讲到这你可能觉得行吧，一个数学定理，跟咱们写代码有啥关系。

关系在 9 年之后。

1968 年 6 月，贝尔实验室一个 25 岁的小伙子叫 Ken Thompson，在 Communications of the ACM 上发了一篇论文，标题叫《Regular Expression Search Algorithm》。

Thompson 当时想干的事挺简单。他在写一个文本编辑器叫 QED，他想让用户能在文件里按「模式」搜字符串，不是精确匹配一个词，是匹配一类东西，比如所有以数字开头的行。

这需求现在每个程序员都熟。1968 年没人干过。

Thompson 翻书的时候看到了 Rabin 和 Scott 1959 年那篇论文，一拍脑袋发现这俩东西能对上。用户写的那个「模式」可以转成一个 NFA，然后用 Rabin-Scott 定理把它编译成一个 DFA，跑起来又快又准。一个纯数学证明，当场变成了一个真能用的字符串搜索引擎。

Thompson 1968 年那篇论文是今天所有正则表达式引擎的祖宗。

他先把这玩意塞进 QED，后来移植到 Unix 的 ed 编辑器，再后来切出来一个独立工具叫 grep。再后来 Perl 把正则玩成了一种次文化。再后来 Python、JavaScript、Java、Go 都内置了正则。再后来你公司表单那个「邮箱格式不正确」的红字，都是它。

一个 26 岁数学系学生在 IBM 打暑期工证的定理，9 年之后落进一个 25 岁工程师的眼里，60 多年之后落进你我每一天的键盘上。

每一代工程师都以为自己在发明新东西。其实大部分时间，咱们都在把上一代数学家证过的定理做成工具。

这还不算完。

1976 年 Rabin 在 MIT 访问，听说一个叫 Gary Miller 的年轻人搞了个快速判断大整数是不是质数的算法。Miller 那个算法有一个小毛病，它依赖一个叫广义黎曼猜想的数学假设。而黎曼猜想到今天都没人证出来。

Rabin 琢磨了一下，1980 年把 Miller 的算法改成了一个概率版本。不用黎曼猜想，牺牲一点精度（万亿分之一的出错概率），换来无条件可用。这就是 Miller-Rabin 算法。

Miller-Rabin 今天干啥用呢？

你每次打开银行 App，那个 HTTPS 小锁头，后面都有 RSA 加密在工作。RSA 的前提是你得快速生成两个大到离谱的质数。你浏览器里 openssl genrsa 命令每次跑出来的质数，都是 Miller-Rabin 一遍遍随机试出来的。全球几十亿台设备每天几万亿次加密握手，底下全是同一个人 1980 年想出来的那套办法。

这还不是他的全部。

Rabin 指纹算法，rsync 和几乎所有现代备份系统在用。Rabin 不经意传输，今天多方安全计算的数学基石。Rabin 密码系统，比 RSA 更早的一版公钥加密。

这人一辈子搞的东西，基本塞满了你每天用电脑的每一个缝隙。

但他在数学界之外不算出名。

介绍他的文章不多。讣闻那天纽约时报和主流媒体都没头版。主要是技术圈自己人在传。

这挺符合老爷子的人设的。他干的都是底下的活儿，你看不见，但你每敲一次键盘都在踩他的路。

Rabin 1931 年生在德国 Breslau，今天那地方叫波兰的 Wrocław。他爸是拉比。30 年代欧洲局势一变，全家逃到当时英国托管的巴勒斯坦。他这辈子换了三个国家、两次战争、两次流亡，最后在 2026 年 4 月 14 号走了，94 岁。

你每天写的 \d+，每次 git grep，每次访问银行网站，都是他留下的东西。

他走了，那些东西还在。