一、匹配場(chǎng)景

判斷一個(gè)句子是不是正規(guī)英文句子

text = "I am a student"

一個(gè)正常的英文句子如上，英文單詞  + 空格隔開

英文單詞 = 多個(gè)英文字符 [a-zA-Z] 

空格用 \s 表示

那么一個(gè)句子就是單詞 + 空格（一個(gè)或者多個(gè)，最后那個(gè)單詞是0個(gè)）（可能有多個(gè)單詞+空格）+ 最后一個(gè)句號(hào) .

那正則就是 

^([a-zA-Z]+(\s)*)+$

 JAVA代碼

public static void main(String[] args) {
        String text = "I am a good student";
        String regex = "^([a-zA-Z]+(\\s)*)+$";

        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(text);
        System.out.println(matcher.find());
        System.out.println(matcher.group(0));
    }

輸出結(jié)果： 

true
I am a good student

二、性能測(cè)試

regex101: build, test, and debug regex.

句子改成：I am a good good student

匹配成功了。39 step，耗時(shí)0.1ms，

但是假如把句子拉長(zhǎng)點(diǎn)，最后加上一個(gè)問(wèn)號(hào) ？

I am a good good student？

83408 step，耗時(shí)5.4ms

假如把句子再拉長(zhǎng)點(diǎn)，那么直接就干爆CPU，耗時(shí)指數(shù)增長(zhǎng)，

為啥會(huì)這樣呢？

三、正則的回溯陷阱

1、了解下NFA與DFA

• DFA (Deterministic finite automaton) 確定型有窮自動(dòng)機(jī)
• NFA (Non-deterministic finite automaton) 非確定型有窮自動(dòng)機(jī)

DFA ：遍歷text字符串，去和Pattern匹配

NFA：遍歷Pattern，去與text匹配

DFA（是電動(dòng)機(jī)） 和NFA（汽油機(jī)） 都有很長(zhǎng)的歷史，不過(guò)，正如汽油機(jī)一樣，NFA 的歷史更長(zhǎng)一些。也有些系統(tǒng)采用了混合引擎，它們會(huì)根據(jù)任務(wù)的不同選擇合適的引擎（甚至對(duì)同一表達(dá)式中的不同部分采用不同的引擎，以求得功能與速度之間的最佳平衡）。 ——《精通正則表達(dá)式》

絕大多數(shù)編程語(yǔ)言都選擇的引擎——NFA (非確定型有窮自動(dòng)機(jī)) 引擎

2、NFA的回溯

字符串 ：abc

表達(dá)式：a(d|b)c

注意這個(gè)位置回退！??！

3、簡(jiǎn)易例子分析

表達(dá)式 = ^(a*)+$
文本 = aaaaaaaaaaaaaaab

走了16w步，花了7.3ms

• 首先 (a*) 已經(jīng)匹配到 aaaaaaaaaaaaaaa 了，
•  (a*)+ 也匹配到 aaaaaaaaaaaaaaa ，
• 結(jié)束符$去匹配的時(shí)候，發(fā)現(xiàn)text不是結(jié)束，而是一個(gè)b
• 那吐出最后的a，變成 (aaaaaaaaaaaaaa) a ，沒匹配上，繼續(xù)吐

a*               a*
(aaaaaaaaaaaaa) (aa)

a*              a* a*
(aaaaaaaaaaaaa) (a)(a)


a*              a* 
(aaaaaaaaaaaa) (aaa)


a*              a* a*
(aaaaaaaaaaaa) (aa)(a)


a*              a* a* a*
(aaaaaaaaaaaa) (a)(a)(a)

--> 吐到最后
(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)

直接干爆CPU 

4、咋優(yōu)化?

1、對(duì)于  ^(a*)+$

直接把表達(dá)式

 ^(a*)+$

改成 ^(a*)$

把后面的 + 號(hào)去掉。

直接就是 5 Step，0.1ms

2、對(duì)于 ^([a-zA-Z]+(\s)*)+$

把后面的 + 號(hào)去掉。就不回溯了，

但是匹配不上，因?yàn)檎Z(yǔ)句有問(wèn)題，就是空格必須存在，但是最后的空格不存在

所以改成 ：^[a-zA-Z]+(\s[a-zA-Z]+)*$

遇到問(wèn)號(hào)也不回溯

去掉問(wèn)號(hào)也匹配上了

到此這篇關(guān)于淺談?wù)齽t表達(dá)式回溯陷阱的文章就介紹到這了,更多相關(guān)正則表達(dá)式回溯陷阱內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論