`
backkom1982
  • 浏览: 28357 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

正则表达式优化技巧总结

阅读更多

正则引擎的分类
正则引擎可以粗略地分为3类:

  • 以文本为主导的DFA(确定型有穷自动机)
  • 以正则表达式为主导的传统型NFA(非确定型有穷自动机)
  • POSIX NFA

部分程序及其使用的正则引擎

DFA
awk(大多数版本)、egrep(大多数版本)、mysql
传统NFA
GNU Emacs、java、grep(大多数版本)、less、more、perl、PHP、sed、vi
POSIX NFA
mawk、GNU Emacs(明确指定时使用)
DFA/NFA混合
GNU awk、GNU grep/egrep


影响正则表达式匹配的重要概念--回溯

    NFA引擎最重要的性质是,它会依次处理各个子表达式或组成元素,遇到需要在两个可能成功的可能中进行选择的时候,它会选择其一,同时记住另一个,以备稍后可能的需要。需要做出选择的情形包括量词(决定是否尝试另一次匹配) 和多选结构(决定选择哪个多选分去)。
    不论选择哪一种途径,如果它匹配成功,而且正则表达式的余下部分也成功了,匹配即告成功。如果正则表达式中余下的部分最终匹配失败,引擎会知道需要回溯到之前做出选择的地方,选择其他的备用分支继续尝试。这样引擎最终会尝试表达式的所有可能途径(或者是匹配完成之前需要的所有途径)。

    回溯的两个要点:
    如果需要在“进行尝试”和“跳过尝试”之间选择,对于匹配优先量词,引擎会优先选择“进行尝试”,而对于忽略优先量词,会选择“跳过尝试”。
距离当前最近储存的选项就是本地失败强制回溯时返回的。使用的原则是LIFO(后进先出)。
多选结构既不是匹配优先的,也不是忽略优先的,而是按顺序排列的,至少对传统型NFA来说是如此。也不是所有的流派都支持按序排列的多选结构。DFA和POSIX NFA确实有匹配优先的多选结构,它们总是匹配所有多选分支中能匹配最多文本的那个。但是,如果你使用的是Perl、PHP、.NET、java.util.regex,或者其他使用传统型NFA的工具,多选结构就是按序排列的。

    性能调优时评价的几个方面:

  • 哪种引擎从中获益?传统型NFA、或者POSIX NFA,或者两者?
  • 什么情况下,这种修改带来的收益最大?在文本能够匹配时,无法匹配时,还是所有时候?


技巧:

  • 如果多选分支是有序的,而能够匹配同样文本的多选分支又不只一个,就要小心安排多选分支的先后顺序。
  • 加速某些操作。某些类型的匹配,例如\d+,极为常见,引擎可能对此有特殊的处理方案,执行速度比通用的处理机制要快。
  • 避免冗余操作。如果引擎认为,对于产生正确结果来说,某些特殊的操作是不必要的,或者某些操作能够应用到比之前更少的文本,忽略这些操作能够节省时间。例如,一个以\A开头的正则表达式只有在字符串的开头位置才能匹配,如果在此处无法匹配,传动装置不会徒劳地尝试其他位置。
  • 消除无必要括号。正则引擎对捕获型括号,每次匹配都会记录状态,回退时需要清除状态。除非必要尽量不要使用捕获型括号。
  • 消除不需要的字符组。比如使用转义后的\.代替[.]
  • 对(.+)*之类的量词结合结构,避免制造指级的回溯
  • 使用占有优先量词消减回溯状态
  • 使用起始锚点。某些正则引擎会对此类表达式进行匹配优化。
  • 提取多选开头的必须元素。比如用th(is|at)代替this|that
  • 根据具体情况分析,使用忽略优先还是匹配优先,或使用固化分组和占有优先量词,以减少回溯
  • 拆分正则表达式。有时,在代码里多次执行拆分后的正则表达式比用一个正则表达式完成的同样的功能,执行时间反而更少。
  • 将最可能匹配的多选分支放在前头
  • 消除循环:常用的解法是opening normal*(special normal)*closing。避免无休止匹配的三个要点:1)special部分和normal部分匹配的开头不能重合。2)normal部分必须匹配至少一个字符。3)special部分必须是固化的。 亦可使用固化分组和占有优先量词。




实施优化时请谨记:有得必有失。实施了某个优化,可能对不同的正则引擎执行效率会产生很大的不同。请谨慎测试。

 

分享到:
评论

相关推荐

    精通正则表达式电子书

    - **优化技巧**:提供了关于如何优化正则表达式使用的技巧,帮助节省资源。 #### 五、正则表达式的实际应用 1. **数据验证**:利用正则表达式进行表单输入的有效性验证。 2. **文本搜索**:在大型文档中查找特定...

    C#表单正则表达式验证手册

    手册可能包含优化正则表达式以提高验证速度的技巧。 8. **案例分析**:通过具体的实例,如密码强度验证、URL验证、邮政编码验证等,帮助读者理解并应用正则表达式。 9. **异常处理**:处理可能出现的正则表达式...

    正则表达式测试工具 1.0绿色版

    总结来说,"正则表达式测试工具 1.0绿色版"是一个方便、实用的辅助工具,它可以帮助用户高效地测试和优化正则表达式,提高开发和数据处理的效率。配合使用说明.txt,用户可以更好地利用该工具提升自己的正则表达式...

    Python正则表达式操作指南.pdf

    ### Python正则表达式操作指南知识点总结 #### 一、Python正则表达式的引入与应用场景 - **Python正则表达式概述**: ...熟练掌握正则表达式的语法和技巧对于任何Python开发者来说都是非常重要的。

    精通正则表达式~~~

    第5章:正则表达式实用技巧.... 185 正则表达式的平衡法则... 186 若干简单的例子... 186 匹配连续行(续前)... 186 匹配IP地址... 187 处理文件名... 190 匹配对称的括号... 193 防备不期望的匹配... 194 ...

    快速完全精通正则表达式

    如果你已经对正则表达式有所了解,本书将帮助你进一步扩展知识边界,学习更高级的技术和技巧。 ##### 使用egrep搜索文本文件 egrep是Linux下用于文本搜索的强大工具之一。它支持更多的元字符和更复杂的模式匹配。 ...

    易语言正则表达式测试工具

    易语言作为中国本土化的一种编程语言,具有简单直观的语法特性,而该测试工具则为易语言开发者提供了一个便捷的平台,以调试和优化他们的正则表达式。 正则表达式是模式匹配的基石,它由一系列字符和特殊符号组成,...

    .net正则表达式测试工具

    3. **模式调整**:用户可以轻松切换单行模式和多行模式,观察不同模式下的匹配差异,从而优化正则表达式。 四、使用技巧 1. **预编译与缓存**:对于频繁使用的正则表达式,可以预先编译为`Regex`对象,以提高匹配...

    C#字符串和正则表达式参考手册

    在C#编程语言中,字符串和正则表达式是两个非常重要的概念,广泛应用于数据处理、文本分析和验证。下面将详细阐述这两个主题的...通过不断实践和学习,你可以掌握更多高级技巧,如自定义正则表达式构造器和优化性能等。

    正则表达式全集(8本)

    5. **正则表达式学习技巧和总结**:理解正则表达式的递归、非贪婪匹配、回溯等特性,有助于解决复杂问题。同时,记忆常见模式和利用在线工具(如RegexBuddy)进行测试和调试也是提升技能的关键。 6. **RegexBuddy ...

    java正则表达式pdf格式

    总结,《Java正则表达式详解》这份PDF文档涵盖了正则表达式的各个方面,从基本概念到高级技巧,结合实例详细解析,对于希望提升Java正则使用技能的开发者来说,是一份不可多得的学习资料。通过阅读和实践,你将能够...

    正则表达式系统教程

    总结,正则表达式系统教程将涵盖以上知识点,并通过实际示例和练习帮助学习者掌握正则表达式的使用技巧。无论你是编程新手还是经验丰富的开发者,这都将是一份极具价值的学习资源。通过阅读和实践“正则表达式系统...

    Python正则表达式指南

    - **高效正则表达式**:本文没有涉及如何编写高效的正则表达式以及优化技巧,请参考其他教程获取相关信息。 - **参考资料**:遇到不熟悉的术语或概念时,建议查阅百度、谷歌或维基百科等相关资源。 以上是对...

Global site tag (gtag.js) - Google Analytics