首页|视野|消息|博览|滚动|焦点|新知|数据|追踪|聚合|推荐|围观|精选|快讯|热点|荐闻

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

发稿时间:2016-11-22 09:32:55 来源:米皮网

  【IT168 评论】正则表达式已经存在几十年了,它甚至早于今天甚嚣尘上的大数据,UI,机器学习以及其他几乎所有的工具和技术。许多开发人员通常认为正则表达式很神秘并且难以学习,嘲笑使用正则表达式来验证电子邮件地址的人。但是,正则表达式非常强大,优雅,简单和通用。

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

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

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

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

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

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

  示例日志行如下所示:

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

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

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

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

责任编辑:刘军
猜你喜欢