专栏首页洁癖是一只狗正则表达式性能优化

正则表达式性能优化

今天说一下正则表达式,正则表达式本人也是很少研究,今天看到一些和大家一块学习

什么是正则表达式

正则表达式是计算科学的一个概念,很多语言都实现了他,正则表达式使用一些特定的元字符来检索,匹配以及替换符合规则的字符串。

构造正则表达式的元字符,有普通字符,标准字符,限定字符,定位字符组成

正则表达式是一个用正则符号写出的公式,程序对这个公式进行语法分析,建立一个语法分析树,在根据这个分析树结合正则表达式的引擎生成执行程序,用于字符匹配。而这里的正则表达式引擎就是一套核心算法,用于建立状态机.

目前实现正则表达式引擎的方式有两种,DFA自动机(确定优先状态自动机)和NFA自动机(非确定有限状态自动机)

DFA自动机的代价远大于NFA自动机,但是DFA自动机的执行效率高于NFA自动机。

假设一个字符串的长度是n,如果用DFA自动机的时间复杂度是O(N),但是如果是NFA自动机,且他的状态树是s,则他的时间复杂度是O(ns),因为他是存在大量的分值和回溯,但是NFA自动机支持更多的功能,例如捕获group ,环视,占有优先量词等高级功能,这个都是基于子表达式独立进行匹配,仅此在编程语言里,使用的正则表达式库都是基于NFA自动机。

NFA是如何进行匹配的呢?正如下面例子

text=“aabcab”
regex=“bc”
  1. 首先,读取正则表达式的第一个匹配符合目标字符串匹配,b对a,不匹配,继续换字符串的下一个字符,也就是a,不匹配,继续下一个b,匹配
  1. 同理然后拿到正则表达式的第二字符c和字符串第四个字符c比较,匹配,然后在拿下一个正则表达式的字符,发现没有了则结束。

上面是就NFA自动机的匹配过程,日常我们碰到的远比这个复杂,但是匹配的方法是一样的。

NFA自动机回溯

正则表达式在匹配的过程可能产生大量的回溯,引起CPU,从而带来系统性能开销.

text=“abbc”
regex=“ab{1,3}c”

匹配的很简单,匹配以a开头,以c结尾,其中间有1-3个b的字符串,具体过程如下

  1. 首先正则表达式第一个匹配符a和字符串第一个字符a匹配
  1. 然后取正则表达式的第二字符b和目标字符串匹配的第二字符b匹配,匹配,但是b{1,3}表示是1-3个b,NFA具有贪婪特性,所以此时不会取正则表达式的下一个字符,而是继续b{1,3}和目标字符串第三个字符b匹配,也匹配.
  1. 继续拿b{1,3}和目标字符串的第四个字符串匹配,不匹配,则此时发生了回溯,把已经读出的目标字符串的第四个字符c吐了出去,指针回到了第三个字符b的位置
  1. 发生回溯之后,在去正则表达式的下一个字符c,和目标字符串第四个字符c进行匹配,匹配,则结束

如何减少回溯

我们发现发生回溯的原因是因为贪婪模式,这和正则表达式匹配模式息息相关,下面我们介绍一下几种模式

贪婪模式

顾名思义,就是在数量匹配中,如果使用+,?*,{min,max}等量词,正则表达式会匹配可能多的内容,如下

text=“abbc”
regex=“ab{1,3}c”

就是在贪婪模式下,NFA自动机读取大量的匹配范围,即匹配三个b字符,匹配发生一次失败,就引起了一次回溯,如果匹配abbbc,就会成功,

text=“abbbc”
regex=“ab{1,3}c”

懒惰模式

在该模式下,正则表达式尽可能少的重复匹配字符,如果匹配成功,就会继续匹配剩余的字符串,例如,上面例子的字符后面加一个?,就可以开启懒惰模式

text=“abc”
regex=“ab{1,3}?c”

匹配的结果是abc,在NFA自动机首先选择最小范围匹配,匹配一个b字符,因此就避免了回溯。

但是懒惰模式是无法完全避免回溯的,可以看看下面例子

text=“abbc”
regex=“ab{1,3}?c”
  1. 首先读取正则表达式第一个字符a和目标字符串a匹配,匹配,然后使用正则表达式第二字符b{1,3}?和目标字符串b进行比较,匹配
  1. 然后取到正则表达式的第三个字符c和目标字符串第三个字符b进行比较,不匹配
  1. 这个时候会发生一次回溯,但是和贪婪模式正好相反,回溯的是正则表达式第二个字符b{1,3}?和目标字符串第三个字符b比较,匹配,则在匹配正则表达式的下一个c和目标字符串的第三个字符c比较,匹配

独占模式

独占模式和贪婪模式一样最大限度的匹配更多内容,不同的是,在独占模式下,匹配失败就会结束匹配,不会发生回溯问题,如上面的例子,字符串添加一个+,就可以开启独占模式

text=“abbc”
regex=“ab{1,3}+bc”

结果是不匹配,结束匹配,不会发生回溯问题

我们再看看下面例子

text=“abbc”
regex=“ab{1,3}+c”

匹配成功,这个是因为与贪婪模式一样,独占模式一样会最大限度的匹配更多内容,即匹配完b之后,再去匹配c,则匹配成功。仔细品回溯的概念.

正则表达式的优化

  1. 少用贪婪模式,多用独占模式 贪婪模式会一起回溯问题,我们可以使用独占模式来避免回溯
  2. 减少分支选择 分支类型(X|Y|Z)的正则表达式会降低性能,我们在开发的时候尽量减少是使用,如果一定使用按照下面规则
    1. 考虑顺序,将比较常用的选择放到前面,使他们可以较快的被匹配
    2. 尝试提取公用模式,例如将(abcd|abef)改成ab(cd|ef),后者匹配速度较快,因为NFA自动机会尝试匹配ab,如果没有找到,就不会再尝试任何选项。
  3. 减少捕获嵌套 此时我们要了解什么是捕获组和非捕获组 捕获组是指正则表达式中,子表达式匹配的内容保存在以数字编码或显示命名的数组中,方便后面引用,一般一个()就是一个捕获组,捕获组可以进行嵌套。

非捕获组则是指,参与匹配却不进行分组编码的捕获组,其表达式一般由(?:exp)组成

在正则表达式中,每个捕获组都有一个编码,编号0代表整个匹配到的内容,我们可以看下面例子

public static void main( String[] args )
{
  String text = "<input high=\"20\" weight=\"70\">test</input>";
  String reg="(<input.*?>)(.*?)(</input>)";
  Pattern p = Pattern.compile(reg);
  Matcher m = p.matcher(text);
while(m.find()) {
    System.out.println(m.group(0));//整个匹配到的内容
    System.out.println(m.group(1));//(<input.*?>)
    System.out.println(m.group(2));//(.*?)
    System.out.println(m.group(3));//(</input>)
  }
}

运行结果

<input high=\"20\" weight=\"70\">test</input>
<input high=\"20\" weight=\"70\">
test
</input>

如果你并不需要获取某一分组的文本,那么就使用非捕获分组,例如,使用(?:exp)代替X

public static void main( String[] args )
{
  String text = "<input high=\"20\" weight=\"70\">test</input>";
  String reg="(?:<input.*?>)(.*?)(?:</input>)";
  Pattern p = Pattern.compile(reg);
  Matcher m = p.matcher(text);
while(m.find()) {
    System.out.println(m.group(0));//整个匹配到的内容
    System.out.println(m.group(1));//(.*?)
  }
}

结果

<input high=\"20\" weight=\"70\">test</input>
test

本文分享自微信公众号 - 洁癖是一只狗(rookie-dog),作者:洁癖汪

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 高可用篇之Keepalived (HAProxy+keepalived 搭建高可用负载均衡集群)

    Keepalived是Linux下一个轻量级别的高可用解决方案。健康检查和失败切换是keepalived的两大核心功能。所谓的健康检查,就是采用tcp三次握手,...

    小土豆Yuki
  • FastDFS轻量级分布式存储文件系统

    FastDFS系统分为三个角色,跟踪服务器(tracker server),存储服务器(storage server),客户端(client).

    小土豆Yuki
  • HAProxy负载均衡器用法详解

    上一篇我们介绍了四层的负载均衡器LVS, 这次我们我们介绍另外一种负载均衡器HAProxy。

    小土豆Yuki
  • 正则表达式-入门

    前言:今天先分享正则表达式的基础元字符,后续会分享正则表达式的子表达式,回溯引用,前后查找,嵌入条件,,全部分享完成之后,会尝试着去分享一些例子与拆分介...

    杨小杰
  • 玩转 JavaScript 正则表达式

    正则表达式也能帮助我们方便的进行Find&Replace;的工作,由于正则表达式的流派很多,而作者比较熟悉JS,这篇文章主要是描述JavaScript中的正则表...

    腾讯IVWEB团队
  • 玩转JavaScript正则表达式

    Why Regular Expression 我们先来看看,我们干哈要学正则表达式这玩意儿: 复杂的字符串搜寻、替换工作,无法用简单的方式(类似借助标准库函数)...

    IMWeb前端团队
  • 玩转JavaScript正则表达式

    在我们常用的开发工具中,如Fiddler Willow、WebStorm、Vim,正则表达式也能帮助我们方便的进行Find&Replace的工作。由于正则表达式...

    IMWeb前端团队
  • JavaScript(RegExp正则匹配)

    正则表达式是一个描述字符模式的对象。JavaScript的RegExp对象和String对象定义了使用正则表达式来执行强大的模式匹配和文本检索与替换函数的方法。

    aehyok
  • 10个正则表达式技巧

    =零或更多 =还有一个?= 0或1 {3} =正好3倍{2,4} =两倍,三倍或四倍{2,} =两倍或更多倍

    前端开发博客
  • 一个正则表达式测试(只可输入中文、字母和数字)

      在项目中碰到了正则表达式的运用,正则还是非常强大的,不管什么编程语言,基本上都可以用到。之前在用java时特别是对用户名或密码使用正则非常爽,写脚本上用正则...

    猿人谷

扫码关注云+社区

领取腾讯云代金券