快捷導(dǎo)航

淺談?wù)齽t表達(dá)式回溯陷阱

更新時(shí)間：2023年11月27日 09:35:34 作者：JebLin02

日常編程經(jīng)常會(huì)用到正則表達(dá)式,躲不開這個(gè)陷阱,本文主要介紹了淺談?wù)齽t表達(dá)式回溯陷阱,具有一定的參考價(jià)值,感興趣的可以了解一下

一、匹配場景

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

text = "I am a student"

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

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

空格用 \s 表示

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

那正則就是

^([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

二、性能測試

regex101: build, test, and debug regex.

icon-default.png?t=N7T8

句子改成：I am a good good student

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

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

I am a good good student？

83408 step，耗時(shí)5.4ms

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

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

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

2、NFA的回溯

字符串：abc

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

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

3、簡易例子分析

表達(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