JAVA 正则表达式的溢出问题 及不完全解决方案。 (感谢Lancelot 在评论中给出的方法)

Exception in thread "main" java.lang.StackOverflowError
at java.lang.Character.codePointAt(Character.java:
2335)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:
3344)
at java.util.regex.Pattern$Branch.match(Pattern.java:
4114)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:
4168)
at java.util.regex.Pattern$LazyLoop.match(Pattern.java:
4357)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:
4227)
 at java.util.regex.Pattern$BranchConn.match(Pattern.java:
4078)
类似于以上异常,源自于正则匹配需要不断地递归字符串。当字符串递归超过800+,具体数字忘记了,就会出现堆栈溢出。
 我在实际应用的场景是,匹配一个网页寻求《div》《/div》 之间的内容。当div 之间字符达到了950的时候这时候产生了 类似以上的错误。
经过分析,和网友遇到的类似问题贴http://topic.csdn.net/u/20110303/10/6a7dce52-481b-430a-b442-98099e9a01c9.html
得出以下不完全正确的解析方案

在正则表达式匹配时对字符个数进行限制 如:"<div>(.*?|\n*|\r*)*</div> 变成了 <div>(.*?|\n*|\r*){0,700}</div> 这样达到了限制字符的作用。
但是当解析到此条目时速度仍然非常慢。

如果您有更好的解决方案请您联系我。

欢迎转帖。转帖请标注出处,以更好的和大家探讨解决问题。

——————————————————————————————————————
Lancelot 提出的正则<div[^>]*>([\s\S]*?)</div>  或<div>([\s\S]*?)</div>
由于没有分支条件,因此大大减少了正则匹配过程的回溯深度。因此成功解决了这一问题。
目前能和大家分享的是,如果遇到类似问题还需简化正则,减少分支条件等。
如果您有更好的方案欢迎您提出宝贵的建议。

posted on 2011-04-28 10:55 scorpio小蝎 阅读(4848) 评论(12)  编辑  收藏 所属分类: java

评论

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 10:59 scorpio小蝎

如果您有更好的解决方案,和遇到类似的问题请联系我  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 12:13 Lancelot

没见过你说的问题。
但是你写的正则实在太菜了,至少你的正则应该写成下面这样吧???
<div[^>]*>([\s\S]*?)</div>  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 12:18 Lancelot

简单分析了一下你的正则,你写的正则回朔次数太多,估计是这个原因才导致的堆溢出。  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 12:39 Peace

(?s)<div>(.*?)</div>
注:(?s)表示.匹配任意字符,包含回车,见 : http://fireinwind.iteye.com/blog/724978  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 13:59 Lancelot

@Peace
你说的这个"(?s)"是符合NFA引擎还是符合DFA引擎的???
拜托不要用方言好不好,这样通用性也太差了吧???
还有,你以为"(.*?)"能匹配换行符???

答疑解惑是好的,但是你也总不能用不规范,甚至是错误的东西来误导人家吧。  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 14:04 scorpio小蝎

@scorpio小蝎
非常感谢您的回复,我也参考了一些网上的资料。像您说的一样,是回溯太多的问题。那么怎样写正则能减少一些回溯呢?提高正则的效率。您能给我一些相关资料,或者参考不  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 14:04 scorpio小蝎

@Peace
谢谢您的回复  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 14:49 Lancelot

给一个你的数据标本。
高效的正则是需要量身定做的。
还有就是你可以用我之前发的正则试试,比你正则的回朔次数要少。  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 14:55 scorpio小蝎

@Lancelot
数据标本没有看到,可能是没法过来。 发我邮箱吧,谢谢。roymoro@gmail.com
另外我想知道您是如何分析回溯次数的。我想是否可以通过某种方法来限定回溯深度呢。
对于您的这个正则,我的div 比较特殊 并没有 属性字段(是否可以去掉[^>]*) , 您说的对深度的影响是不主要产生在或的分隔符产生的代价呢
<div[^>]*>([\s\S]*?)</div>
  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 15:06 scorpio小蝎

@Lancelot
直接解决了问题,非常感谢。
虽然这次是由于正则写的很菜的原因,但就与这次的问题,我想继续研究一下 正则 的 匹配机制,和如何才能写出高效的正则。 想请您给些这方面的建议和参考资料。 比如在这次就发现了,回溯到一定情况下会 发出异常这个严重的问题,基本上是由于 | 的分支太多,导致了回溯量的暴增  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 2011-04-28 15:09 Lancelot

@scorpio小蝎
刚才我的表述方式会引起歧义,我的本意是说:你应该把你需要处理的数据放一个标本出来。
"[^>]*"只是为了匹配div标签里的attribute的,如果没有,去掉就是了,如不去掉,每次匹配的时候会多增加一次回朔。
关于,回朔次数分析,你应该先去了解正则匹配的机制——正则是一个一个字符匹配的。你写的正则,会根据行数的不同,有不同的回朔次数,我写的正则,只会有950(对应:"当div 之间字符达到了950的时候这时候产生了 类似以上的错误")次回朔。  回复  更多评论   

# re: JAVA 正则表达式的溢出问题 及不完全解决方案。 (感谢Lancelot 在评论中给出的方法) 2011-04-28 15:14 scorpio小蝎

@Lancelot
了解了,非常感谢。以后有问题向您请教  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜