`
liyiye
  • 浏览: 425420 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

优化Java中的正则表达式

    博客分类:
  • java
阅读更多

如果你花费了数小时和正则表达式做斗争,只是为了让它完成它几秒内就可以完成的匹配,那么这篇文章正是为你量身定做的。Cristian Mocanu指出了在什么地方正则模式匹配会发生延迟,并且解释了为什么。然后,他演示了如何做更多的回缩(backtracking)而不是迷失在其中,如何优化贪婪模式和勉强模式(译者注——这个翻译是在网上查到,总感觉不太合适,原文是reluctant quantifier),以及Possessive quantifiers(译者注——这个有的地方称为抢占量子)、独立分组(independent grouping)和环视(look-around)为什么是你的朋友。

    编写正则表达式不仅仅是一种技巧,更是一种艺术 ——Jeffrey Friedl

    本文中,我将介绍一些正则表达式中使用默认的java.util.regex包的常见缺点。我将解释为什么回缩(backtracking)既是使用正则表达式进行模式匹配的基础,又是应用程序代码中的常见瓶颈;为什么在使用贪婪模式和勉强模式要学会谨慎,以及它是你正则表达式优化的要素。然后我会介绍优化正则表达的技巧,并讨论通过Java模式匹配引擎运行新的正则表达式时会发生什么。

    基于本文的目的,我假设你已经有使用正则表达式的经验,并且对在Java代码中优化它们抱有很大的兴趣。本文主题包括简单和自动优化优化技巧,以及如何使用抢占量子(possessive quantifiers)、独立分组(independent grouping)和环视(lookarounds)优化贪婪模式和勉强模式(greedy and reluctant quantifiers)。关于Java中正则表达式的介绍,请参考本文的资源部分。

    Java模式匹配引擎和回缩(The Java pattern-matching engine and backtracking)

    java.util.regex包使用一种称为非确定性的有限自动机(Nondeterministic Finite Automaton,简称为NFA)的模式匹配引擎。之所以称之为非确定性的,是因为当尝试使用输入的字符串匹配一个正则表达式时,每一个字符会因为正则表达式的不同部分而被多次检查。这也是一种在。NET、PHP、Perl、Python和Ruby被广泛使用的引擎。它将大部分的权利交到了程序员手里,提供了宽范围的量词和其他专有的结构如环视(lookarounds),在后面部分将会讨论。

    NFA在本质上使用回缩。通常情况下,并非只有一种方式在给定的字符串上使用正则表达式,因此模式匹配引擎会尝试所有情况,直到它宣布失败。为了更好的理解NFA和回缩(backtracking),考虑下面的例子:正则表达式是“sc(ored|ared|oring)x”,输入字符串是“scared”。

    首先引擎会寻找“sc”,由于在输入字符串的起始两个字符,因此会立即找到。然后,它会从输入字符串的第三个字符开始尝试匹配“ored”。没有匹配项,它就回到第三个字符,尝试“ared”。找到匹配,于是它继续向前,尝试匹配“x”。不能找到匹配,它将返回第三个字符,寻找“oring”。仍然没有匹配,于是它就返回到输入字符串的第二个字符,开始寻找另外一个“sc”。一直到达输入字符串的结束,它将宣布失败。

    回缩的优化小技巧(Optimization tips for backtracking)

    通过上面的例子,你已经看到了NFA如何使用回缩进行模式匹配的,同时你也会发现回缩存在的一个问题。甚至在上面十分简单的例子中,引擎为了将输入字符串匹配到正则表达式不得不回退数次。不难想象,如果回缩使失去控制,将会对你的应用程序的性能发生什么样的影响。优化正则表达式的一个重要部分就是最小化回缩的数量。

    Java模式匹配引擎有一些可以自由支配的优化规则,并可以自动应用它们。在本文稍后的部分我将会讨论其中的一些规则。不幸的是,你不能总是依赖引擎来优化你的正则表达式。在上面的例子中,正则表达式的确可以相当快地匹配,但是在多数情况中,对于引擎自动优化来说,表达式过于复杂,而输入字符串也过大。

    由于回缩,在现实场景中正则表达式有时候会遇到花费数小时完成匹配的情况。更惨的是,引擎会花费比匹配成功更长的时间声明正则表达式不匹配输入字符串。牢记这个重要的事实。当你想要测试正则表达式的速度时,使用其不能匹配的字符串进行测试。其中,特别是使用几乎匹配的字符串,因为它们会消耗最长的时间。

现在,我们考虑一些可以优化正则表达式的针对回缩的方法。

    优化正则表达式的简单方法(Simple ways to optimize regular expressions)

    在本文后面的部分,我会介绍更加复杂的方法,你可以使用它们优化Java中的正则表达式。不过,作为开始,这里是一些可以节省时间的简单优化方式:1、如果在程序中多次使用同一个正则表达式,一定要用Pattern.compile()编译,代替直接使用Pattern.matches()。如果一次次对同一个正则表达式使用Pattern.matches(),例如在循环中,没有编译的正则表达式消耗比较大。因为matches()方法每次都会预编译使用的表达式。另外,记住你可以通过调用reset()方法对不同的输入字符串重复使用Matcher对象。

    2、留意选择(Beware of alternation)。类似“(X|Y|Z)”的正则表达式有降低速度的坏名声,所以要多留心。首先,考虑选择的顺序,那么要将比较常用的选择项放在前面,因此它们可以较快被匹配。另外,尝试提取共用模式;例如将“(abcd|abef)”替换为“ab(cd|ef)”。后者匹配速度较快,因为NFA会尝试匹配ab,如果没有找到就不再尝试任何选择项。(在当前情况下,只有两个选择项。如果有很多选择项,速度将会有显著的提升。)选择的确会降低程序的速度。在我的测试中,表达式“。*(abcd|efgh|ijkl)。*”要比调用String.indexOf()三次——每次针对表达式中的一个选项——慢三倍。

    3、获取每次使用引起小损失的分组。如果你实际并不需要获取一个分组内的文本,那么就使用非捕获分组。例如使用“(?:X)”代替“(X)”。

    让引擎完成优化(Let the engine do the work for you)

    如上面我所提到的,java.util.regex包可以编译正则表达式时对其优化。例如,正则表达式中包含了一个必须在输入字符串中出现的字符串(或者整个表达式都不匹配),引擎有时会首先搜索该字符串,如果没有找到匹配就会报告失败,不再检查整个正则表达式。

    另外非常有用地自动优化正则表达式的方式让引擎根据正则表达式中的期望长度检查输入字符串的长度。例如,表达式“\d{100}”是内在优化的,以致于如果输入字符串不是100个字符,引擎就会报告失败,而不再考察整个正则表达式。

    无论何时编写复杂的正则表达式时,尝试找出一种编写方式使引擎可以识别和优化这些特殊情况。例如,不要在分组或选择中隐藏命令字符串,因为引擎不会识别它们。若有可能,指定你想要匹配的输入字符串的长度也是相当有用的,如上例所示。

    优化贪婪模式和勉强模式(Optimizing greedy and reluctant quantifiers)

    你已经有了如何优化正则表达式的基本概念,其中一些方式可以让引擎来完成优化。现在我们讨论优化贪婪模式和勉强模式。贪婪模式量词如“*”或“+”,会首先从输入字符串中尝试匹配尽可能多的字符,即使这意味着字符串中的剩下的内容已经不足以匹配正则表达式的其余部分。如果是这样,贪婪模式量词就会回缩,返回字符,知道可以完全匹配或者没有字符了。勉强(或者lazy)模式,另一方面,会首先尝试匹配输入字符串中尽可能少的字符。

    那么举个例子,比如说你想优化一个子表达式“。*a”。如果字符a在输入字符串临近结尾处,使用贪婪模式量词“*”较好。如果这个字符在输入字符串的开始位置附近,使用勉强模式的量词“*?”好一些,可以将子表达式改为“。*?a”。通常情况下,我注意到勉强模式比贪婪模式稍微快一些。

    另外一个编写正则表达式技巧是比较明确的。尽量少使用普通的子结构像“。*”,因为它们会引起很多回缩,特别是剩余的表达式不能匹配输入字符串时。例如,如果你想获取输入字符串中两个a之间的内容,可以使用“a([^a]*)a”代替“a(。*)a”。

    抢占量子和独立分组(Possessive quantifiers and independent grouping)

    抢占量子和独立分组是优化正则表达式最有用的操作符。无论何时使用它们你都可以戏剧性地改善表达式的运行时间。抢占量子由额外的“+”表示,例如表达式中“X?+”、“X*+”和“X++”。独立分组的符号是“(?>X)”。

    我曾经同时使用抢占量子和独立分组成功地将正则表达式的运行从几分钟减少几秒钟。两种操作符都会使模式匹配引擎的针对分组的回缩行为失去作用。它们会尝试匹配它们的表达式就像贪婪模式一样,但是如果不能匹配,它们不会返回已经匹配的字符,即使引起整个表达式失败。

    它们之间的差异是非常微妙的。你最好通过比较抢占量子“(X)*+”和独立分组“(?>X)*”来了解。前者,抢占量子会取消针对X子表达式和“*”量词的回缩。后者,只有针对X子表达式的回缩会取消,而分组之外的“*”操作符,不受独立分组的影响,还是可以任意回缩。

 

你怎么优化这个正则表达式?(How would you optimize this regular expression?)

    现在我们看一个优化的例子。假如你尝试在一个长输入字符串中匹配子表达式“[^a]*a”,输入字符串中只有重复出现的字母b.这个表达式将会失败,因为输入字符串没有包含字母a.因为模式匹配引擎不知道这一点,你会尝试匹配表达式“[^a]*”。因为“*”是一个贪婪模式量词,它会获取所有字符直到输入字符串结束,然后开始回退,寻找匹配时每次返回一个字符。

    当不能再回缩时,这个表达式就会失败,这会花费不少时间。更坏的是,因为“[^a]*”获取所有不是a的字符,即使回缩作用也不大。

    解决方法是将表达式由“[^a]*a”改为“[^a]*+a”,使用抢占量子“*+”。新表达式会更快失败,因为一旦它阐释匹配所有非a子符,它不回缩;于是在此处匹配失败。

    环视结构(Lookaround constructs)

    如果你想写一个匹配除某些字符之外的任意字符的正则表达式,可以很轻松写出类似“[^abc]*”这样的表达式,它表示:匹配除a、b或c之外的任意字符。但是,如果你想匹配如“cab”或“cba”而不是“abc”这样的字符串时应该怎么做呢?

    对于这种情况,你可以使用环视结构(lookaround constructs)。java.util.regex包包含了四种类型:1、正向向前寻找(Positive lookahead):“(?=X)”

    2、负向向前寻找(Negative lookaheade):“(?!X)”

    3、正向向后寻找(Positive lookbehind):“(?<=X)”

    4、负向向后寻找(Negative lookbehind):“(?<!X)”

    此处正向(Positive)是指你希望表达式匹配,而负向(Negative)则表示你不想表达式匹配。向前查找(Lookahead)是指你想搜索输入字符串中当前位置的右面部分。向后查找(Lookbehind)则是指搜索当前位置的左面部分。请紧记,环视结构只是向前或向后看,实际上并不改变输入字符串的当前位置。比如说,你可以在表达式“((?!abc)。)*”使用负向向前寻找操作符“?!”匹配任何除“abc”外的任何顺序的字符。

    实战环视结构(Lookarounds in practice)

    在编写正则表达式时,环视结构可以在更细节上提供帮助,在匹配性能会有明显的效果。代码1演示了一个非常简单的例子:使用正则表达式匹配HTML域。

    代码1. 匹配HTML域Regular expression: "<img.*src=(\S*)/>" Input string 1: "<img border=1 src=image.jpg />" Input string 2: "<img src=src=src=src= …… many src= …… src=src=>"

    代码1中的正则表达式的目的是匹配HTML的image标签中的src属性的内容。我特意简化了这个表达式,假定在src之后没有其他属性,这样可以将精力集中到性能上。

    这个表达式匹配输入的字符串“string 1”时速度足够快,但是尝试匹配输入字符串“string 2”并宣布失败时花费了很长时间(随着输入字符串的长度成指数增长)。它匹配失败是因为输入字符串结尾没有“/>”。为了优化这个表达式,看一下第一个“。*”结构。它匹配“src”之前的任何属性,但是太普通并且匹配次数太多了。事实上,这个结构应该只匹配除“src”之外的属性。

    重写的表达式“<img((?!src=)。)*src=(\S*)/>”处理大且不匹配的字符串的速度要比原来的快将近100倍。

 

为什么不是lazy模式?

    你可能会认为我会使用勉强模式“。*?”优化代码1中的正则表达式。事实上,“<img.*?src=(。*)/>”能够轻易地匹配第一个遇到的“src=”。这个解决方案在该正则表达式可以匹配的时候能够正常工作。如果它不能匹配输入字符串,然而,它将开始回缩,然后消耗和贪婪模式同样长的时间。记住,首先使用不能匹配的字符串测试正则表达式。

    注意StackOverflowError(A note about the StackOverflowError)

    有时regex包中的Pattern类会抛出StackOverflowError.这是已知的bug #5050507的表现,它自从Java 1.4就存在于java.util.regex包中。这个bug仍然存在,因为它是“won't fix”的状态。这个错误的出现是因为,Pattern类把一个正则表达式编译为一个用来寻找匹配的小程序。这个程序被递归调用,有时太多的递归就会导致该错误的出现。更多细节请参考bug描述。看起来大部分是在使用选择(alternation)的出现。

    如果你碰到了这个错误,尝试重写正则表达式,或者分为几个子表达式,然后分别单独执行。后者有时设置会提高性能。

    总结(In conclusion)

    正则表达式不应该花费数小时匹配,特别是应用程序只有几秒时间时。在本文中,我介绍了java.util.regex包的一些弱点,并且向你展示了如何克服这些弱点。像回缩(backtracking)这样的简单瓶颈只需要一些小小的技巧,而像贪婪模式和勉强模式(greedy and reluctant quantifiers)这样的罪魁祸首就需要更加仔细的考虑。在某些情况下,你可以完全替换它们,而在另外一些情况下,可以使用“环视(lookaround)”。无论哪种方式,你已经掌握了一些正则表达式的提升速度的技巧。

分享到:
评论

相关推荐

    java正则表达式.zip

    - 正则表达式中的特殊字符需要转义,如`\d`应写为`\\d`。 - 如果正则表达式在字符串中,需要额外的转义,如`"\\d\\d"`。 - 贪婪与非贪婪匹配:默认情况下,`*`, `+`, `?`是贪婪的,会尽可能多地匹配。如果在后面加上...

    详解Java判断是否是整数,小数或实数的正则表达式

    在Java中使用正则表达式来判断字符串是否符合整数、小数或实数的格式是一种常见且有效的做法。在编程中,我们经常需要对输入的字符串进行格式验证,以确保它们符合预期的数值格式,尤其是在处理财务数据、用户输入...

    Java 正则表达式判断字符串是否包含中文

    ### Java正则表达式判断字符串是否包含中文 在日常的软件开发过程中,我们经常会遇到需要对输入的字符串进行校验的情况。例如,在处理用户输入、文本分析或数据清洗时,可能需要判断一个字符串中是否包含中文字符。...

    java正则表达式使用例子

    Java正则表达式是Java编程语言中用于处理字符串的强大工具,它允许我们通过模式匹配来查找、替换或分割文本。在Android开发中,正则表达式尤其重要,因为它们可以帮助我们验证用户输入、处理文本数据或者进行复杂的...

    Java 正则表达式库

    这个库不仅包含了标准Java API中的`java.util.regex`包,还可能包含了一些第三方库,如`automaton-1.11-7`,这可能是对Java正则表达式功能的一种扩展或优化。 正则表达式的语法是相当丰富的,包括字符类(如`\d`...

    正则表达式转DFA

    Java实现的这个项目提供了一个直观的方式去理解这一转换过程,并通过可视化结果加深对正则表达式和DFA之间关系的理解。源代码文件中应该包含了具体的实现细节,包括类的设计、方法的编写以及如何调用Graph库进行绘图...

    正则表达式工具类,正则表达式封装,Java正则表达式

    总之,`RegUtils`是一个为了简化Java正则表达式操作而设计的工具类,它通过封装各种常见的正则表达式操作,使得开发者可以更方便地在代码中进行文本处理。在实际项目中,此类的使用能提高代码的可读性和可维护性。...

    精通正则表达式(第3版)(含awz3 mobi epub)

    本书主要讲解了正则表达式的特性和流派、匹配原理、优化原则、实用诀窍以及调校措施,并详细介绍了正则表达式在Perl、Java、.NET、PHP中的用法。 本书自第1 版开始着力于教会读者“以正则表达式来思考”,来让读者...

    JAVA 正则表达式测试器

    通过使用Java正则表达式测试器,开发者可以更高效地调试和优化他们的正则表达式,提高代码质量。无论是新手还是经验丰富的程序员,这个工具都能极大地提升开发效率,减少因为正则表达式错误导致的问题。

    java中用正则表达式检测IP地址是否合理

    - `\\.`: 匹配点号,由于点号在正则表达式中有特殊含义,所以需要用反斜杠转义。 #### 4. 实现代码示例 下面是一个简单的Java程序示例,演示了如何使用正则表达式来验证IP地址的有效性: ```java package RegEx; ...

    java常用正则表达式(转)

    Java中的正则表达式是处理字符串的强大工具,它在编程中扮演着不可或缺的角色,尤其是在文本处理、数据验证和模式匹配等方面。这篇博客“java常用正则表达式(转)”可能详细介绍了Java如何使用正则表达式进行各种...

    强大的JAVA正则表达式处理包jakarta-oro

    在Java标准库中的java.util.regex包之外,Jakarta ORO提供了额外的特性和优化,使得它在某些场景下比原生的Java正则表达式API更为实用。 Jakarta ORO的核心功能包括: 1. **高效性能**:Jakarta ORO采用了优化的...

    java正则表达式教程html版带目录

    Java正则表达式是Java编程语言中的一个强大工具,它用于模式匹配和字符串处理,尤其在数据验证、文本检索和替换等方面发挥着重要作用。本教程是专为初学者设计的HTML版,旨在帮助读者快速掌握Java正则表达式的概念和...

    测试正则表达式软件

    这对于学习和优化正则表达式非常有帮助,避免了在代码中反复测试的麻烦。 总的来说,正则表达式是Java编程中不可或缺的一部分,熟练掌握其用法可以提高代码的效率和可读性。测试正则表达式的软件是开发者的好帮手,...

    Java Swing版的正则表达式测试工具

    Java中的正则表达式主要通过`java.util.regex`包来支持,这个包包含`Pattern`、`Matcher`和`MatchResult`等类,它们提供了丰富的功能来处理正则表达式。 在这款测试工具中,用户可以输入自定义的正则表达式,然后...

    通过正则表达式生成数据

    2. **利用编程语言**:大多数编程语言如Python、Java、JavaScript等都内置了正则表达式的支持,并提供了方法来生成符合正则表达式的随机字符串。例如,Python的`re`模块配合`random.choice`或`random.choices`可以...

    正则表达式的调试器java实现

    3. **分组与回溯**:正则表达式中的括号可以创建分组,`Matcher`提供了访问这些分组的方法,如`group(int group)`。回溯机制允许正则引擎在匹配失败时撤销先前的匹配,以尝试其他可能性。 4. **迭代匹配**:对于...

    精通正则表达式 中英文

    如今,正则表达式已经成为众多语言及工具——Perl、PHP、Java、Python、Ruby、MysQL、VB.NET和c#(以及.NET Framework中的任何语言)——中的标准特性,依靠它,你能以之前完全不敢设想的方式进行复杂而精巧的文本...

    java正则表达式资料下载

    - **元字符**: 在正则表达式中,一些字符具有特殊含义,如`.`代表任意字符,`\d`代表数字,`\w`代表单词字符(字母、数字或下划线),`\s`代表空白字符。 - **量词**: `*`表示零个或多个前一个字符,`+`表示一个或...

Global site tag (gtag.js) - Google Analytics