- 浏览: 271959 次
- 性别:
- 来自: 山东
最新评论
-
xchz:
没想到做的这么完善
状态模式-实现屏幕截取程序 -
songwangchu:
不错啊。哈哈哈
Reactor模式,或者叫反应器模式 -
yuanliangding:
很简洁易懂。怎么没有系列文章
Reactor模式,或者叫反应器模式 -
过冷水:
讲的不错
Reactor模式,或者叫反应器模式 -
Hero_z:
讲的非常通俗易懂,108个赞!!!
Reactor模式,或者叫反应器模式
使用RegexBuddy测试正确的正则,放入到java代码中会抛出stackoverflowerror.
开始以为是文件太长,将文件减短后还是会有问题,觉得应该是java内置的正则的问题,网上Google了一下,遇到这个问题的人多了去了。
java内置的正则解析器有问题,不过可以绕过去。有两个较好用的库,这两个库都不会发生StackOverFlowerError(这里有点错误,使用jregex还是会发生溢出的)。
pattwo :http://www.javaregex.com
jregex :http://sourceforge.net/projects/freshmeat_jregex
另有一篇参考文档:
http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html
-----------------------------------------2009.5.25日凌晨更新---------------------
这两天觉得正则表达式在匹配时会溢出的问题还是没有搞清楚,所以就又google了一下,发现距离答案又近了一些。栈溢出并不是java的bug,这和正则表达式引擎的算法有关系。主要有两种正则引擎:DFA和NFA。
有一往篇文章介绍的挺好,这里拿过来用一下
1. 了解正则表达式的历史
正则表达式萌芽于1940年代的神经生理学研究,由著名数学家Stephen Kleene第一个正式描述。具体地说,Kleene归纳了前述的神经生理学研究,在一篇题为《正则集代数》的论文中定义了“正则集”,并在其上定义了一个代数系统,并且引入了一种记号系统来描述正则集,这种记号系统被他称为“正则表达式”。在理论数学的圈子里被研究了几十年之后,1968年,后来发明了 UNIX系统的Ken Thompson第一个把正则表达式用于计算机领域,开发了qed和grep两个实用文本处理工具,取得了巨大成功。在此后十几年里,一大批一流计算机科学家和黑客对正则表达式进行了密集的研究和实践。在1980年代早期,UNIX运动的两个中心贝尔实验室和加州大学伯克利分校分别围绕grep工具对正则表达式引擎进行了研究和实现。与之同时,编译器“龙书”的作者Alfred Aho开发了Egrep工具,大大扩展和增强了正则表达式的功能。此后,他又与《C程序设计语言》的作者Brian Kernighan等三人一起发明了流行的awk文本编辑语言。到了1986年,正则表达式迎来了一次飞跃。先是C语言顶级黑客Henry Spencer以源代码形式发布了一个用C语言写成的正则表达式程序库(当时还不叫open source),从而把正则表达式的奥妙带入寻常百姓家,然后是技术怪杰Larry Wall横空出世,发布了Perl语言的第一个版本。自那以后,Perl一直是正则表达式的旗手,可以说,今天正则表达式的标准和地位是由Perl塑造的。Perl 5.x发布以后,正则表达式进入了稳定成熟期,其强大能力已经征服了几乎所有主流语言平台,成为每个专业开发者都必须掌握的基本工具。
2. 掌握一门正则表达式语言
使用正则表达式有两种方法,一种是通过程序库,另一种是通过内置了正则表达式引擎的语言本身。前者的代表是 Java、.NET、C/C++、Python,后者的代表则是Perl、Ruby、JavaScript和一些新兴语言,如Groovy等。如果学习正则表达式的目标仅仅是应付日常应用,则通过程序库使用就可以。但只有掌握一门正则表达式语言,才能够将正则表达式变成编程的直觉本能,达到较高的水准。不但如此,正则表达式语言也能够在实践中提供更高的开发和执行效率。因此,有心者应当掌握一门正则表达式语言。
3. 理解DFA和NFA
正则表达式引擎分成两类,一类称为DFA(确定性有穷自动机),另一类称为NFA(非确定性有穷自动机)。两类引擎要顺利工作,都必须有一个正则式和一个文本串,一个捏在手里,一个吃下去。DFA捏着文本串去比较正则式,看到一个子正则式,就把可能的匹配串全标注出来,然后再看正则式的下一个部分,根据新的匹配结果更新标注。而NFA是捏着正则式去比文本,吃掉一个字符,就把它跟正则式比较,匹配就记下来:“某年某月某日在某处匹配上了!”,然后接着往下干。一旦不匹配,就把刚吃的这个字符吐出来,一个个的吐,直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响:
1. DFA 对于文本串里的每一个字符只需扫描一次,比较快,但特性较少;NFA要翻来覆去吃字符、吐字符,速度慢,但是特性丰富,所以反而应用广泛,当今主要的正则表达式引擎,如Perl、Ruby、Python的re模块、Java和.NET的regex库,都是NFA的。
2. 只有NFA才支持lazy和backreference等特性;
3. NFA急于邀功请赏,所以最左子正则式优先匹配成功,因此偶尔会错过最佳匹配结果;DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词(见item 4);
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。
我这里举一个例子来说明第3个影响。
例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA,则以正则式为导向,手里捏着正则式,眼睛看着文本,一个字符一个字符的吃,吃完 ‘perl’ 以后,跟第一个子正则式/perl/已经匹配上了,于是记录在案,往下再看,吃进一个 ‘m’,这下糟了,跟子式/perl/不匹配了,于是把m吐出来,向上汇报说成功匹配 ‘perl’,不再关心其他,也不尝试后面那个子正则式/perlman/,自然也就看不到那个更好的答案了。
如果是DFA,它是以文本为导向,手里捏着文本,眼睛看着正则式,一口一口的吃。吃到/p/,就在手里的 ‘p’ 上打一个钩,记上一笔,说这个字符已经匹配上了,然后往下吃。当看到 /perl/ 之后,DFA不会停,会尝试再吃一口。这时候,第一个子正则式已经山穷水尽了,没得吃了,于是就甩掉它,去吃第二个子正则式的/m/。这一吃好了,因为又匹配上了,于是接着往下吃。直到把正则式吃完,心满意足往上报告说成功匹配了 ‘perlman’。
由此可知,要让NFA正确工作,应该使用 /perlman|perl/ 模式。
通过以上例子,可以理解为什么NFA是最左子式匹配,而DFA是最长左子式匹配。实际上,如果仔细分析,关于NFA和DFA的不同之处,都可以找出道理。而明白这些道理,对于有效应用正则表达式是非常有意义的。
4. 理解greedy和lazy量词
由于日常遇到的正则表达式引擎全都是NFA,所以缺省都采用greedy量词。Greedy量词的意思不难理解,就是对于/.*/、/w+/这样的“重复n”次的模式,以贪婪方式进行,尽可能匹配更多字符,直到不得以罢手为止。
举一个例子,以 /<.*>/ 模式匹配 ‘<book> <title> Perl Hacks </title> </book>t’文本,匹配结果不是 ‘<book>’,而是 ‘<book> <title> Perl Hacks </title> </book>’。原因就在于NFA引擎以贪婪方式执行“重复n次”的命令。让我们来仔细分析一下这个过程。
条款3指出,NFA的模型是以正则式为导向,拿着正则式吃文本。在上面的例子里,当它拿着/.*/这个正则式去吃文本的时候,缺省情况下它就这么一路吃下去,即使碰到 ‘>’字符也不罢手——既然 /./ 是匹配任意字符, ‘>’ 当然也可以匹配!所以就尽管吃下去,直到吃完遇到结尾(包括t字符)也不觉得有什么不对。这个时候它突然发现,在正则表达式最后还有一个 />/,于是慌了神,知道吃多了,于是就开始一个字符一个字符的往回吐,直到吐出倒数第二个字符 ‘>’,完成了与正则式的匹配,才长舒一口气,向上汇报,匹配字符串从第一个字符 ‘<’ 开始,到倒数第二个字符 ‘>’结束,即‘<book> <title> Perl Hacks </title> </book>’。
Greedy量词的行为有时确实是用户所需要的,有时则不是。比如在这个例子里,用户可能实际上想得到的是 ‘book’ 串。怎么办呢?这时候lazy量词就派上用场了。把模式改为/<.*?>/就可以得到 ‘book’。这个加在 ‘*’号后面的 ‘?’ 把greedy量词行为变成lazy量词行为,从而由尽量多吃变为尽量少吃,只要吃到一个 ‘>’立刻停止。
问号在正则表达式里用途最广泛,这里是很重要的一个用途。
5. 理解backtracking
在条款4的基础上解释backtracking就很容易了。当NFA发现自己吃多了,一个一个往回吐,边吐边找匹配,这个过程叫做backtracking。由于存在这个过程,在NFA匹配过程中,特别是在编写不合理的正则式匹配过程中,文本被反复扫描,效率损失是不小的。明白这个道理,对于写出高效的正则表达式很有帮助。
从上面应该可以看出,由于java使用的是NFA的正则引擎,所以在处理长字符串的匹配时发生栈溢出是可以理解的,因为这种引擎支持回溯,而字符的匹配是通过栈来完成的回溯。
文本的内容毕竟有限,如果真的发生溢出了可以使用VM的-Xss参数来增加程序的栈空间,可以通过-Xss90M,来指定使用90M的栈空间,这样就基本上不会发生溢出了,除非真的有很大的文本,这个时候就没有好办法,因为-Xss指定的栈空间好像不能大于90多M,再大点的话虚拟机启动不了,就异常退出了,这个还没有明白为什么。
还有一个没有明白的问题:回溯时使用的栈,应该可以使用Stack对象吧,这样就可以将对象产生在堆空间上了,为什么不这样做,还是不能这样做?后面再研究一下代码看看
开始以为是文件太长,将文件减短后还是会有问题,觉得应该是java内置的正则的问题,网上Google了一下,遇到这个问题的人多了去了。
java内置的正则解析器有问题,不过可以绕过去。有两个较好用的库,这两个库都不会发生StackOverFlowerError(这里有点错误,使用jregex还是会发生溢出的)。
pattwo :http://www.javaregex.com
jregex :http://sourceforge.net/projects/freshmeat_jregex
另有一篇参考文档:
http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html
-----------------------------------------2009.5.25日凌晨更新---------------------
这两天觉得正则表达式在匹配时会溢出的问题还是没有搞清楚,所以就又google了一下,发现距离答案又近了一些。栈溢出并不是java的bug,这和正则表达式引擎的算法有关系。主要有两种正则引擎:DFA和NFA。
有一往篇文章介绍的挺好,这里拿过来用一下
引用
1. 了解正则表达式的历史
正则表达式萌芽于1940年代的神经生理学研究,由著名数学家Stephen Kleene第一个正式描述。具体地说,Kleene归纳了前述的神经生理学研究,在一篇题为《正则集代数》的论文中定义了“正则集”,并在其上定义了一个代数系统,并且引入了一种记号系统来描述正则集,这种记号系统被他称为“正则表达式”。在理论数学的圈子里被研究了几十年之后,1968年,后来发明了 UNIX系统的Ken Thompson第一个把正则表达式用于计算机领域,开发了qed和grep两个实用文本处理工具,取得了巨大成功。在此后十几年里,一大批一流计算机科学家和黑客对正则表达式进行了密集的研究和实践。在1980年代早期,UNIX运动的两个中心贝尔实验室和加州大学伯克利分校分别围绕grep工具对正则表达式引擎进行了研究和实现。与之同时,编译器“龙书”的作者Alfred Aho开发了Egrep工具,大大扩展和增强了正则表达式的功能。此后,他又与《C程序设计语言》的作者Brian Kernighan等三人一起发明了流行的awk文本编辑语言。到了1986年,正则表达式迎来了一次飞跃。先是C语言顶级黑客Henry Spencer以源代码形式发布了一个用C语言写成的正则表达式程序库(当时还不叫open source),从而把正则表达式的奥妙带入寻常百姓家,然后是技术怪杰Larry Wall横空出世,发布了Perl语言的第一个版本。自那以后,Perl一直是正则表达式的旗手,可以说,今天正则表达式的标准和地位是由Perl塑造的。Perl 5.x发布以后,正则表达式进入了稳定成熟期,其强大能力已经征服了几乎所有主流语言平台,成为每个专业开发者都必须掌握的基本工具。
2. 掌握一门正则表达式语言
使用正则表达式有两种方法,一种是通过程序库,另一种是通过内置了正则表达式引擎的语言本身。前者的代表是 Java、.NET、C/C++、Python,后者的代表则是Perl、Ruby、JavaScript和一些新兴语言,如Groovy等。如果学习正则表达式的目标仅仅是应付日常应用,则通过程序库使用就可以。但只有掌握一门正则表达式语言,才能够将正则表达式变成编程的直觉本能,达到较高的水准。不但如此,正则表达式语言也能够在实践中提供更高的开发和执行效率。因此,有心者应当掌握一门正则表达式语言。
3. 理解DFA和NFA
正则表达式引擎分成两类,一类称为DFA(确定性有穷自动机),另一类称为NFA(非确定性有穷自动机)。两类引擎要顺利工作,都必须有一个正则式和一个文本串,一个捏在手里,一个吃下去。DFA捏着文本串去比较正则式,看到一个子正则式,就把可能的匹配串全标注出来,然后再看正则式的下一个部分,根据新的匹配结果更新标注。而NFA是捏着正则式去比文本,吃掉一个字符,就把它跟正则式比较,匹配就记下来:“某年某月某日在某处匹配上了!”,然后接着往下干。一旦不匹配,就把刚吃的这个字符吐出来,一个个的吐,直到回到上一次匹配的地方。
DFA与NFA机制上的不同带来5个影响:
1. DFA 对于文本串里的每一个字符只需扫描一次,比较快,但特性较少;NFA要翻来覆去吃字符、吐字符,速度慢,但是特性丰富,所以反而应用广泛,当今主要的正则表达式引擎,如Perl、Ruby、Python的re模块、Java和.NET的regex库,都是NFA的。
2. 只有NFA才支持lazy和backreference等特性;
3. NFA急于邀功请赏,所以最左子正则式优先匹配成功,因此偶尔会错过最佳匹配结果;DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词(见item 4);
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。
我这里举一个例子来说明第3个影响。
例如用正则式/perl|perlman/来匹配文本 ‘perlman book’。如果是NFA,则以正则式为导向,手里捏着正则式,眼睛看着文本,一个字符一个字符的吃,吃完 ‘perl’ 以后,跟第一个子正则式/perl/已经匹配上了,于是记录在案,往下再看,吃进一个 ‘m’,这下糟了,跟子式/perl/不匹配了,于是把m吐出来,向上汇报说成功匹配 ‘perl’,不再关心其他,也不尝试后面那个子正则式/perlman/,自然也就看不到那个更好的答案了。
如果是DFA,它是以文本为导向,手里捏着文本,眼睛看着正则式,一口一口的吃。吃到/p/,就在手里的 ‘p’ 上打一个钩,记上一笔,说这个字符已经匹配上了,然后往下吃。当看到 /perl/ 之后,DFA不会停,会尝试再吃一口。这时候,第一个子正则式已经山穷水尽了,没得吃了,于是就甩掉它,去吃第二个子正则式的/m/。这一吃好了,因为又匹配上了,于是接着往下吃。直到把正则式吃完,心满意足往上报告说成功匹配了 ‘perlman’。
由此可知,要让NFA正确工作,应该使用 /perlman|perl/ 模式。
通过以上例子,可以理解为什么NFA是最左子式匹配,而DFA是最长左子式匹配。实际上,如果仔细分析,关于NFA和DFA的不同之处,都可以找出道理。而明白这些道理,对于有效应用正则表达式是非常有意义的。
4. 理解greedy和lazy量词
由于日常遇到的正则表达式引擎全都是NFA,所以缺省都采用greedy量词。Greedy量词的意思不难理解,就是对于/.*/、/w+/这样的“重复n”次的模式,以贪婪方式进行,尽可能匹配更多字符,直到不得以罢手为止。
举一个例子,以 /<.*>/ 模式匹配 ‘<book> <title> Perl Hacks </title> </book>t’文本,匹配结果不是 ‘<book>’,而是 ‘<book> <title> Perl Hacks </title> </book>’。原因就在于NFA引擎以贪婪方式执行“重复n次”的命令。让我们来仔细分析一下这个过程。
条款3指出,NFA的模型是以正则式为导向,拿着正则式吃文本。在上面的例子里,当它拿着/.*/这个正则式去吃文本的时候,缺省情况下它就这么一路吃下去,即使碰到 ‘>’字符也不罢手——既然 /./ 是匹配任意字符, ‘>’ 当然也可以匹配!所以就尽管吃下去,直到吃完遇到结尾(包括t字符)也不觉得有什么不对。这个时候它突然发现,在正则表达式最后还有一个 />/,于是慌了神,知道吃多了,于是就开始一个字符一个字符的往回吐,直到吐出倒数第二个字符 ‘>’,完成了与正则式的匹配,才长舒一口气,向上汇报,匹配字符串从第一个字符 ‘<’ 开始,到倒数第二个字符 ‘>’结束,即‘<book> <title> Perl Hacks </title> </book>’。
Greedy量词的行为有时确实是用户所需要的,有时则不是。比如在这个例子里,用户可能实际上想得到的是 ‘book’ 串。怎么办呢?这时候lazy量词就派上用场了。把模式改为/<.*?>/就可以得到 ‘book’。这个加在 ‘*’号后面的 ‘?’ 把greedy量词行为变成lazy量词行为,从而由尽量多吃变为尽量少吃,只要吃到一个 ‘>’立刻停止。
问号在正则表达式里用途最广泛,这里是很重要的一个用途。
5. 理解backtracking
在条款4的基础上解释backtracking就很容易了。当NFA发现自己吃多了,一个一个往回吐,边吐边找匹配,这个过程叫做backtracking。由于存在这个过程,在NFA匹配过程中,特别是在编写不合理的正则式匹配过程中,文本被反复扫描,效率损失是不小的。明白这个道理,对于写出高效的正则表达式很有帮助。
从上面应该可以看出,由于java使用的是NFA的正则引擎,所以在处理长字符串的匹配时发生栈溢出是可以理解的,因为这种引擎支持回溯,而字符的匹配是通过栈来完成的回溯。
文本的内容毕竟有限,如果真的发生溢出了可以使用VM的-Xss参数来增加程序的栈空间,可以通过-Xss90M,来指定使用90M的栈空间,这样就基本上不会发生溢出了,除非真的有很大的文本,这个时候就没有好办法,因为-Xss指定的栈空间好像不能大于90多M,再大点的话虚拟机启动不了,就异常退出了,这个还没有明白为什么。
还有一个没有明白的问题:回溯时使用的栈,应该可以使用Stack对象吧,这样就可以将对象产生在堆空间上了,为什么不这样做,还是不能这样做?后面再研究一下代码看看
发表评论
-
转:idea点用C盘空间解决办法
2015-03-30 17:02 1442原文:http://my.oschina.net/ulyn ... -
转:Java安全模型
2015-02-26 13:50 786原文地址:http://www.ibm.com/develo ... -
序列化对象大小计算
2013-01-21 16:45 0import java.io.ByteArrayOutput ... -
wait死了,今天真是郁闷
2012-09-13 22:21 1003wait should always be in syn ... -
获取所有淘金币全额兑换商品
2012-08-08 16:36 1727找淘金币全额兑换的商品是不是很麻烦,点来点去每个类目找一下,等 ... -
gc 日志格式
2011-03-04 14:58 0Here's an example GC log file w ... -
使用Oauth向新浪微博发消息
2011-02-13 00:16 4742最近看了一下新浪围脖 ... -
classloader
2011-02-12 16:57 0/** * classloader single * ... -
mail
2011-02-12 16:28 0package org.mail.core; impor ... -
Mina原理草图及注释
2011-01-18 23:00 5920今天先画一个草图备忘,明天再注释一下。 上图 ... -
Reactor模式,或者叫反应器模式
2010-11-29 22:29 69381Reactor这个词译成汉语还真没有什么合适的,很多地方叫反应 ... -
eclipse“随变”,随机变换eclipse启动界面
2010-06-02 20:17 4304对eclipse的启动界面审美疲劳了,手贱,想换掉它,趁老婆不 ... -
java编译时生成调试信息选项详解(javac -g)
2010-05-30 02:31 6259引子 先说一下为什么 ... -
文件Copy,什么方式才最快呀~~
2010-05-17 23:31 1513闲逛CSDN,发现有人找文件Copy的方法,顺手解答了一下,有 ... -
Eclipse调试常用技巧
2010-04-06 01:43 25716本文写给那些像几年前的我一样刚刚走出校门,及一些未使用过这些高 ... -
log4j真的比JDK logger快吗?
2009-09-20 23:58 4206这里不想比较这两个日 ... -
String.format函数使用方法介绍
2009-08-09 10:52 2034转自:http://blog.csdn.net/andycpp ... -
在程序中实现对java源文件编译的3种方法
2009-07-18 18:34 2696一般情况下对java源文件的编译均是在代码完成后使用javac ... -
Java读带有BOM的UTF-8文件乱码原因及解决方法
2009-05-28 01:31 20256最近在处理文件时发现了同样类型的文件使用的编码可能是不同的。所 ... -
Java 正则表达式处理选项及SQL注释删除
2009-05-09 23:58 5891常 量 等效的嵌入标志表达式 ...
相关推荐
Java正则表达式Java正则表达式Java正则表达式Java正则表达式
java正则表达式java正则表达式java正则表达式java正则表达式java正则表达式java正则表达式
java正则与程序优化java正则与程序优化java正则与程序优化
java,正则表达式,详解,java正则表达式,PDF
JAVA正则表达式JAVA正则表达式JAVA正则表达式
本文写作时,一个包含了用正则表达式进行文本处理的Java规范需求(Specification Request)已经得到认可,你可以期待在JDK的下一版本中看到它。 然而,如果现在就需要使用正则表达式,又该怎么办呢?你可以从Apache...
java正则表达式.pdfjava正则表达式.pdfjava正则表达式.pdfjava正则表达式.pdfjava正则表达式.pdf
java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解
java使用正则表达式进行校验验证,主要使用了Pattern和Matcher类,直接main方法运行就可以,亲测有效
Java正则表达式 Java 正则表达式 图片版 携带方便,查阅方便!~
正则表达式之道.doc 正则表达式中的特殊字符.doc Java正则表达式详解.doc 正则表达式.ppt JAVA正则表达式--Pattern和Matcher.doc 例子
Java正则表达式介绍和练习Java正则表达式介绍和练习Java正则表达式介绍和练习
java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解java正则表达式详解
java正则表达式验证IP地址
java正则实现解析算术表达式 (仅限+-*/和括号)
java 正则匹配所有 {},并取出所有符合的字符串。该项目为普通java项目
"yyyyMM","yyyyMMdd","yyyyMMdd HH:mm:ss", "yyyy-MM","yyyy-MM-dd","yyyy-MM-dd HH:mm:ss" "yyyy.MM","yyyy.MM.dd","yyyy.MM.dd HH:mm:ss" "yyyy/MM","yyyy/MM/dd","yyyy/MM/dd HH:mm:ss" "yyyy_MM","yyyy_MM_dd",...
java正则表达式总结,java正则表达式入门的好材料
Java正则表达式应用总结
包括后台java正则验证及前台js验证 请输入一个数字(精确到小数点后两位): fdsa54325.54 fdsa54325.54 false 请输入一个数字(金额不超过万亿精确到小数点后两位) 请输入一个数字(精确到小数点后两位): ...