正则表达式是如何实现查找匹配的？
1，正则表达式的使用
2，正则表达式匹配搜索算法
3，正则表达式引擎:DFA和NFA
4，正则表达式的性能与优化
1，正则表达式的使用
正则表达式（Regular Expression 简写regex），是一种字符串匹配的模式（pattern），用来匹配搜索一段已知字符串中是否含有自己需要的子字符串，
初次接触正则表达时会觉得很深奥难写，这么多符号怎么记呢。其实当你通过几个实际例子应用之后就会觉得也没那么难。
比如：
1.给你一个字符串,把字符串里面的链接、数字、电话等显示不同的颜色；
2.给你一个包含自定义表情的文字，找出里面的表情，替换成本地的表情图片；
3.根据用户的输入内容，判断是否是微信号、手机号、邮箱、纯数字等；
而正则的应用也不仅仅局限于业务代码中的字符串匹配，编辑器的查找替换，grep查找命令，vim编辑查找等都有用到。
grep中的正则
所以，学习正则表达式并不是我们照着正则规则可以实现业务逻辑就够了，最好还要能知其所以然。
2，正则表达式匹配搜索算法
说到字符串匹配算法，常见有朴素字符串匹配算法，KMP算法，有限自动机算法（Finite Automation）等。而正则表达式用到的就是有限自动机算法。
有限状态机（finite-state machine,FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。有些地方也叫“自动机”，指的都是同一个东西。
FSM常用状态转移图来表示，下图就是一个状态转移图：
image
比如我今年18岁，我现在处于18岁的状态，如果时间过了一年，我就变成19岁的状态了，再过一年就20了。当然我20岁时时光倒流2年我又可以回到18岁的状态。
每个圈代表一个节点表示一种状态，每条有向边表示一个状态到另一个状态的转移条件。上图中状态是我的年龄，边表示时间正向或者逆向流逝。
所以通过边上条件的转移我们可以从一个状态转移到另一个状态，如果我们把要匹配的字符串的首字母和尾字母作为起始态和终止态，当从起始态可以顺利的走到终止态是不是就表示匹配成功了呢？
没错，就是这样的。
image
举个栗子：
给定正则表达式a(bb)+a，其中+表示匹配前面的子表达式一次或多次，那么该正则表达式对应的FSM状态转移图如下：
这里写图片描述
假设输入字符串是 abbbba。当机器读取字符串的第一个字母 时 a，它处于起始状态s 0。它跟随 a 箭头到达状态s1。
当机器读取字符串的其余部分时重复此过程:b,b,b,b ，最后是 a。 也就是s1->s2->s3->s2->s3->s4
所以字符串abbbba可以被这个正则所匹配。
image
该状态机结束于最后一个状态，这是一个匹配成功的状态。
若状态机结束于非匹配成功状态，那么匹配失败。如果在运行过程中，没有办法到达其他状态，那么状态机提前结束。
3，正则表达式引擎:DFA和NFA
上面例子的状态机中，任何状态每个可能的输入字符，最多只会让它转到一个新的状态，也就是说新状态是确定性的，所以上述状态机被称为：确定性有限状态自动机(Deterministic finite automaton，DFA)。
对于给定的任意一个状态和输入字符，DFA只会转移到一个确定的状态。并且DFA不允许出现没有输入字符的状态转移。
同样，如果在一个状态上输入字符可能会转移到多个不同的状态，那么这种状态机就是非确定性的，称为：非确定型有穷自动机（Non deterministic Finite Automaton，NFA）
对于任意一个状态和输入字符，NFA所能转移的状态是一个非空集合。
虽然是两种不同形态的状态机，但是DFA和NFA存在等价性，也就是说NFA和DFA是可以相互转换的。
比如上面例子的DFA，就可以转换为下面的NFA：
fig2
或
fig3
由于NFA的非确定性，在面对一个输入的时候可能有多条可选的路径，所以在一条路径走不通的情况下，需要回溯到选择点去走另外一条路径。
但DFA不同，在每个状态下，对每个输入不会存在多条路径，就不需要递归和回溯了，可以一条路走到黑。DFA的匹复杂度只有O(n)，但因为要递归和回溯NFA的匹配复杂度达到了O(n^2)。
所以将引擎中的NFA转化为DFA的场景更多。
DFA和NFA比较
但是，因为DFA支持的功能较少，所以一般的业务代码语言还是选择了NFA引擎。
4，正则表达式的性能与优化
这两种引擎有着极为不同的性能表现
image
其中一种用在许多语言的标准解释器,用的是递归回溯算法(有Perl，Ruby，python等)。另外一种用在为数不多的地方（主要是awk，grep和Thompson NFA）。
实际业务代码中的正则表达式远比上面描述的要复杂的多，因为他们还要支持各种字符集，转义序列，有限重复，部分匹配提前和断言等，比如*,+,\d,[0-9],^,$,(?=)等等。
image
既然NFA会有递归回溯，那么就会有递归回溯的性能问题，如果一个正则表达式特别模糊，那么会带来怎么样的问题呢？
曾经国外有位工程师因为写了十分模糊的正则导致cpu被打爆：
(?:(?:\"|'|\]|\}|\\|\d| (?:nan|infinity|true|false|null|undefined|symbol|math)|\|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
引起性能问题的关键部分是 .*(?:.*=.*)，这里可以先不管那个非捕获组，将性能问题的正则看做 .*.*=.* 。
.* 表示贪婪匹配任意字符任意次。这会带来极大的回溯问题。一个简单的x=x将会匹配23步才能查到。
23-steps-1
如果输入是 x=xxx，则需要 45步。这不是线性的。这是一个图表，显示了从 x=x 到 x=xxxxxxxxxxxxxxxxxxxx（= 后的 20 个 x）的匹配。在 = 之后有 20 个 x，引擎需要 555 步才能匹配！
更糟糕的是，如果缺少 x=，那么字符串只有 20 个 x，引擎将需要 4,067 步才能找到不匹配的模式。
匹配次数会随着x的数量上升而指数级的上升，十分可怕。
matching-x-x
当然，我觉得一般业务也不会写这种正则，但是写正则的时候还是要有这种性能意识，尽量的缩小范围少写模糊匹配，比如能确定是数字就不要用*匹配，越精确越好，模糊匹配、贪婪匹配、惰性匹配都会带来回溯问题。注重性能问题才能避免发生这种悲剧。
参考 ：
1:https://swtch.com/~rsc/regexp/regexp1.html
2:https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
网友评论