欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間：2023年11月27日 09:35:34   作者：JebLin02  
日常編程經(jīng)常會用到正則表達(dá)式,躲不開這個陷阱,本文主要介紹了淺談?wù)齽t表達(dá)式回溯陷阱,具有一定的參考價值,感興趣的可以了解一下

一、匹配場景

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

text = "I am a student"

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

英文單詞 = 多個英文字符 [a-zA-Z] 

空格用 \s 表示

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

那正則就是 

^([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，耗時0.1ms，

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

I am a good good student？

83408 step，耗時5.4ms

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

為啥會這樣呢？

三、正則的回溯陷阱

1、了解下NFA與DFA

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

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

NFA：遍歷Pattern，去與text匹配

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

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

2、NFA的回溯

字符串 ：abc

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

注意這個位置回退?。。?/strong>

3、簡易例子分析

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

走了16w步，花了7.3ms

  • 首先 (a*) 已經(jīng)匹配到 aaaaaaaaaaaaaaa 了，
  •  (a*)+ 也匹配到 aaaaaaaaaaaaaaa ，
  • 結(jié)束符$去匹配的時候，發(fā)現(xiàn)text不是結(jié)束，而是一個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、對于  ^(a*)+$

直接把表達(dá)式

 ^(a*)+$

改成 ^(a*)$

把后面的 + 號去掉。

直接就是 5 Step，0.1ms

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

把后面的 + 號去掉。就不回溯了，

但是匹配不上，因為語句有問題，就是空格必須存在，但是最后的空格不存在

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

遇到問號也不回溯

去掉問號也匹配上了

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

相關(guān)文章

最新評論