效能優化——慎重使用正則表達式

什麼是正則表達式？

正則表達式是電腦科學的一個概念，很多語言都實現了它。正則表達式使用一些特定的元
字元來檢索、匹配以及替換符合規則的字串。

構造正則表達式語法的元字元，由普通字元、標準字元、限定字元（量詞）、定位字元（邊
界字元）組成。詳情可見下圖：

正則表達式引擎

正則表達式是一個用正則符號寫出的公式，程式對這個公式進行語法分析，建立一個語法分
析樹，再根據這個分析樹結合正則表達式的引擎生成執行程式（這個執行程式我們把它稱作
狀態機，也叫狀態自動機），用於字元匹配。

而這裏的正則表達式引擎就是一套核心演算法，用於建立狀態機。

目前實現正則表達式引擎的方式有兩種：DFA 自動機（Deterministic Final Automata 確
定有限狀態自動機）和 NFA 自動機（Non deterministic Finite Automaton 非確定有限
狀態自動機）。

對比來看，構造 DFA 自動機的代價遠大於 NFA 自動機，但 DFA 自動機的執行效率高於
NFA 自動機。

假設一個字串的長度是 n，如果用 DFA 自動機作爲正則表達式引擎，則匹配的時間複雜
度爲 O(n)；如果用 NFA 自動機作爲正則表達式引擎，由於 NFA 自動機在匹配過程中存在
大量的