美文网首页正则表达式
一起学习正则表达式(七)回溯陷阱

一起学习正则表达式(七)回溯陷阱

作者: 容华谢后 | 来源:发表于2021-08-29 20:11 被阅读0次
    思维导图

    转载请注明出处:https://www.jianshu.com/p/40f8988ba339

    本文出自 容华谢后的博客

    往期回顾:

    《一起学习正则表达式(一)那些让人头晕的元字符》

    《一起学习正则表达式(二)量词与贪婪》

    《一起学习正则表达式(三)分组与引用》

    《一起学习正则表达式(四)常见的4种匹配模式》

    《一起学习正则表达式(五)断言匹配》

    《一起学习正则表达式(六)正则匹配原理》

    《一起学习正则表达式(七)回溯陷阱》

    0.写在前面

    在上一篇文章中,我们学习了正则表达式的匹配原理,在我们常用的开发语言中,大多数都是采用的传统型 NFA 引擎,也就是非确定性有穷自动机。

    NFA 引擎以正则为主导,就是拿着正则看文本,会发生回溯,文本的同一部分,有可能会被反复测试很多次,在最坏的情况下,它的执行速度可能会非常慢,那什么是最坏的情况呢,一起来看一看。

    1.回溯

    在第二篇文章量词与贪婪中,我们了解到,表示次数的量词默认是贪婪的,在贪婪模式下,会尽可能最大长度的去匹配目标文本。

    举个栗子,我们现在的需求是找到以字母 dy 结尾的单词或句子,我们可以很快的写出正则表达式:

    目标文本:Toady is such a beautify day.

    正则表达式:.+dy

    看下结果:

    贪婪匹配

    可以看到匹配了31次才找到我们想要的内容,这31次都做了哪些工作,来看下:

    贪婪匹配过程

    正则中的 .+ 在一开始就匹配到了文本的全部内容,然后拿着正则看文本,正则中还剩下 dy 没有匹配,去文本中查找,发现已经没有字符可以匹配了,于是向前回溯,吐出句号,用正则再次对比,发现还没有匹配上,于是继续向前回溯,吐出字母 a,再次对比,还没有匹配上,就这样反反复复的向前回溯,终于找到了 Toady 这个单词,匹配结束。

    这样写出的正则表达式性能肯定是有问题的,如果目标文本再长一点,再加上几个选择分支,回溯步骤直接就要上天,于是我们利用学过的知识,简单修改下:

    目标文本:Toady is such a beautify day.

    正则表达式:.+?dy

    在量词后面加上一个问号,就代表当前量词的匹配行为是非贪婪模式,非贪婪模式虽然也会发生回溯,但是不会一上来就把目标文本一口气都吃掉,从而节省了很多匹配步骤,先再看结果:

    非贪婪匹配

    可以看到只用了6次就成功的匹配到了,再看下匹配的过程:

    非贪婪匹配过程

    2.Lazada 卖家中心案例

    这是一个真实的案例,来自阿里技术微信公众号上的发文,Lazada 卖家中心店铺名检验规则比较复杂,名称中可以出现下面这些组合:

    • 英文字母大小写

    • 数字

    • 越南文

    • 一些特殊字符,如 “&”、“-”、“_” 等

    负责开发的同学随手就写出了下面的正则表达式:

    
    ^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
    
    

    看起来很长,但其实就是两个选择分支,我们来简化下:

    ^([条件分支1]|[条件分支2])+$
    

    在内部测试的时候,没有发现什么问题,然后就上线运行了,在运营的过程中,经常会遇到服务器CPU狂飙到100%的情况,于是就找啊找,终于找到竟然是这样一个正则引起的问题,一个小小的正则竟然可以让服务器直接崩溃,这是为什么呢,一起来看下:

    我们用一段文本来测试下:

    Lazada 正则校验

    示例:https://regex101.com/r/dTzUyx/1

    可以看到,一个很短的字符串,NFA 引擎竟然尝试了1万多次,由于是贪婪匹配,第一个分支可以匹配上 Talk is Cheap 这部分,接着后面的逗号匹配失败,使用第二个分支继续匹配,还是失败,此时贪婪匹配的过程就结束了。

    接着 NFA 引擎用后面的 $ 来进行匹配,但此处不是文本结尾,匹配不上,开始回溯,吐出第一个分支匹配上的最后一个字母 p,用第二个分支匹配,第二个分支匹配上了字母 p,但是还是匹配不上逗号。

    Lazada 匹配过程

    继续回溯,吐出第二个分支匹配上的字母 p,然后再继续吐出第一个分支匹配上的字母 a,再用第二个分支匹配字母 a 和 p,最后还是没有匹配上,继续吐出第二个分支匹配上的字母 p,用第一个分支再次匹配,由此进入了死亡循环,如果测试的文本增加一位,那么整体的匹配步骤就会直接翻倍。

    那么该如何解决这个问题呢,也很简单,直接使用独占模式就可以,在量词加号的后面,再加上一个 + 号,就变成了独占模式,独占模式不会发生回溯,匹配失败就直接返回失败了,不会引发性能问题:

    ^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])++$
    
    Lazada 独占模式

    还可以去掉两个分支中的重复条件 A-Za-z:

    ^([0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
    
    Lazada 去除重复条件

    这样修改之后,只用了57次就匹配完成了,所以切记,如果你写的正则表达式中有多个分支条件,里面的条件千万不要重复。

    3.避坑指南

    在见识了正则回溯的威力之后,发现如果对正则不了解,还是很容易写出存在性能问题的正则表达式的,下面我们来总结下那些我们在平时开发中容易踩到的坑:

    3.0 避免不同分支重复匹配

    在上文中,我们已经讲到了,如果正则中存在多个条件分支,其中各个分支中的条件千万不要重复。

    3.1 提前编译好正则

    编程语言中一般都自带“编译”方法,我们可以在使用正则之前提前编译好,这样就不用每次使用的时候去反复构造状态机,从而提升正则匹配的性能:

    import re
    
    # 先编译好,再使用
    reg = re.compile(r'ab?c')  
    reg.findall('abc')
    
    # 直接使用
    re.findall(r'ab?c', 'abc')
    

    3.2 提取出公共部分

    比如我们匹配 http 或 https,有的同学会写成 http|https,可以直接优化成 https?

    3.3 出现可能性大的放左边

    由于正则是从左到右匹配的,把出现概率大的放左边,域名中 .com 的使用是比 .net 多的,所以我们可以写成 .(?:com|net)\b,而不是 .(?:net|com)\b。

    3.4 只在必要时才使用子组

    有些同学为了写出来的正则表达式更加易读,会故意在表达式中加一些括号用于区分,因为正则是默认保存子组的,正则引擎必须做一些额外工作来保存匹配到的内容,这会降低正则的匹配性能,如果后续不会再用到这个子组,记得加上 ?: 不保存子组。

    3.5 警惕嵌套的子组重复

    如果一个组里面包含重复,接着这个组整体也可以重复,比如 (.) 这个正则,匹配的次数会呈指数级增长,所以尽量不要写这样的正则。

    3.6 测试性能的方法

    我们写好正则之后,可以通过 regex101.com 这个网站来测试正则的匹配次数和性能,还可以debug调试,非常方便。

    4.写在最后

    最后在总结下上面讲到的内容:

    思维导图

    到这里,正则表达式的回溯陷阱就讲完了,如果有问题可以给我留言评论,谢谢。

    正则表达式在线校验工具:https://regex101.com/

    相关文章

      网友评论

        本文标题:一起学习正则表达式(七)回溯陷阱

        本文链接:https://www.haomeiwen.com/subject/gdnlbltx.html