周末快到了，今天為大家送上一篇很有意思的小文章，具有提神醒腦之功效。作者是來自阿裡巴巴LAZADA産品技術部的申徒童鞋。
近期我在為Lazada賣家中心做一個自助注冊的項目，其中的shop name校驗規則較為複雜，要求：
1. 英文字母大小寫
2. 數字
3. 越南文
4. 一些特殊字元，如“&”，“-”，“_”等
看到這個要求的時候，自然而然地想到了正規表達式。于是就有了下面的表達式（寫的比較龊）：
在測試環境，這個表達式從功能上符合業務方的要求，就被釋出到了馬來西亞的線上環境。結果上線之後，發現線上機器時有發生CPU飙到100%的情況，導緻整個站點響應異常緩慢。通過dump線程trace，才發現線程全部卡在了這個正規表達式的校驗上：
一開始難以置信，一個正規表達式的比對過程怎麼可能引發CPU飚高呢？抱着懷疑的态度去查了資料才發現小小的正規表達式裡面竟然大有文章，平時寫起來都是淺嘗辄止，隻要能夠滿足功能需求，就認為達到目的了，完全忽略了它可能帶來的性能隐患。
引發這次血案的就是所謂的正則“回溯陷阱（Catastrophic Backtracking）”。下面詳細介紹下這個問題，以避免重蹈覆轍。
說起回溯陷阱，要先從正規表達式的引擎說起。正則引擎主要可以分為基本不同的兩大類：一種是DFA（确定型有窮自動機），另一種是NFA（不确定型有窮自動機）。簡單來講，NFA 對應的是正規表達式主導的比對，而 DFA 對應的是文本主導的比對。
DFA從比對文本入手，從左到右，每個字元不會比對兩次，它的時間複雜度是多項式的，是以通常情況下，它的速度更快，但支援的特性很少，不支援捕獲組、各種引用等等；而NFA則是從正規表達式入手，不斷讀入字元，嘗試是否比對目前正則，不比對則吐出字元重新嘗試，通常它的速度比較慢，最優時間複雜度為多項式的，最差情況為指數級的。但NFA支援更多的特性，因而絕大多數程式設計場景下（包括java，js），我們面對的是NFA。以下面的表達式和文本為例，
在NFA比對時候，是根據正規表達式來比對文本的，從t開始比對a，失敗，繼續，直到文本裡面的第一個t，接着比較o和e，失敗，正則回退到 t，繼續，直到文本裡面的第二個t，然後 o和文本裡面的o也比對，繼續，正規表達式後面有三個可選條件，依次比對，第一個失敗，接着二、三，直到比對。
而在DFA比對時候，采用的是用文本來比對正規表達式的方式，從a開始比對t，直到第一個t跟正則的t比對，但e跟o比對失敗，繼續，直到文本裡面的第二個 t 比對正則的t，接着o與o比對，n的時候發現正則裡面有三個可選比對，開始并行比對，直到文本中的g使得第一個可選條件不比對，繼續，直到最後比對。
可以看到，DFA比對過程中文本中的字元每一個隻比較了一次，沒有吐出的操作，應該是快于NFA的。另外，不管正規表達式怎麼寫，對于DFA而言，文本的比對過程是一緻的，都是對文本的字元依次從左到右進行比對，是以，DFA在比對過程中是跟正規表達式無關的，而 NFA 對于不同但效果相同的正規表達式，比對過程是完全不同的。
說完了引擎，我們再來看看到底什麼是回溯。對于下面這個表達式，相信大家很清楚它的意圖，
也就是說中間的b需要比對1~3次。那麼對于文本“abbbc”，按照第1部分NFA引擎的比對規則，其實是沒有發生回溯的，在表達式中的a比對完成之後，b恰好和文本中的3個b完整比對，之後是c發生比對，一氣呵成。如果我們把文本換成“abc”呢？無非就是少了一個字母b，卻發生了所謂的回溯。比對過程如下圖所示（橙色為比對，黃色為不比對），
1~2步應該都好了解，但是為什麼在第3步開始，雖然已經文本中已經有一個b比對了b{1,3}，後面還會拉着字母c跟b{1,3}做比較呢？這個就是我們下面将要提到的正則的貪婪特性，也就是說b{1,3}會竭盡所能的比對最多的字元。在這個地方我們先知道它一直要比對到撞上南牆為止。 在這種情況下，第3步發生不比對之後，整個比對流程并沒有走完，而是像棧一樣，将字元c吐出來，然後去用正規表達式中的c去和文本中的c進行比對。這樣就發生了一次回溯。
我們再來看一下究竟什麼是貪婪模式。
下面的幾個特殊字元相信大家都知道它們的用法：
i. ?: 告訴引擎比對前導字元0次或一次。事實上是表示前導字元是可選的。
ii. +: 告訴引擎比對前導字元1次或多次。
iii. *: 告訴引擎比對前導字元0次或多次。
iv. {min, max}: 告訴引擎比對前導字元min次到max次。min和max都是非負整數。如果有逗号而max被省略了，則表示max沒有限制；如果逗号和max都被省略了，則表示重複min次。
預設情況下，這個幾個特殊字元都是貪婪的，也就是說，它會根據前導字元去比對盡可能多的内容。這也就解釋了為什麼在第3部分的例子中，第3步以後的事情會發生了。
在以上字元後加上一個問号（？）則可以開啟懶惰模式，在該模式下，正則引擎盡可能少的重複比對字元，比對成功之後它會繼續比對剩餘的字元串。在上例中，如果将正則換為
則比對過程變成了下面這樣（橙色為比對，黃色為不比對），
由此可見，在非貪婪模式下，第2步正則中的b{1,3}?與文本b比對之後，接着去用c與文本中的c進行比對，而未發生回溯。
如果在以上四種表達式後加上一個加号（+），則會開啟獨占模式。同貪婪模式一樣，獨占模式一樣會比對最長。不過在獨占模式下，正規表達式盡可能長地去比對字元串，一旦比對不成功就會結束比對而不會回溯。我們以下面的表達式為例，
如果我們用文本"abbc"去比對上面的表達式，比對的過程如下圖所示（橙色為比對，黃色為不比對），
可以發現，在第2和第3步，b{1,3}+會将文本中的2個字母b都比對上，結果文本中隻剩下一個字母c。那麼在第4步時，正則中的b和文本中的c進行比對，當無法比對時，并不進行回溯，這時候整個文本就無法和正規表達式發生比對。如果将正規表達式中的加号（+）去掉，那麼這個文本整體就是比對的了。
把以上三種模式的表達式列出如下，
貪婪
懶惰
獨占
X?
X??
X?+
X*
X*?
X*+
X+
X+?
X++
X{n}
X{n}?
X{n}+
X{n,}
X{n,}?
X{n,}+
X{n,m}
X{n,m}?
X{n,m}+
現在再回過頭看看文章開頭的那個很長的正規表達式，其實簡化之後，就是一個形如
的表達式。該字元集大小約為250，而+号表示至少出現一次。按照上面說到的NFA引擎貪婪模式，在使用者輸入一個過長字元串進行比對時，一旦發生回溯，計算量将是巨大的。後來采用了獨占模式，CPU 100%的問題也得到了解決。
是以，在自己寫正規表達式的時候，一定不能大意，在實作功能的情況下，還要仔細考慮是否會帶來性能隐患。
關于正規表達式，你有哪些想要分享的特殊技能？歡迎在下面留言，一起交流探讨。
來源：【阿裡技術】微信公衆号
♥ 作者：明志健緻遠
♠ 出處：http://www.cnblogs.com/study-everyday/
♦ 本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
♣ 本部落格大多為學習筆記或讀書筆記，本文如對您有幫助，還請多推薦下此文，如有錯誤歡迎指正，互相學習，共同進步。