java正则式简介（2）

正则式解析算法

•      NFA(不确定的有穷自动机):时间复杂度O(|N|*|x|)，|N|表示NFA的状态数， |x|表示匹配串的长度。

•      DFA (确定的有穷自动机):时间复杂度O(nlogn) ,n是DFA的状态数。速度明显比NFA要高。

•      避免使用类似(a|b)*a(a|b)(a|b)…(a|b),包含了n-1个 (a|b)的正则表达式。为什么？

正则式的强大工具： Jflex

 

正则式优化

•      减少回退次数
java.util.regex包使用NFA.正由于使用了这个算法，对于某些正则式性能会比较差，因为，NFA对于每个节点状态有多个出口状态，有可能利用回退策略尝试其他节点状态。
考虑下面的例子：正则表达式是“sc（ored|ared|oring）x”，输入字符串是“scared”。

•               优化：例如将“（abcd|abef）”替换为“ab（cd|ef）”。

•      Pattern.compile()编译，代替直接使用Pattern.matches()。

•      通过调用reset（）方法对不同的输入字符串重复使用Matcher对象

•      考虑选择的顺序，要将比较常用的选择项放在前面.例如，如果X比Y使用频率高，则”w(X|Y)”比”w(Y|X)”要好得多。

•      获取每次使用引起小损失的分组。如果你实际并不需要获取一个分组内的文本，那么就使用非捕获分组。例如使用“(?:X)”代替“（X）”。

•