正则引擎与效率
28 October 2016

引擎种类及特点

  • NFA（非确定型有穷自动机）：表达式主导。移动正则表达式筛选文本。同一个字符会被检查多次，即使针对同一段子表达式。表达式的书写方式对匹配效率有很大的影响
  • DFA（确定型有穷自动机）：文本主导。移动文本筛选可能匹配的正则表达式，所扫描的字符串中的每个字符都对引擎进行了控制。并且在扫描字符时，会记录当前有效的所有匹配可能，每个字符只会被检测一次。效率更高
  • POSIX NFA:

判断是NFA: 忽略优先量词（*?,+?,??,{num,num}?）被支持 判断是DFA: 捕获型括号和回溯不被支持

编译

在正则表达式搜索之前，两种引擎都会编译表达式，得到一套内化形式，适应各自的匹配算法。NFA的编译过程通常要快一点，需要的内存也更少一点。

匹配结果

DFA返回最左边最长的匹配结果

匹配原理

优先选择最左端的匹配结果

“传动装置”会从字符串的第一个位置开始尝试正则表达式体现的所有可能情况，如果不符合再从第二个位置开始尝试匹配，直到匹配成功或者最后一个位置都不能成功

起始位置和结束位置锚点^$能够提高效率

标准的匹配量词（*,+,?,{num,num}）是匹配优先的

标准匹配量词在匹配成功之前进行尝试的次数是有上下限的，这些尝试总是希望获得最长的匹配

匹配优先的注意点：

  • 不滥用(.*)，譬如匹配双引号之间的文本，不使用/"(.*)"/,而是/"(^"*)"/
  • 善用忽略优先，譬如要匹配<a></a>之间的元素，不使用/<a>.*</a>/，而是/<a>.*?</a>/。

忽略优先量词

*?, +?, ?? , {num,num}?

占有优先量词

*+，++，?+，{num,num}+

占有优先量词与匹配优先量词很类似，只是从不交还已匹配的字符。加号在匹配之前保存了很少的状态，有利于提升性能

匹配优先和忽略优先都为全局服务

如果只有一条可能的路径，那么使用匹配优先量词或者忽略优先量词都能找到这个结果，只是他们尝试路径的次序不同，并不影响结果，只是影响效率。

多选分支

多选分支既不是匹配优先，也不是忽略优先，而是对于每一个字符按顺序尝试匹配。

用/tour|to|tourenament/匹配’tourenaments’，得到的结果是tour

合理安排多选分支的结构：

  • 针对匹配对象，将匹配成功可能性最大的子分支放在最前
  • 如果一个分支是另一个分支的子集，将父集置于最先，以免不必要的检查。如/\.\d\d|\.\d\d[1-9]/

尽可能合并多选分支，减少子分支长度。任何多选分支匹配失败都会带来回溯影响性能。

引擎的构造单元

  • 文本文字
  • 字符组、点号、unicode属性及其他
  • 捕获型括号
  • 锚点：^,$,顺序环视,逆序环视

回溯

NFA引擎的重要特性：它会依次处理各个子表达式或组成元素，遇到需要在2个可能成功的可能中进行选择的时候，它会选择其中一个，同时记住另一个，以备稍后可能的需要。需要作出选择的情况包括量词和多选结构。

回溯时使用的选择

距离当前最近存储的选项就是当本地失败强制回溯时返回的。使用的原则是LIFO（后进先出）。

量词的回溯

量词匹配优先，并不受其后元素的影响，但是回溯会受其后元素的影响

  1. ？ 保存?前的回溯

  2. * 保存*匹配的元素的每一个位置

使用技巧

表达式的复杂和精确程度根据需求调整，越复杂精确一般效率越低，需要权衡。

所以可以：

  • 采用比较模糊的匹配，然后对匹配结果进行进一步校验
  • 根据匹配对象生成表达式，如是否需要开始结束锚点

如果回溯会导致不期望，与多选机构有关的匹配结果，问题很可能在于，任何成功的匹配都不过是多选分支的排列顺序造成的偶然结果。这说明多个多选分支的内容发生了重叠。

排除子集|父集模式

匹配连续行：/[^\n\\]|\./

组合可能性

匹配IP地址：/^([01]?\d\d?|2[0-4]\d|25[0-5])\.{3,3}([01]?\d\d|2[0-4]\d|25[0-5])/。

使用锚点提高效率

匹配路径和文件名：/^(.*)/([^/])*$/, path=$1, file=$2

匹配对称的符号

正则表达式可以匹配特定深度的嵌套结构，但是无法匹配任意深度的的嵌套结构。

匹配单层对称的括号： /\[^()]*(\([^()]*\)[^()]*)*\)/

防备不期望的匹配

错误的浮点数匹配：/-?[0-9]*\.?[0-9]*/，每个部分都不是必须的，所以可以匹配任意字符。

匹配浮点数：/-?([0-9]+(\.[0-9]*)?|\.[0-9]+)/

匹配分隔符之内的文本

  1. 匹配起始分隔符
  2. 匹配正文：匹配正文的时候不要超越结束分隔符
  3. 匹配结束分隔符

匹配引文字符串，但是允许其中包含转义的引号： /*(\\.|[^"])*+"/

为了效率，将复杂表达式拆成多个简单高效的表达式

譬如匹配文本首尾字符用：/^\s+/和/\s+$/。

而不是：

  • /\s*(.*?)\s*$/
  • /^\s+|\s+$/

拆分单元,组合情况

  • 匹配html 的<和>标签：/<(?:"[^"]*+"|'[^']*+'|[^'">])*>/
  • 匹配a标签：/<a([^>]+)>(.*?)</a>/ig
  • 匹配href的值：/href\s*=\s*(?:"([^"]*)")|'([^']*)'|([^'">\S]+)/xi
  • 获取url的主机名、端口号、路径：/^http://([^/:]+)(:(\d+))?(/.*)?$/i，$1是主机名，$3如果存在是端口号，$4是路径
  • 匹配url：/^(ftp|https?)://(?:[a-z0-9](?:[-a-z0-9]*[a-z0-9])?\.)+(?:com|edu|biz|gov|in(?:t|fo)|mil|net|org|[a-z][a-z])(:\d+)?(/[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]*(?:[.!,?]+[^.!,?;"'<>()\[\]{}\s\x7F-\xFF]+)*)?$/

不依赖传动装置的驱动过程，保持数据的协调性案例

案例：需要处理一系列5位数的邮政编码，从中跳过以44开头的邮政编码

  • /(?:[^4]\d\d\d\d|\d[^4]\d\d\d)*(44\d\d\d)/。注意不能使用/(?:[^4][^4]\d\d\d)*/，他无法匹配43210这样的邮政编码
  • /(?:\d\d\d\d\d)*?(44\d\d\d)/，忽略优先量词

这并没有解决问题，因为一旦本轮匹配失败后还是会进行驱动过程和重试，这样就会从邮政编码字符串的某个位置开始。解决方法是将44\d\d\d改为匹配优先的可选项，这样就不会发生匹配失败和驱动过程的回溯了：

  • /(?:[^4]\d\d\d\d|\d[^4]\d\d\d)*(44\d\d\d)?/

效率

常见优化措施：

  • 加速某些操作：某些类型的匹配，例如\d+即为常见，引擎对此有特殊的处理方案，执行速度比通用的处理机制要快。
  • 避免冗余操作。尽量用锚点，且将锚点独立出来。譬如/^(?:abc|123)/和/^abc|^123/虽然是等效的，但是大多数正则引擎只会对第一个表达式使用开头字符/字符串识别优化。
  • 从量词中提取必须的元素，例如/xx*/比/x+/能适用的优化措施更多
  • 主导引擎的匹配，使用/th(?:is|at)/而不是/this|that/

正则表达式应用原理

image

image

编译缓存(内置)

引擎内置

通过传动装置进行优化(内置)

  • 行锚点优化
  • 开头字符/字符组/子串识别优化
  • 内嵌文字字符串检查优化
  • 长度识别优化传动

优化表达式本身

  • 文字字符串连续优化，如字符组[abc]
  • 消除无作用的括号，使用非捕获型括号(?:)，而且括号会组织某些优化措施，譬如(.*)
  • 消除不需要的字符组，如单个字符的字符组[a]
  • “过度”回溯检测，避免指数级： (.+)*会在引擎超限时停止匹配。使用占有优先量词削减状态。

先迈最好使的腿

将最容易匹配的子表达式放最前面。

例如匹配双引号字符串： /"([^"\\]|\\.)*"/比/"(\\.|[^"\\])*"/更高效，但是降低了准确性，譬如会错误匹配"You need a 2\"3\" photo."中的"You need a 2\"部分？。

将结尾部分分散到多选分支内，这样任意一个包含结尾部分的分支匹配失败来的更快。

限制匹配优先的作用范围

对于/"([^"\\]|\\.)*"/如果对更通用的[^"\\]使用占有优先量词+*作用后，能达到更高效率的效果。 /"([^"\\]+|\\.)*"/

新增的加号大大减少了多选结构回溯的次数，以及星号的迭代次数。星号量词作用于括号内的子表达式，每次迭代都需要进入后再退出括号，这都需要成本，因为引擎需要记录括号内的子表达式匹配的文本。

指数级匹配

但是+和*的排列组合对于无法匹配的元素会造成“指数级匹配”，回溯次数指数级上涨。

为了避免/"(\\.|[^\\"]+)*"/的指数级匹配，可以使用：/"[^\\"]+(\\.[^\\"]+)*"/

  1. 避免指数级匹配，消除循环常见解法：

    opening normal*(special nomal*)*closeing

    注意：

    1. special部分和normal部分匹配的开头不能重合
    2. normal部分必须匹配至少一个字符
    3. special部分是固化的

    使用“自顶向下的视角”分析这个问题： 如果我们认为[^\\"]能够处理字符串中的绝大部分字符，就知道如果匹配停止一定是遇到了闭引号或者时转义字符。

  2. 使用占有优先量词 /"(\\.|[^\\"]++)*+"/

无法匹配时的回溯效率

排除字符时确定对象，减少使用.。使用[^"]*取代.*

/"[^"]*"/在无法匹配时回溯的次数比/".*"/少很多

多选结构代价很高

尽量使用字符组而不是多选结构。

预查必须字符/子字符串优化

相比正则表达式的完整应用，在字符串中搜索某个字符是更加“轻量级”的操作。譬如检查/subject:(.*)/中的:。譬如/this|that|other/中的th。

忽略优先还是匹配优先

/^.*:/能匹配到最后的冒号,/^.*?:/能匹配到第一个冒号。

根据需求决定。如果冒号比较接近字符串开头，使用忽略优先量词，反之使用匹配优先量词。如果不知道数据规则，那使用匹配优先量词。因为引擎对匹配优先量词的优化一般比其他量词要好。

另外，排除型字符组/^[^:]*:/比/^.*?:/效率要高

使用占有优先量词

占有优先量词能极大的提高匹配速度而不改变匹配结果。使用占有优先量词能够让引擎抛弃没有意义得备用状态。但是占有优先量词要注意和排除型字符组组合使用，如果和/./使用会造成不期望的匹配。

譬如/^[^:]+:/中的冒号第一次尝试无法匹配，那么无论如何回溯都无法匹配。