正则表达式的实现和效率

正则表达式的实现引擎(NFA/DFA)

NFA 是不确定的有限自动机,也就是说在状态的迁移过程中,下一个状态可能有好几种可能,而对于 DFA 确定有限自动机而言,下一个状态只有一种可能。

想起大学时上的一门课,“可计算性理论”,用自动机来证明程序是可以写出来的,我大学有两门典型天书课,这个是一,另一个是 “相对论和量子力学”。

简单来讲,NFA 对应的是正则表达式主导的匹配,而 DFA 对应的是文本主导的匹配。

比如说对于这样的文本和正则表达式,

text = ‘after tonight’

regex = ‘to(nite|nighta|night)’

在 NFA 匹配时候,是根据正则表达式来匹配文本的,从 t 开始匹配 a,失败,继续,直到文本里面的第一个 t,接着比较 o 和 e,失败,正则回退到 t,继续,直到文本里面的第二个 t,然后 o 和 文本里面的 o 也匹配,继续,正则表达式后面有三个可选条件,依次匹配,第一个失败,接着二,三,直到匹配,可以看到回朔发生了两次。

而在 DFA 匹配时候,采用的是用文本来匹配正则表达式的方式,从 a 开始匹配 t,直到第一个 t 跟正则的 t 匹配,但 e 跟 o 匹配失败,回朔,继续,直到文本里面的第二个 t 匹配正则的 t,接着 o o 匹配,n 的时候发现正则里面有三个可选匹配,开始并行匹配,直到文本中的 g 使得第一个可选条件不匹配,继续,直到最后匹配。

可以看到,DFA 匹配过程中文本中的字符每一个只比较了一次,没有回朔的操作,应该是快于 NFA 的,另外,不管正则表达式怎么写,对于 DFA 而言,文本的匹配过程是一致的,都是对文本的字符依次从左到右进行匹配,所以,DFA 在匹配过程中是跟正则表达式无关的,而 NFA 对于不同但效果相同的正则表达式,匹配过程是完全不同的,比如,

to(ni(ght|te)|knight) vs. tonite|toknight|tonight

也正因为 DFA 跟正则表达式无关,也就意味着通过变更正则表达式来提升效率是不可能的,因为不管神马正则表达式,其匹配的过程是一致的。

为什么不用 DFA?

那为什么 DFA 这么快,而大多数工具都采用的是 NFA 的呢,比如 Emacs, vi, grep, awk, sed, python 等。

因为 DFA 不支持很多正则表达式的 feature, 例如,

Group capturing

regex = ‘ab(.+)fg abcdefg’

这个正则表达式里面的 () 代表的是 group,匹配完之后,可以用 \1 来表示该 group 匹配的内容,在这个例子里面,就是 cde,capturing 是在字符串替换等应用中很常用的功能。

Lookaround

text = ‘JeffreyJeff’

regex = ‘(?=Jeffrey)Jeff JeffreyJeff’

我想匹配文本里面的 Jeffrey 里面的 Jeff, 但不想匹配最后的那个 Jeff, 这个时候,就可以采用 Lookaround 功能,?= 代表的是向后查看,也就是说在匹配到第一个 J 时,先向后看有没有 Jeffrey, 有的话,才开始匹配,没有的话,就跳过。在这个例子里面,第一个 Jeff 完成了匹配,到第二个 Jeff 的时候,因为后面没有 Jeffrey,所以直接跳过,不进行匹配。

Non-greey quantifiers

*, +, {m, n} 等元字符 (metacharacter) 都是贪心版的,比如,

text = ‘<html> <title> Test </title></html>’

如果采用 <.*> 来匹配,因为 * 是贪心的,所以这个正则表达式是匹配了整个文本 <htm...html>,如果采用 *? 这个非贪心元字符,则匹配的是 <html>

另外还有一些 feature 比如 atomic capturing 等也不支持,在这里就不赘述了。

DFA 之所以可以并行的进行多种可能的匹配,那是因为在匹配前的编译阶段做了工作,它对正则表达式进行了分析,生成了一些 map 关系,在并行匹配过程中才能知道下一个匹配字符是哪个,而这个操作是有 time 和 memory 的消耗的,所以编译阶段,NFA 的效率是高于 DFA 的。

匹配规则

The match that begins earliest wins

text = ’indicates your cat is’

regex = ‘cat’

上面正则表达式匹配的是 indicates 里面的 cat,因为出现的最早。

The standard quantifiers are greey

text = ‘Copyright 2003′

regex = .+([0-9]+)

上面正则表达式的 () 里面匹配的是什么?

是 2003 吗?

不是的,因为 + 是贪心的,所有直接匹配到文本最后,然后发现匹配失败,于是回朔到 3,发现满足 [0-9]+,于是匹配结束,group 匹配的只有 3。

效率

因为 DFA 在匹配过程中是跟正则表达式无关的,所以接下来效率提升方面的讨论只针对 NFA。

我们如何知道一个正则表达式效率低?

匹配失败发生回朔的次数是一个指标,我的 keynote 里面有几个例子来展示对正则表达式进行很简单的改动,就可以大幅减少回朔的次数。

而为什么会发生回朔呢?

因为基本的元字符是贪婪的 (*, +),因为有选择性的匹配 (|), 于是在匹配过程中每一次这样的选择,都会记录一个回朔点,在匹配失败时,就会回朔到之前一个回朔点,继续匹配,也就是类似于栈的机制,后进先出。

一些提升效率的技巧

对于大部分人来讲,使用正则表达式是想让自己的一些手工劳动变得简单自动高效,所以这里提到的都是类似于 common sense 之类简单的技巧,而如果真的效率很重要,那可能还需要更深入更复杂的方式,在这里就不讨论了。

Alternation is expensive

u|v|w|x|y|z vs. [uvwxyz]

前者每一次匹配失败都要进行回朔,后者一次匹配所有的,如果失败,只发生一次匹配,也就是说,使用前者在全部匹配失败时的回朔次数是后者的六倍。虽然两个方式效果是一样的,能用后者尽量用后者。

Start or end of string/line anchor

如果可以确认行首或者行尾的特征时,尽量使用 ^ $ 元字符,尤其是后面使用 .* 等贪心元字符时。

^T.*

对于这个正则表达式,如果没有 ^,那么匹配过程中会对一行中每一个字符进行匹配,看其是否是 T,如果这一行有两万个字符,就回朔两万次,而使用了 ^ 之后,只进行一次匹配。

Use non-capturing parentheses (?:)

text = ‘abcdefgh’

regex = ‘ab(.+)e(.+)h

上述正则表达式的两个 () 分别匹配的是 cd 和 fg,但是在很多情况下,使用 () 只是用来组合元字符,对于其匹配的内容不在乎,那么采用 ab(?:.+)e(?:.+)h,告诉匹配引擎,不需要匹配组,这样可以提升回朔的效率。因为组的匹配会对回朔的效率产生负面影响。

Expose

th(?:is|at) vs. (?:this|that)

显而易见,前者的效率是高于后者的,就跟写程序一样,重复功能可以提出来当作一个函数,在这里,可选择匹配里面重复的内容可以提取到 | 外面,从而减少回朔的次数。

Most likely alternation first

假设我想匹配包含 com net org edu biz 等 url 的后缀,于是我从网上找到所有的可能后缀,然后按字母排序,写出正则表达式如下:

(?:aero|biz|com|...)

但是每一个后缀的域名数量是不一样的,比如 .net .org 的域名很多,但在上面正则表达式的匹配中,因为其很靠后,所以需要匹配失败很多次才能到 .net .org 的匹配,于是按照域名的可能数量来排序

(?:com|edu|org|net|...)

回朔的次数便大大减少了。

Example

假设我需要匹配有效的 IP 地址,例如 10.10.10.10

这样写

[0-9]*\.[0-9]*\.[0-9]*\.[0-9]*

匹配成功,但发现这样的文本 ‘then ...’ 也可以成功。

好,. 前后应该至少有一位数字,并且一行只能有一个 IP 地址,不能出现其他字符,于是改成这样,

^[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+$

OK, 这次 ‘then ...’ 匹配失败了,可是 1234.5678.9101112.131415 匹配成功了,对了,必须至多三位数字的,继续改,

^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$

表的是所有数字,跟 [0-9] 意义一样,成功。可是 900.1.1.1 是个无效 IP 地址,但还是可以匹配的,那我们必须限定数字的取值,有效 IP 地址的每一部分只能是 0-255 的数字,于是我绞尽脑汁,费尽心力折腾出这样一个正则表达式,

^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$

这下圆满了。从后到前看,25[0-5] 代表数字如果开头是 25,那么只能是 250-255;2[0-4]代表如果数字大于 200,那么只能是介于 200 到 249 之间;[01]? 代表所有小于 200 大于 0 的数字。

可是可是,0.0.0.0 也是匹配的,但它是无效 IP 地址。

肿么办?

天无绝人之路,我们还有 Lookaround,

^(?!0+\.0+\.0+\.0+$)([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$

(?!0+.0+.0+.0+$) 表示在匹配过程中先往后面看,如果是 0.0.0.0 0.00.0.00 这类 IP 地址,那么直接跳过,不进行后面的一串匹配,也就意味着可以通过 lookaround 功能来剔除匹配中的一些无效匹配。

我们可以说不

为了简单的 IP 地址匹配,我们造出了这么长一个正则表达式,有必要吗?

做任何事情都有一个投入产出比,使用正则表达式,我们是想提高工作效率,减少手工重复劳动,而不是尽量全部使用正则表达式来展示其魔力。

比如对于上面 IP 地址匹配,到这一步 ^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$ 是不是就已经够了?

已经限制了 IP 地址的每一部分最多三位数,如果我们在用 Python RE 做这个匹配,那么将每一部分以 group () 的形式返回, 然后在 Python 中比较是不是处于 0-255 之间,是不是来得更快,因为数字比较,任何编程语言都是强项,但正则表达式不是。

Keynote

-- 记得是四月份的时候在北京 QCon 上看到 Twitter 的 Evan Weaver 在用这个工具,这次试用了一下,是个靠谱的工具 XD

-- Mastering Regular Expression 是本好书,推荐。