叱咤大数据的Regex真的是正则表达式?

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
日志服务 SLS,月写入数据量 50GB 1个月
简介:
文章讲的是 叱咤大数据的Regex真的是正则表达式正则表达式已经存在几十年了,它甚至早于今天甚嚣尘上的大数据,UI,机器学习以及其他几乎所有的工具和技术。许多开发人员通常认为正则表达式很神秘并且难以学习,嘲笑使用正则表达式来验证电子邮件地址的人。但是,正则表达式非常强大,优雅,简单和通用。

叱咤大数据的Regex真的是正则表达式?

  即使在今天的大数据世界,正则表达式在任何软件工程师的工具包中都足以长期存在。根据形式语言理论,正则表达式作为计算机科学的基础与任何编程语言或机器可读数据格式一样重要,是非结构化数据被结构化的一种机制,使混乱的数据变得有秩序。

  当面对文本处理的挑战时,很少有工具比正则表达式更适合。然而,在某种程度上,有一些性能问题需要注意。为了探讨这些注意事项,让我们先来看一下计算机科学理论。什么是正则表达式?正则表达式是状态机的文本编码。正因如此,正则表达式的表达能力有限,但它可以非常有效地处理输入。例如,当计算机不能确定输入的是否是回文时,正则表达式可以确定字符串是否是回文。正则表达式严格来说不如上下文无关语法强大,而这些语法又不如完整的编程语言(如C或Java)强大。因此,任何可以使用正则表达式解决的,技术上也可以使用标准的编程语言解决。

  但是,结合大数据使用的Regex真的是正则表达式吗?看到这,很多人会不假思索的脱口而出“是”,但其实,Regex并不是标准的正则表达式。

叱咤大数据的Regex真的是正则表达式?

  严格地说,正则表达式与我们现在知道的Regex不同。这两个术语经常被混淆,但是多年来,从Perl的Regex引擎开始,Regex已经演变的比正规的正则表达式更强大。诸如从技术上看,捕获组反向引用的特征在实际的正则表达式中是不可能的。但真正的正则表达式可以被快速处理,支持正则表达式的引擎使用非常高效的Thompson NFA算法(例如SED,AWK和GREP)。而Regex设计了一种新的算法:递归回溯算法。这种新算法的出现引入了一系列正则表达式性能问题,性能慢现在几乎成了正则表达式的基本特征,尤其是在大数据时代。

  使用基于递归回溯的Regex引擎,可以制作出相对于输入长度在时间指数上更匹配的正则表达式,而Thompson NFA算法是在线时间匹配。如名称所暗示的,递归回溯算法的性能问题是由在处理输入中涉及的回溯引起的。当在大规模输入下使用正则表达式时,这种回溯会产生严重的后果,因为低效的正则表达式比正规的正则表达式需要更大的数量级来匹配。在大多数现代语言中,如Java,Python,Perl,PHP和JavaScript的标准正则表达式引擎都使用这种递归回溯算法,因此几乎任何涉及正则表达式的现代解决方案都容易受到性能不佳的正则表达式的攻击。幸运的是,几乎所有情况下,一个无效的正则表达式都可以被优化为一个有效的正则表达式,潜在地导致巨大的CPU周期节省。

  为了说明这一点,让我们考虑一个示例用例:解析日志数据。由于其可预测的格式,日志行可以容易地与正则表达式匹配,以提取有用的信息。假设下面的示例使用Regex来解析日志行是这样的:

叱咤大数据的Regex真的是正则表达式?

  示例日志行如下所示:

叱咤大数据的Regex真的是正则表达式?

  我们有兴趣收集的信息是app和web.1,它们通过第一和第二捕获组提取。虽然上面的正则表达式简单,可读,足以从输入文本中提取所需的信息,但一个高效的正则表达式是这样的:

叱咤大数据的Regex真的是正则表达式?

  两个正则表达式从相同的输入文本提取相同的数据。然而,第二个正则表达式对于它期望匹配的数据格式有更多的设定。它首先编码日志行的时间戳格式,这几乎立即排除了不匹配的日志行。同时,它使用了否定字符类,不是(.*),消除了几乎所有的回溯。低效的正则表达式,因为所有的.*回溯过度,导致匹配慢很多。因为它以.*开头,它将消耗很多文本,缩放输入直至结束。然后它将向后搜索,直到寻找到下一个字符,本文这个例子是空格字符。一旦从最后开始搜索遇到第一个空格,它会再次占用所有字符,直到输入和回溯结束,再次搜索下一个字符,如果找到一个开放的方括号,就在找到下一个开放的方括号时匹配结束,否则此过程会继续直到输入匹配或没有更多的可能性尝试。高效的正则表达式没有这种回溯,性能就会有很大提高。

  一个简单的基准,其中每个正则表达式被输入10,000次,表明无效的正则表达式比高效的正则表达式需要大约20倍的匹配。这是非常惊人的,因为两个正则表达式从同一个输入提取相同的信息。这意味着如果你想使用正则表达式解析大量数据,Regex定义中的一些小调整可能会需要20台机器进行处理,而正规的正则表达式则仅需要1台机器,这显然会使成本降低并免于延迟。

  所以,我们现在普遍认同的Regex并不是真正的正则表达式,但除了性能之外,它似乎已经在各方面超越了正规的正则表达式,以至于我们逐渐模糊了两者之间的界限,归为统一。


作者:zyy

来源:IT168

原文链接:叱咤大数据的Regex真的是正则表达式?

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps 
相关文章
|
8月前
|
Java
java regex 正则表达式 提取数字和去除数字,过滤数字,提取价格
java regex 正则表达式 提取数字和去除数字,过滤数字,提取价格
|
16天前
|
存储 C++ 容器
C++一分钟之-正则表达式库(regex)
【7月更文挑战第7天】C++从C++11开始支持正则表达式,通过`<regex>`库提供功能。本文涵盖基本概念如`std::regex`、`std::smatch`,以及`regex_search`和`regex_match`的使用。常见问题包括大小写敏感性、特殊字符转义、贪婪与非贪婪匹配和捕获组。提供的代码示例展示了如何进行匹配、不区分大小写的匹配、特殊字符匹配、贪婪与非贪婪匹配和捕获组的使用。理解并练习正则表达式能提升文本处理效率。
15 0
|
24天前
|
数据采集 分布式计算 DataWorks
DataWorks产品使用合集之odps如何使用正则表达式匹配字段的内容
DataWorks作为一站式的数据开发与治理平台,提供了从数据采集、清洗、开发、调度、服务化、质量监控到安全管理的全套解决方案,帮助企业构建高效、规范、安全的大数据处理体系。以下是对DataWorks产品使用合集的概述,涵盖数据处理的各个环节。
39 0
|
2月前
|
机器学习/深度学习 Python
正则表达式(Regular Expression,常简写为regex或regexp)是一种强大的文本处理工具
【5月更文挑战第12天】正则表达式是文本处理工具,Python的re模块支持其使用。元字符如.、*、+、?等在正则表达式中具有特殊含义,用于指定匹配规则。示例中,通过正则表达式模式匹配字符串中的电子邮件地址,并使用re.findall()找出所有匹配项。
41 4
|
2月前
|
安全
正则表达式(Regular Expression,简称regex或regexp)
正则表达式(Regular Expression,简称regex或regexp)
34 2
|
2月前
|
Python
在Python中,如何使用`regex`库进行正则表达式匹配?
在Python中,如何使用`regex`库进行正则表达式匹配?
34 0
|
2月前
|
Python
Python 正则表达式(RegEx)指南
正则表达式(RegEx)是一系列字符,形成了一个搜索模式。RegEx 可用于检查字符串是否包含指定的搜索模式。
54 0
|
9月前
|
C++ Windows Perl
[笔记]c++基础实践《二》regex正则表达式
[笔记]c++基础实践《二》regex正则表达式
re/regex:正则表达式(持续更新ing...)
re/regex:正则表达式(持续更新ing...)
|
大数据 Scala 分布式计算
大数据Scala系列之文件以及正则表达式
大数据Scala系列之文件以及正则表达式1 读取行导入scala.io.Source后,即可引用Source中的方法读取文件信息。 import scala.io.Sourceobject FileDemo extends App{ val source = Source.
1376 0