从 Regex 断言到性能优化

刚开始学习正则表达式的时候看的教学只讲解了最基础的正则表达式内容,由于那时还很少在自己写的代码中用到正则表达式所以也就仅限于浅尝辄止,没再深挖过。然而需要进行一些相对复杂的字符串格式验证(密码、邮箱格式校验之类)时,被网上现成的 regex sheet 给难住了,看了半天也没看懂里面的语法。最后一搜才知道,这里面用到了先行断言和后行断言。在进行讲解之前,笔者先向各位推荐一个 Regex 网站,这个网站是专门讲解 Regex 的,并且囊括了所有主流编程语言,尽管不同的编程语言对于 Regex 的用法基本如出一辙,还是有极少一些地方是有所不同的,这个网站对于这些地方也都做了讲解:

Rex Egg

初窥

下面是一个例子:

// 先行断言
const reg = /^.*f(?=\d+)$/;
console.log(reg.test('qfo'));  // expected output: false
console.log(reg.test('ggf5'));  // expected output: true

上面代码中的 n(?=...)m 格式即为先行断言的肯定形式,它所表达的逻辑是 紧接 n 之后有 ... 中的内容,在例子中即为查看紧接着 f 之后是否有 1 至多个的数字。后行断言的格式则是 n(?<=...)m ,即紧接着 m 之前有 ...中的内容。上面两者将 = 替换为 ! 就成了他们各自的否定形式,即分别是紧接着 n 之后和 m 之前没有 ... 中的内容。这里是 mdn 的描述。

实践

regex lookarounds 是正则表达式中一个非常好用的特性,下面是一个用它实现的密码格式校验:

const pswValidator = /^(?=\w{6,10}$)(?=.*\d)(?=.*[a-z])(?=.*[A-Z])$/;

接下来我们把其中包含的所有断言拆分开来看每一部分实现的功能:

  • (?=\w{6,10}$): 长度为 6-10,由单字字符 \w (数字、字母、下划线)组成,检查至末尾
  • (?=.*\d): 至少包含一个数字
  • (?=.*[a-z]): 至少包含一个小写字母
  • (?=.*[A-Z]): 至少包含一个大写字母

拆开来看每一部分的功能倒是很好理解,那么放到一起该怎么分析逻辑呢?接下来就是理解断言最重要的一个点:
无论其中检查的内容是什么,断言检查过后都不会移动正则表达式引擎进行下一次检查时的起始位置

With lookarounds, your feet stay planted on the string. You're just looking, not moving!

带着这样的思想再来看 pswValidator 的内容,就豁然开朗了:首先看 (?=\w{6,10}$), 它的前面就是 ^ 即字符串开头,而自己的内部又是以 $ 结尾,所以这条断言将会检查字符串是否从头到尾有 6-10 个单字字符。正如上面所说,第一个断言检查过后,正则表达式引擎仍然停留在字符串开头位置,然后进行下一步,这时发现接下来仍然是一个断言,就继续从字符串的起始位置对这条断言的内容进行检查,看看字符串中是否有数字,这条断言没有必要在末尾写 $ ,因为它所做的工作并不包括限制字符串长度,这项工作已经由第一条断言完成了,它现在的工作只是从字符串起始位置开始查找数字,如果当前位置没有就继续往下看,直到看到(注意是看,而不是找,因为表达式引擎位置不变)一个数字或看到字符串末尾为止。由此也可以总结出一条规律:即若干个连续的断言在一起,无论怎样调换彼此的顺序,都不影响最后的检查,因为它们都是从第一个断言开始处进行检查,接下来后面的两个同理。
接下来看一道小练习:

const reg = /^(?=.*[a-z])y(?=\d+)/;

const a = '1quiz';
const b = 'xyz72';
const c = 'yy121';
const d = 'y3zz';

console.log(reg.test(a));
console.log(reg.test(b));
console.log(reg.test(c));
console.log(reg.test(d));

请问上面的四次控制台输出中,有哪些会返回 false, 哪些会返回 true 呢?首先我们把正则表达式拆分成三部分:

  1. (?=.*[a-z])
  2. y
  3. (?=\d+)

然后逐个分析每一个字符串:

  • a: 正则表达式的 (?=.*[a-z]) 是紧接着 ^ 也就是字符串起始位置,那就看字符串起始位置是否有一位小写字母,然而 a 中第一位是数字,所以第一个输出是 false;
  • b: 第一个字符为字母,符合 (?=.*[a-z]) 的要求,正则表达式接下来是检验一个 y 字符,这里的判断最重要的一点就是确认 y 的校验到底是从哪里开始的。由于前面是断言,并没有移动表达式引擎的位置,所以对于 y 的匹配也要从字符串起始位置看起,发现字符串首位紧跟的是 x 字符而不是 y 字符,不符合规则,输出 false;
  • c: 字符串第一位是字母 y , 同时满足了前两部分的条件,接下来看是否满足最后一部分 (?=\d+) 的条件。(?=...) 的形式依然是先行正向断言,那就看上一位后面紧跟的是否有一至多位数字。首先要确定此时表达式引擎的位置,上一个判断是 y ,注意这不是断言,而是正则表达式中最普通也最常见的一个字符匹配,所以引擎在做完这次校验后会向后移动,也就是在这一位校验通过后,表达式引擎的位置从字符串的起始位置挪到了 y 字符的后面,字符串中一共有两个 y, 此时引擎位置到底在哪一个 y 的后面呢? 由于正则表达式的第二部分只匹配一个 y 单字字符,所以引擎的位置只移动了一位,即在第一个字符 y 的后面,正则表达式第三部分要求的是紧跟数字,而此时紧跟的是第二个字母 y,不符合规则,同样输出 false;
  • d: 第四个字符三部分均符合规则,且最后一部分是 (?=\d+) 而并非 (?=\d+$),无需在第一个 y 字符过后以连续数字结尾,所以后面的两个 z 字符符合规则,输出 true;

控制台输出:

console

深入

此时我们再看之前定义的用于密码校验的正则表达式:

const pswValidator = /^(?=\w{6,10}$)(?=.*\d)(?=.*[a-z])(?=.*[A-Z])$/;

虽然这种写法能够满足密码校验,但是在性能上却并非最优写法,在介绍更好的写法前,不妨先聊一聊正则表达式的贪婪匹配和非贪婪匹配。

匹配机制

*, +, {} 和 ? 是正则表达式语法中的量词,它们跟在指定的字符描述后面,进行数量上的匹配,每一种的数量要求在此不再赘述。假设现在有一个字符串 ab1b12b123cde, 有一个正则表达式 /^.*b123.*$/,不难看出字符串是符合该表达式的,那么具体的匹配过程是怎样的呢?字符串从头到尾整个都符合表达式的第一部分 .*, 那在执行完第一部分的匹配后,表达式引擎的位置现在在第一位后面还是在最后一位后面?答案是最后一位后面,当有多种情况满足时,量词会遵循贪婪匹配,也就是有多少符合要求的字符就匹配多少。那么问题来了,现在表达式引擎已经到了最后一位,第二部分 b123 不就没办法进行匹配了?别急,虽然贪婪匹配很贪婪,但也很好说话,当贪婪匹配之后的匹配无法找到符合规则的部分的情况下,它会把自己已经匹配好的最后一个字符还给后者,让其进行匹配,如果满足条件,就继续执行后面的匹配,在本例中第一部分把 e 还给第二部分让其进行检验,依然不符合规则, 然后再追溯到第一部分,使其把 d 也还给第二部分,以此类推,直到把最后一个 b 字符还给第二部分时,第二部分满足了条件,继续执行第三部分匹配,匹配成功,匹配结束。这种行为叫做 backtrack,也就是回溯调查,它的停止条件是直到满足了后者的匹配或是前者已经无法再给(再给一个就无法满足自身的匹配要求)。由此可以看出,贪婪匹配似乎并不是一种效率很高的匹配机制。

Greedy… but docile. ——虽然贪婪,却很温顺

直接使用这些量词时,它们的匹配机制都会遵循贪婪匹配,要改成非贪婪匹配也很简单,就是在它们之后再加一个 ? 即可,这时就会只匹配到满足条件的最少内容。还是以刚才的字符串为例,我们把正则表达式改成 /^.*?b123.*$/,这时的第一部分 .*? 会遵循非贪婪匹配规则,也就是匹配0个字符,当执行第二部分匹配时,表达式引擎还停留在字符串首位,然而此时问题又来了,表达式引擎校验到 a,发现不符合,就会把 a 匀给第一部分,然后再从 a 后面开始匹配, 第一位 b 符合条件,第二位 1 也符合条件,然而第三位 b 并不符合条件,表达式引擎就又得回到 a 后面再匀一个 b 给第一部分,然后从第一个 b 后面重新进行校验,以此类推,也就是说,非贪婪匹配同样触发了 backtrack 机制。

Contrast is beautiful

contrast(相反) 是正则表达式非常推崇的写法,它可以完美的避开 backtrack。这种写法要如何遵循呢?以之前的密码校验表达式 /^(?=\w{6,10}$)(?=.*\d)(?=.*[a-z])(?=.*[A-Z])$/ 为例,现在我们把它改成如下形式:

// previous:
const pswValidator = /^(?=\w{6,10}$)(?=.*\d)(?=.*[a-z])(?=.*[A-Z])$/;

// new:
const pswValidator = /^(?=\w{6,10}$)(?=\D*\d)(?=[^a-z]*[a-z])(?=[^A-Z]*[A-Z])$/

后面三个断言的第一部分都由匹配 .* 改成了匹配它们各自第二部分内容的相反内容。在这样的模式下,就可以保证执行到第二部分时,第一部分所检测过的内容一定是无法通过第二部分检测的,第二部分只需要顺序的检查下去就好了。这在刚才的表达式 /^.*b123.*$/ 中同样适用,现在我们依然想要匹配含有 b123 的字符串,但是又不能触发 backtrack 机制,第一部分要怎么排除 b123 才能实现 contrast 呢? 如果你的答案是 [^b123]* 那就错了,它的意思是排除 b, 1, 2, 3 这四个字符,而非排除 b123,此时我们可以用捕获括号将 b123 包起来,写成 [^(b123)]*,这实现了 contrast ,但还不够完美,因为 (x) 是捕获括号的形式,捕获括号会消耗额外的性能来帮助这个组可以在匹配到的子字符串数组中找到,如果不需再次访问被匹配的子字符串,我们可以采用非捕获括号的写法 (?:x) 在本例中的第一部分也就是 [^(?:b123)]*

完整表达式:

const reg = /[^(?:b123)]*b123.*$/;

总结

有些时候想要找到一个正则表达式的完美写法是需要一些时间的,但是只要明白正则表达式的各种机制并遵循其所推崇的写法,就一定能推理出效率最高的写法。诚然,对于现在计算机的处理速度来说,一个并不优雅的表达式和一个完美的表达式执行一次甚至连续执行成百上千次所差的时间微乎其微,但是在追求优化的大型应用场景中,花一点点额外的时间去寻求一个正则表达式的最优解一定是值得去做的事情。

参考文献

评论

暂无评论