>>分享Java编程技术,对《Java面向对象编程》等书籍提供技术支持 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 21992 个阅读者 刷新本主题
 * 贴子主题:  正则表达式性能调优 回复文章 点赞(0)  收藏  
作者:flybird    发表时间:2020-01-27 21:19:54     消息  查看  搜索  好友  邮件  复制  引用

  
这篇文章主要是分享最近在开发中正则的学习心得体会。我们开发,一开始是采用python的正则库,后来为了适应Spring Cloud兼容Java所以正则也相应的修改成为了Java版本,经过测试,Java在匹配速度上相对慢了好多,平台一天需要处理一亿多条日志,但按照当时的处理速度,每天差不多就只能处理了2千多万条,这样的速度,实在扎心,提单申请扩容,那边的负责人说资源不足,好咯,将Java所使用的正则库替换成C++,C++够快了吧,不过,这个库是通过牺牲功能换取性能来实现的。

     点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小

正则表达式的原理

理论模型是

有穷自动机

,具体的实现为

正则引擎(Regex Engine)

分两类

确定型有穷自动机(Definite Finite Automata,DFA,其状态都是确定)



非确定型有穷自动机(Non-definite Finite Automate,NFA,其状态在某个时刻是不确定的)

。DFA和NFA是可以证明存在等价关系,不过这是两种不同的自动机。在这里,我才不会深入讨论它们的原理。简单地说,DFA 的时间复杂度是线性的。它更稳定,但功能有限。NFA 的时间复杂度相对不稳定。 根据正则表达式的不同,时间有时长,有时短。NFA 的优点是它的功能更强大,所以被 Java、.NET、Perl、Python、Ruby 和 PHP 用来处理正则表达式。 NFA 是怎样进行匹配的呢?我用下面的字符串和表达式作为例子。
  text="A lovely cat."
regex="cat"
NFA 匹配是基于正则表达式的。也就是说,NFA 将依次读取正则表达式的匹配符,并将其与目标字符串进行匹配。如果匹配成功,它将转到正则表达式的下一个匹配符。否则,它将继续与目标字符串的下一个字符进行比较。 让我们一步一步地来看一下上面的例子。
  • 首先,提取正则表达式的第一个匹配符:c。然后,将它与字符串的第一个字符 A 进行比较。不匹配,所以转到下一个。第二个字符是 l,也不匹配。继续转到下一个,也就是 o。匹配失败。于是,继续读取text的字符直到c,匹配成功猴,读取正则表达式的第二个字符: a。
  • 正则表达式的第二个匹配符是:a。将它与字符串的第九个字符 a进行比较。又匹配了。于是继续读取正则表达式的第三个字符 t。
  • 正则表达式的第三个匹配符是 t。让我们继续与字符串的第十个字符比较。匹配成功。接着,尝试读取正则表达式的下一个字符,发现没有字符了,因此匹配结束。

回溯(backtracking)

为了应对NFA状态不确定,可能会匹配出错误的结果,因此需要“尝试失败-重新选择”的过程,现在,我已经解释了 NFA 是如何进行字符串匹配的——回溯法。我们将使用下面的例子,以便更好的解释回朔法。
  text="xyyyyyyz"
regex="xy{1,10}z"
这是一个比较简单的例子。正则表达式以 x 开始,以 z 结束。它们之间有以 1-10 个 y 组成的字符串。NFA 的匹配过程如下:
  • 首先,读取正则表达式的第一个匹配符 x,并将其与字符串的第一个字符 x 进行比较。两者匹配,所以,接下来是移动到正则表达式的第二个字符。
  • 读取正则表达式的第二个匹配符

    y{1,10}

    ,将它与字符串的第二个字符 y 进行比较。它们又匹配了。

    y{1,10}

    代表 1-10 个 y,基于 NFA 的贪婪特性(即,尽可能地进行匹配),此时它不会读取正则表达式的下一个匹配符,而是仍然使用

    y{1,10}

    与字符串的第三个字符 y 进行比较。它们匹配了。于是继续用 y{1,10} 与字符串的第n个字符 y 进行比较,直到第七个,它们不匹配。 回溯就出现在这里
  • 那么回溯是如何进行的?回溯后,字符串中已被读取的第七个字符 y 将被放弃。指针将返回到字符串的第三个字符。接着,正则表达式的下一个匹配符 z 会被用来与待匹配字符串当前指针的下一个字符 z 进行对比。两者是匹配的。这时,字符串最后一个字符已经被读取。匹配结束。

正则表达式的三种模式

  1. 贪婪模式
    • 这个就是最简单的匹配模式,也是最先接触的匹配模式
  2. 勉强模式
    • 在正则表达式中添加一个

      ?

      标志,贪婪模式将变成勉强模式。此时,它将尽可能少地匹配。然而,勉强模式下回溯仍可能出现。
  3. 独占模式
    • 如果添加

      +

      标志,则原来的贪婪模式将变成独占模式。也就是说,它将匹配尽可能多的字符,但不会回溯。
  text="xyyyyyyz"
regex="xy{1,10}?z"
正则表达式的第一个字符 x 与字符串的第一个字符 x 相匹配。正则表达式的第二个运算符

y{1,10}?

匹配了字符串的第二个字符 y 。由于最小匹配的原则,正则表达式将读取第三个运算符 z,并与字符串第三个字符 y 进行比较。两者不匹配。因此,程序进行回溯并将正则表达式的第二个运算符

y{1,10}?

与字符串的第三个字符 y 进行比较。还是匹配成功了。之后继续匹配,正则表达式的第三个匹配符 c 与字符串的第七个字符 z 正相匹配。匹配结束。
这三种模式,在Python,Java这些常见的开发工具中是比较常用的,然而在C++中并不是合适,我们开发团队经过一次次的修改、优化,在性能调优上才有了质的飞跃。

调优分析

下面以一份日志为例,介绍利用前面介绍的三种模式所开发出来的模型匹配。
  [INFO][08:27:34.260][2b0e7244d940]:LOGIN| client_id=007102| ip=8.8.8.8| uin=66666666 | mailname=123456789@139.com| userip=223.3.3.3|
我们想要的就是将日志中的数据进行提取,获得我们想要的内容,其中包括,clientIP、userID、user、mobileNumber这些,因为还有其他数据描述,后续提高数据挖掘的效率,和对安全风险的分析能力,我们也想对这些日志进行解析。一开始我们使用贪婪模式,也就是常见的使用

*

,看图中箭头方向,这个步长4635,大概需要11ms,步长其实就是回溯的次数,迭代计算这么多次,对于性能来说确实挺令人失望的,原因已经很明显了,就是由于

*

导致的,贪婪匹配n次直到和下个符号不匹配为止,因此消耗了大量的计算性能,这个也是我们需要进行优化地方。
点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小
  ^[(?P<type>.)][(?P<null1>.)][(?P<null2>.)].\=(?P<cid>.)|.\=(?P<ip>.)|.\=(?P<uin>.)|.\=(?P<mailname>.)|.\=(?P<userip>.*)$
接下来开始调优对原来的贪婪模式追加勉强匹配(外文名词翻译真让人抓狂),匹配效果卓著,原因在于勉强模式尽最大努力地减少了回溯次数,在原来的回溯全文之后的基础上,该模式如果遇匹配上了下个字符,立即结束,比如匹配

type

这个字段,我们的原先的贪婪模式,没遇到一次就会全文都匹配一遍之后在回到起点,确认匹配完成,而勉强模式则是在边界就停下来,比如

\]

,

\[

等字段。
到了这里我们并不满足,是否还可以更快,对计算资源是否可以更友好?毕竟我们的计算资源很宝贵,于是可以继续尝试使用独占模式。见下图
点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小
  ^[(?P<type>.?)][(?P<null1>.?)][(?P<null2>.?)].?\=(?P<cid>.?)|.?\=(?P<ip>.?)|.\=(?P<uin>.?)|.?\=(?P<mailname>.?)|.?\=(?P<userip>.*?)$
在这个模式下我们的表达式性能得到了极大的提升,此时相较于初始版本,性能已经提高了十倍,称之为勉强追加独占模式,该匹配已经匹配了,基本上可以交差给服务器日夜不停工作了。

     此时性能看起来已经达到了最优了,但我们要考虑到表达式的健壮性,毕竟在众多的日志里,总会出现有些字段为空(并不是null)的情况,如下图所示,我特意删除一些字段,如果是空格还好,当不是的时候又应该怎么处理咧?

     点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小

     这里需要使用

|

这个符号,对这样的场景经行适配,此时不管是空的还是有数据的都没啥关系了,我们已经做好了应对准备。

     点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小
  ^[(?P<type>.+?)][(?P<null1>.+?)][(?P<null2>.+?)].+?\=(?P<cid>.+?)|.+?\=(?P<ip>.+?)|.*\=(?P<uin>.+?)|.+?\=(?P<mailname>.+?)|.+?\=(?P<userip>.+?)$

最终版

点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小
  [(?P<type>|.+?)][(?P<null1>|.+?)][(?P<null2>|.+?)].+?\=(?P<cid>|.+?)|.+?\=(?P<ip>|.+?)|.*\=(?P<uin>|.+?)|.+?\=(?P<mailname>|.+?)|.+?\=(?P<userip>.+|)
这里我特意删除

^



$

这两个字符,考虑到在这个场景下,其实没必要规定起止符,因为我们是全文匹配的,起止符的出现反而需要计算机再验证一次是否到了终点,确定一下自己是不是在起点,有点画蛇添足。

结束语

在生产环境中学习很快,尴尬的就是没时间沉淀,生产的过程中遇到了好多我觉得是经典的场景,时间不允许匆匆留在工作笔记中,还没探究出所以然。之前以为我学会了正则,搞爬虫嘛,对正则也是要有一定的理解的,在进行模型分析的这段时间越发看不懂正则,总觉得这个是在写啥,官网说的是啥,看文档,现在写正则舒服很多了,处理日志各种不规范,提供的日志规范和接收到日志70%以上是不匹配的,还有拼写错误 ,各种命名法, 形式翻新,永不重复,这叫一个皮。。。

推荐网站

在线正则测试网站
这个网站可以很明显的提示我们表达式中的错误内容,或者说不符合语法规则的地方。跟我们说明该表达式的性能特点,消耗的资源等信息。



----------------------------
原文链接:https://blog.51cto.com/yerikyu/2330192

程序猿的技术大观园:www.javathinker.net



[这个贴子最后由 sunweiqin 在 2020-01-28 12:13:24 重新编辑]
  Java面向对象编程-->Java语言中的修饰符
  JavaWeb开发-->访问数据库(Ⅰ)
  JSP与Hibernate开发-->Java应用分层架构及软件模型
  Java网络编程-->基于UDP的数据报和套接字
  精通Spring-->通过Vuex进行状态管理
  Vue3开发-->通过Vuex进行状态管理
  Java中保留数字的若干位小数位数的方法
  观察者模式和发布订阅模式的区别
  Java虚拟机(JVM)参数配置说明
  用注解去代替if-else的技巧
  靠一个HashMap的讲解打动了头条面试官
  Java是如何实现自己的SPI机制的?
  使用 RocketMQ 事务消息,实现分布事务
  最实用的10个重构小技巧排行榜,你都用过哪些?
  Eclipse的安装配置
  java.util.logging.Logger使用详解
  Synchronized与ReentrantLock区别总结
  volatile 与 synchronized 详解
  Java设计模式:迭代器模式
  Java入门实用代码:修改文件最后的修改日期
  Java中的main()方法详解
  更多...
 IPIP: 已设置保密
树形列表:   
1页 0条记录 当前第1
发表一个新主题 开启一个新投票 回复文章


中文版权所有: JavaThinker技术网站 Copyright 2016-2026 沪ICP备16029593号-2
荟萃Java程序员智慧的结晶,分享交流Java前沿技术。  联系我们
如有技术文章涉及侵权,请与本站管理员联系。