网站导航网学 原创论文 网站设计 最新系统 最新研究 原创论文 获取论文 论文降重 发表论文 论文发表 UI设计定制 论文答辩PPT格式排版 期刊发表 论文专题
返回网学首页
网学原创论文
最新论文 推荐专题 热门论文 论文专题
当前位置: 网学 > 设计资源 > 正则表达式 > 正文

正则表达式之贪婪与非贪婪模式详解(概述)

来源:http://myeducs.cn 联系QQ:点击这里给我发消息 作者: 用户投稿 来源: 网络 发布时间: 13/06/29
用固化分组,对正则做进一步的优化。

给出正则表达式四:"(?>[^"]*)"

固化分组并不是所有语言都支持的,如.NET支持,而Java就不支持,但是在Java中却可以使用更简单的占有优先量词来代替:"[^"]*+"。

3 贪婪还是非贪婪模式——再谈匹配效率
一般来说,贪婪与非贪婪模式,如果量词修饰的子表达式相同,比如“.*”和“.*?”,它们的应用场景通常是不同的,所以效率上一般不具有可比性。

而对于改变量词修饰的子表达式,以满足需求时,比如把“.*”改为“[^"]*”,由于修饰的子表达式已不同,也不具有直接的可对比性。但是在相同的子表达式,又都可以满足需求的情况下,比如“[^"]*”和“[^"]*?”,贪婪模式的匹配效率通常要高些。

同时还有一个事实就是,非贪婪模式可以实现的,通过优化量词修饰的子表达式的贪婪模式都可以实现,而贪婪模式可以实现的一些优化效果,却未必是非贪婪模式可以实现的。

贪婪模式还有一点优势,就是在匹配失败时,贪婪模式可以更快速的报告失败,从而提升匹配效率。下面将全面考察贪婪与非贪婪模式的匹配效率。

3.1 效率提升——演进过程
在了解了贪婪与非贪婪模式的匹配基本原理之后,我们再来重新看一下正则效率提升的演进过程。

需求:取得两个“"”中的子串,其中不能再包含“"”。

源字符串:The phrase "regular expression" is called "Regex" for short.

正则表达式一:".*"

正则表达式一匹配的内容为“"regular expression" is called "Regex"”,不符合要求。

提出正则表达式二:".*?"

首先“"”取得控制权,由位置0位开始尝试匹配,直到位置11处匹配成功,控制权交给“.*?”,匹配过程同2.2.1中非贪婪模式的匹配过程。“.*?”匹配的内容为“Regex”,匹配过程中进行了四次回溯。

如何消除回溯带来的匹配效率的损失,就是使用更小范围的子表达式,采用贪婪模式,提出正则表达式三:"[^"]*"

首先“"”取得控制权,由位置0位开始尝试匹配,直到位置11处匹配成功,控制权交给“[^"]*”,匹配过程同2.2.2节中非贪婪模式的匹配过程。“[^"]*”匹配的内容为“Regex”,匹配过程中没有进行回溯。

3.2 效率提升——更快的报告失败
以上讨论的是匹配成功的演进过程,而对于一个正则表达式,在匹配失败的情况下,如果能够以最快的速度报告匹配失败,也会提升匹配效率,这或许是我们设计正则过程中最容易忽略的。而在源字符串数据量非常大,或正则表达式比较复杂的情况下,是否能够快速报告匹配失败,将对匹配效率产生直接的影响。

下面将构建匹配失败的正则表达式,对匹配过程进行分析。

以下匹配过程分析中,源字符串统一为:The phrase "regular expression" is called "Regex" for short.

3.2.1 非贪婪模式匹配失败过程分析
3-1
图3-1

构建匹配失败的非贪婪模式的正则表达式:".*?"@

由于最后的“@”的存在,这个正则表达式最后一定是匹配失败的,那么看一下匹配过程。

首先由“"”取得控制权,由位置0处开始尝试匹配,匹配失败,直到图中标示的A处匹配成功,控制权交给“.*?”。

“.*?”取得控制权后,由A后面的位置开始尝试匹配,由于是非贪婪模式,首先忽略匹配,将控制权交给“"”,同时记录一下回溯状态。“"”取得控制权后,由A后面的位置开始尝试匹配,匹配字符“r”失败,查找可供回溯的状态,将控制权交给“.*?”,由“.*?”匹配字符“r”。重复以上过程,直到“.*?”匹配了B处前面的字符“n”,“"”匹配了B处的字符“””,将控制权交给“@”。由“@”匹配接下来的空格“ ”,匹配失败,查找可供回溯的状态,控制权交给“.*?”,由“.*?”匹配空格。继续重复以上匹配过程,直到由“.*?”匹配到字符串结束位置,将控制权交给“"”。由于已经是字符串结束位置,匹配失败,报告整个表达式在
  • 下一篇资讯: 正则基础之神奇的转义
  • 网学推荐

  • ·【推荐参考】最新可过维普检测低于30%
  • ·【推荐】原创参考论文 原创资料
  • ·【推荐】原创参考论文导航
  • ·咨询参考QQ:3710167
  • ·咨询参考微信号:yclw90
  • ·扫一扫 加微信 咨询
  • ·我们提供原创参考论文和原创的参考资料!
  • ·很多朋友如果想要查重指导等,请沟通我们!
  • ·原创的论文资料参考省时间!
  • ·论文格式排版可以找我们!
  • ·论文答辩PPT格式排版定制!
  • ·程序和网站等UI设计定制!
  • ·程序设计定制!
  • ·网站设计定制!
  • ·UI设计定制!
  • ·程序和网站等UI设计定制!
  • ·原创参考论文参考定制!
  • 免费论文

    原创论文

    设为首页 | 加入收藏 | 论文首页 |原创论文 |
    版权所有 QQ:3710167 邮箱:3710167@qq.com 网学网 [Myeducs.cn] 您电脑的分辨率是 像素
    Copyright 2008-2020 myeducs.Cn www.myeducs.Cn All Rights Reserved 湘ICP备09003080号 常年法律顾问:王律师