欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 后台管理


新闻资讯

MENU

软件开发知识

Java 正则表达式 Sta CAD加密 ckOverflowError 问题及其优化

点击: 次  来源:宝鼎软件 时间:2017-09-10

原文出处: xrzs

正则可以看做一门 DSL,但它却应用极其遍及,可以轻松办理许多场景下的字符串匹配、筛选问题。同时呢有句老话:

“ 假如你有一个问题,用正则表达式办理,那么你此刻就有两个问题了。”

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

本日我们就来聊聊 Java 正则表达式 StackOverflowError 的问题及其一些优化点。

1、问题

最近,有同事发明一段正则在当地怎么跑都没问题,可是放到 Hadoop 集群上总会时不时的抛 StackOverflowError 。

代码我先简化下:

package java8test;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test {

	public static void main(String[] args) {

		final String TEST_REGEX = "([=+]|[\\s]|[\\p{P}]|[A-Za-z0-9]|[\u4E00-\u9FA5])+";
		StringBuilder line = new StringBuilder();
		System.out.println("++++++++++++++++++++++++++++++");
		for (int i = 0; i < 10; i++) {
			line.append(
					"http://hh.ooxx.com/ershoufang/?PGTID=14366988648680=+.7342327926307917&ClickID=1&key=%2525u7261%2525u4E39%2525u5BCC%2525u8D35%2525u82B1%2525u56ED&sourcetype=1_5");
			line.append(
					"http://wiki.corp.com/index.php?title=Track%E6%A0%87%E5%87%86%E6%97%A5%E5%BF%97Hive%E8%A1%A8-%E5%8D%B3%E6%B8%85%E6%B4%97%E5%90%8E%E7%9A%84%E6%97%A5%E5%BF%97");
			line.append(
					"http://www.baidu.com/s?ie=UTF-8&wd=58%cd%ac%b3%c7%b6%fe%ca%d6%b3%b5%b2%e2%ca%d4%ca%fd%be%dd&tn=11000003_hao_dg");
			line.append("http://cs.ooxx.com/yewu/?key=城&cmcskey=的设计费开始低&final=1&jump=1&specialtype=gls");
			line.append(
					"http%3A%2F%2Fcq.ooxx.com%2Fjob%2F%3Fkey%3D%25E7%25BD%2591%25E4%25B8%258A%25E5%2585%25BC%25E8%2581%258C%26cmcskey%3D%25E7%25BD%2591%25E4%25B8%258A%25E5%2585%25BC%25E8%2581%258C%26final%3D1%26jump%3D2%26specialtype%3Dgls%26canclequery%3Disbiz%253D0%26sourcetype%3D4");
		}
		line.append(" \001 11111111111111111111111111");
		Pattern p_a = null;
		try {
			p_a = Pattern.compile(TEST_REGEX);
			Matcher m_a = p_a.matcher(line);
			while (m_a.find()) {
				String a = m_a.group();
				System.out.println(a);
			}
		} catch (Exception e) {
			// TODO: handle exception
		}

		System.out.println("line size: " + line.length());
	}
}

执行之后的功效是:

++++++++++++++++++++++++++++++
Exception in thread "main" java.lang.StackOverflowError
	at java.util.regex.Pattern$Loop.match(Unknown Source)
	at java.util.regex.Pattern$GroupTail.match(Unknown Source)
	at java.util.regex.Pattern$BranchConn.match(Unknown Source)
	at java.util.regex.Pattern$CharProperty.match(Unknown Source)
......

起初这个问题是从集群上抛出来的,各人可以看到这个异常有两个特点:

(1)不行用 Exception 捕捉,因为 Error 直接担任自 Throwable 而非 Exception,所以纵然你要捕捉也该当捕捉 Error。

(2)别的一点是各人可以看到抛出的错误并没有指明行号,当这段代码混在一个数百行的东西类,有数十条雷同的正则的时候,无疑给定位问题带来了难度,这就需要我们能有必然的单位测试本领。

注:

(1)假如你的情况没有抛出上述错误,实验调大 for 轮回的次数可能指定 jvm 参数:-Xss1k

(2)假如你还不大白 StackOverflowError 是什么寄义,可以参考上一篇文章:JVM 运行时数据区简介

2、问题阐明

正则表达式引擎分成两类,一类称为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量词;

5. NFA大概会陷入递归挪用的陷阱而表示得机能极差。