首页 > 其他 > 详细

正则性能调优

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

技术分享图片

正则表达式的原理

理论模型是有穷自动机,具体的实现为正则引擎(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次直到和下个符号不匹配为止,因此消耗了大量的计算性能,这个也是我们需要进行优化地方。
技术分享图片

^[(?P<type>.)][(?P<null1>.)][(?P<null2>.)].\=(?P<cid>.)|.\=(?P<ip>.)|.\=(?P<uin>.)|.\=(?P<mailname>.)|.\=(?P<userip>.*)$

接下来开始调优对原来的贪婪模式追加勉强匹配(外文名词翻译真让人抓狂),匹配效果卓著,原因在于勉强模式尽最大努力地减少了回溯次数,在原来的回溯全文之后的基础上,该模式如果遇匹配上了下个字符,立即结束,比如匹配type这个字段,我们的原先的贪婪模式,没遇到一次就会全文都匹配一遍之后在回到起点,确认匹配完成,而勉强模式则是在边界就停下来,比如\],\[等字段。
到了这里我们并不满足,是否还可以更快,对计算资源是否可以更友好?毕竟我们的计算资源很宝贵,于是可以继续尝试使用独占模式。见下图
技术分享图片

^[(?P<type>.?)][(?P<null1>.?)][(?P<null2>.?)].?\=(?P<cid>.?)|.?\=(?P<ip>.?)|.\=(?P<uin>.?)|.?\=(?P<mailname>.?)|.?\=(?P<userip>.*?)$

在这个模式下我们的表达式性能得到了极大的提升,此时相较于初始版本,性能已经提高了十倍,称之为勉强追加独占模式,该匹配已经匹配了,基本上可以交差给服务器日夜不停工作了。

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

技术分享图片

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

技术分享图片

^[(?P<type>.+?)][(?P<null1>.+?)][(?P<null2>.+?)].+?\=(?P<cid>.+?)|.+?\=(?P<ip>.+?)|.*\=(?P<uin>.+?)|.+?\=(?P<mailname>.+?)|.+?\=(?P<userip>.+?)$

最终版

技术分享图片

[(?P<type>|.+?)][(?P<null1>|.+?)][(?P<null2>|.+?)].+?\=(?P<cid>|.+?)|.+?\=(?P<ip>|.+?)|.*\=(?P<uin>|.+?)|.+?\=(?P<mailname>|.+?)|.+?\=(?P<userip>.+|)

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

结束语

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

推荐网站

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

正则性能调优

原文:http://blog.51cto.com/yerikyu/2330192

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!