正則表達式是如何實現查找匹配的婶恼？
1，正則表達式的使用
2畅涂，正則表達式匹配搜索算法
3港华，正則表達式引擎:DFA和NFA
4，正則表達式的性能與優(yōu)化
1午衰，正則表達式的使用
正則表達式（Regular Expression 簡寫regex）立宜，是一種字符串匹配的模式（pattern），用來匹配搜索一段已知字符串中是否含有自己需要的子字符串苇经，
初次接觸正則表達時會覺得很深奧難寫赘理，這么多符號怎么記呢。其實當你通過幾個實際例子應用之后就會覺得也沒那么難扇单。
比如：
1.給你一個字符串,把字符串里面的鏈接商模、數字、電話等顯示不同的顏色蜘澜；
2.給你一個包含自定義表情的文字施流，找出里面的表情，替換成本地的表情圖片鄙信；
3.根據用戶的輸入內容瞪醋，判斷是否是微信號、手機號装诡、郵箱银受、純數字等；
而正則的應用也不僅僅局限于業(yè)務代碼中的字符串匹配鸦采，編輯器的查找替換宾巍，grep查找命令，vim編輯查找等都有用到渔伯。
所以顶霞，學習正則表達式并不是我們照著正則規(guī)則可以實現業(yè)務邏輯就夠了，最好還要能知其所以然锣吼。
2选浑，正則表達式匹配搜索算法
說到字符串匹配算法，常見有樸素字符串匹配算法玄叠，KMP算法古徒，有限自動機算法（Finite Automation）等。而正則表達式用到的就是有限自動機算法读恃。
有限狀態(tài)機（finite-state machine,FSM）又稱有限狀態(tài)自動機隧膘，簡稱狀態(tài)機崎苗，是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉移和動作等行為的數學模型。有些地方也叫“自動機”舀寓，指的都是同一個東西胆数。
FSM常用狀態(tài)轉移圖來表示，下圖就是一個狀態(tài)轉移圖：
比如我今年18歲互墓，我現在處于18歲的狀態(tài)必尼，如果時間過了一年，我就變成19歲的狀態(tài)了篡撵，再過一年就20了判莉。當然我20歲時時光倒流2年我又可以回到18歲的狀態(tài)。
每個圈代表一個節(jié)點表示一種狀態(tài)育谬，每條有向邊表示一個狀態(tài)到另一個狀態(tài)的轉移條件券盅。上圖中狀態(tài)是我的年齡，邊表示時間正向或者逆向流逝膛檀。
所以通過邊上條件的轉移我們可以從一個狀態(tài)轉移到另一個狀態(tài)锰镀，如果我們把要匹配的字符串的首字母和尾字母作為起始態(tài)和終止態(tài)，當從起始態(tài)可以順利的走到終止態(tài)是不是就表示匹配成功了呢咖刃？
沒錯泳炉，就是這樣的。
舉個栗子：
給定正則表達式a(bb)+a嚎杨，其中+表示匹配前面的子表達式一次或多次花鹅，那么該正則表達式對應的FSM狀態(tài)轉移圖如下：
假設輸入字符串是 abbbba。當機器讀取字符串的第一個字母 時 a枫浙，它處于起始狀態(tài)s 0刨肃。它跟隨 a 箭頭到達狀態(tài)s1。
當機器讀取字符串的其余部分時重復此過程:b,b,b,b 箩帚，最后是 a真友。 也就是s1->s2->s3->s2->s3->s4
所以字符串abbbba可以被這個正則所匹配。
該狀態(tài)機結束于最后一個狀態(tài)膏潮，這是一個匹配成功的狀態(tài)锻狗。
若狀態(tài)機結束于非匹配成功狀態(tài)满力，那么匹配失敗焕参。如果在運行過程中，沒有辦法到達其他狀態(tài)油额，那么狀態(tài)機提前結束叠纷。
3，正則表達式引擎:DFA和NFA
上面例子的狀態(tài)機中潦嘶，任何狀態(tài)每個可能的輸入字符涩嚣，最多只會讓它轉到一個新的狀態(tài)，也就是說新狀態(tài)是確定性的，所以上述狀態(tài)機被稱為：確定性有限狀態(tài)自動機(Deterministic finite automaton航厚，DFA)顷歌。
對于給定的任意一個狀態(tài)和輸入字符，DFA只會轉移到一個確定的狀態(tài)幔睬。并且DFA不允許出現沒有輸入字符的狀態(tài)轉移眯漩。
同樣，如果在一個狀態(tài)上輸入字符可能會轉移到多個不同的狀態(tài)麻顶，那么這種狀態(tài)機就是非確定性的赦抖，稱為：非確定型有窮自動機（Non deterministic Finite Automaton，NFA）
對于任意一個狀態(tài)和輸入字符辅肾，NFA所能轉移的狀態(tài)是一個非空集合队萤。
雖然是兩種不同形態(tài)的狀態(tài)機，但是DFA和NFA存在等價性矫钓，也就是說NFA和DFA是可以相互轉換的要尔。
比如上面例子的DFA，就可以轉換為下面的NFA：
或
由于NFA的非確定性新娜，在面對一個輸入的時候可能有多條可選的路徑盈电，所以在一條路徑走不通的情況下，需要回溯到選擇點去走另外一條路徑杯活。
但DFA不同匆帚，在每個狀態(tài)下，對每個輸入不會存在多條路徑旁钧，就不需要遞歸和回溯了吸重，可以一條路走到黑。DFA的匹復雜度只有O(n)歪今，但因為要遞歸和回溯NFA的匹配復雜度達到了O(n^2)嚎幸。
所以將引擎中的NFA轉化為DFA的場景更多。
但是寄猩，因為DFA支持的功能較少嫉晶，所以一般的業(yè)務代碼語言還是選擇了NFA引擎。
4田篇，正則表達式的性能與優(yōu)化
這兩種引擎有著極為不同的性能表現
其中一種用在許多語言的標準解釋器,用的是遞歸回溯算法(有Perl替废，Ruby，python等)泊柬。另外一種用在為數不多的地方（主要是awk椎镣，grep和Thompson NFA）。
實際業(yè)務代碼中的正則表達式遠比上面描述的要復雜的多兽赁，因為他們還要支持各種字符集状答，轉義序列冷守，有限重復，部分匹配提前和斷言等惊科，比如*,+,\d,[0-9],^,$,(?=)等等拍摇。
既然NFA會有遞歸回溯，那么就會有遞歸回溯的性能問題馆截，如果一個正則表達式特別模糊授翻，那么會帶來怎么樣的問題呢？
曾經國外有位工程師因為寫了十分模糊的正則導致cpu被打爆：
(?:(?:\"|'|\]|\}|\\|\d| (?:nan|infinity|true|false|null|undefined|symbol|math)|\|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
引起性能問題的關鍵部分是 .*(?:.*=.*)孙咪，這里可以先不管那個非捕獲組堪唐，將性能問題的正則看做 .*.*=.* 。
.* 表示貪婪匹配任意字符任意次翎蹈。這會帶來極大的回溯問題淮菠。一個簡單的x=x將會匹配23步才能查到。
如果輸入是 x=xxx荤堪，則需要 45步合陵。這不是線性的。這是一個圖表澄阳，顯示了從 x=x 到 x=xxxxxxxxxxxxxxxxxxxx（= 后的 20 個 x）的匹配拥知。在 = 之后有 20 個 x，引擎需要 555 步才能匹配碎赢！
更糟糕的是低剔，如果缺少 x=，那么字符串只有 20 個 x肮塞，引擎將需要 4,067 步才能找到不匹配的模式襟齿。
匹配次數會隨著x的數量上升而指數級的上升，十分可怕枕赵。
當然猜欺，我覺得一般業(yè)務也不會寫這種正則，但是寫正則的時候還是要有這種性能意識拷窜，盡量的縮小范圍少寫模糊匹配开皿，比如能確定是數字就不要用*匹配，越精確越好篮昧，模糊匹配赋荆、貪婪匹配、惰性匹配都會帶來回溯問題恋谭。注重性能問題才能避免發(fā)生這種悲劇糠睡。
參考 ：
1:https://swtch.com/~rsc/regexp/regexp1.html
2:https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
