正則表達式與優化
- 2020 年 1 月 21 日
- 筆記
整體已整理成思維導圖：
1. 元字符
1.1 普通字符
字母[a-zA-Z]，數字[0-9]，下劃線[_]，漢字。標點符號等
1.2 標準字符
- 能夠與「多種普通字符」匹配的簡單表達式
- 比如：d、w、s等
1.3 限定字符
- 用於表示匹配的字符數量
- 比如：*、+、?、{n}等
1.4 定位字符
- 「零寬」，標記符合某種條件的位置
- 比如：$,^等。
2.引擎
2.1 DFA自動機
- Deterministic Final Automata 確定有限狀態自動機
- 從匹配文本入手，從左到右，每個字符不會匹配兩次
2.2 NFA自動機
- Non Deterministic Final Automata 非確定有限狀態自動機
- 從正則表達式入手，不斷讀入字符，嘗試是否匹配當前正則，不匹配則吐出字符重新嘗試
2.2.1 NFA自動機的回溯
用 NFA 自動機實現的比較複雜的正則表達式，在匹配過程中經常會引起回溯問題。大量的回溯會長時間地佔用 CPU，從而帶來系統性能開銷。
下面以如下為例：
// 待匹配字符串 text = "abbc"; // 正則表達式 regex = "ab{1,3}c";
NFA 自動機對其解析如下：
- 第一步，讀取正則表達式第一個匹配符
a和字符串第一個字符a進行比較，a對a，匹配。 - 第二步，讀取正則表達式第二個匹配符
b{1,3}和字符串的第二個字符b進行比較，匹配。 - 第三步，因為
b{1,3}表示 1-3 個 b 字符串，NFA 自動機又具有貪婪特性，所以此時不會繼續讀取正則表達式的下一個匹配符，而是依舊使用b{1,3}和字符串的第三個字符b進行比較，結果還是匹配。 - 第四步，繼續使用
b{1,3}和字符串的第四個字符c進行比較，發現不匹配了，此時就會發生回溯，已經讀取的字符串第四個字符c將被吐出去，指針回到第三個字符 b 的位置。 - 第五步， 程序會讀取正則表達式的下一個匹配符
c，和字符串中的第四個字符c進行比較，結果匹配，結束。
2.3不同
- 構造DFA自動機的代價遠大於NFA,但DFA自動機的執行效率高於NFA自動機
- 假設一個字符串的長度是 n，如果用 DFA 自動機作為正則表達式引擎，則匹配的時間複雜度為 O(n)；
- 如果用 NFA 自動機作為正則表達式引擎，由於 NFA 自動機在匹配過程中存在大量的分支和回溯，假設 NFA 的狀態數為 s，則該匹配算法的時間複雜度為 O（ns）。
- NFA自動機的優勢是支持更多功能。如捕獲group、環視、佔有優先量詞等高級功能。
3. 匹配模式
3.1 貪婪模式（Greedy）
在數量匹配中，如果單獨使用 +、 ? 、* 或{min,max} 等量詞，正則表達式會匹配儘可能多的內容
3.2 懶惰模式（Reluctant）
- 正則表達式會儘可能少地重複匹配字符。如果匹配成功，它會繼續匹配剩餘的字符串。
- NFA 自動機首先選擇最小的匹配範圍
匹配解析
對於如下實例：
// 待匹配字符串 text = "abbc"; // 正則表達式 regex = "ab{1,3}?c";
在網上搜到一篇[《藏在正則表達式里的陷阱》，裏面說懶惰模式也會有回溯，具體如下：
- 正則表達式的第一個操作符
a與 字符串第一個字符 a 匹配，匹配成。 - 正則表達式的第二個操作符
b{1,3}?和 字符串第二個字符 b 匹配，匹配成功。 - 因為最小匹配原則，所以拿正則表達式第三個操作符
c與字符串第三個字符b匹配，發現不匹配。 - 此時回溯回去，拿正則表達式第二個操作符
b{1,3}?和字符串第三個字符b匹配，匹配成功。 - 於是再拿正則表達式第三個操作符
c與字符串第四個字符c匹配，匹配成功。於是結束。
詢問《Java性能調優實戰》專欄的老師被告知與貪婪模式的區別在於它不會使用b{1,3}與c匹配，在匹配完成abb之後，會使用regex中的c匹配text中的c。
3.3 獨佔模式（Possessive）
- 同貪婪模式一樣，獨佔模式一樣會最大限度地匹配更多內容；
- 不同的是，在獨佔模式下，匹配失敗就會結束匹配，不會發生回溯問題。
4. 優化
4.1 少用貪婪模式，多用獨佔模式
貪婪模式會引起回溯問題，可用獨佔模式避免
4.2 減少分支選擇
分支選擇類型「(X|Y|Z)」的表達式會降低性能，盡量減少使用。
4.2.1 分支選擇優化
- 比較常用的選擇項放在前面，使它們可以較快地被匹配到
- 嘗試提取共用模式。例如，將「(abcd|abef)」替換為「ab(cd|ef)」，後者匹配速度較快，因為 NFA 自動機會嘗試匹配 ab，如果沒有找到，就不會再嘗試任何選項；
- 若是簡單的分支選擇類型，可以用三次index代替「(X|Y|Z)」，前者效率比後者高出一些。index即String中的indexof方法。
4.3 減少捕獲嵌套
- 捕獲組是指把正則表達式中，子表達式匹配的內容保存到以數字編號或顯式命名的數組中，方便後面引用。一般一個
()就是一個捕獲組，捕獲組可以進行嵌套。 - 非捕獲組則是指參與匹配卻不進行分組編號的捕獲組，其表達式一般由
（?:exp）組成。 - 在正則表達式中，每個捕獲組都有一個編號，編號 0 代表整個匹配到的內容。
public static void main( String[] args ){ String text = "<input high="20" weight="70">test</input>"; // reg有三個捕獲組：(<input.*?>)、(.*?)、(</input>) String reg="(<input.*?>)(.*?)(</input>)"; // regOfNot有兩個非捕獲組：(?:<input.*?>)和(?:</input>)，一個捕獲組：(.*?) String regOfNot="(?:<input.*?>)(.*?)(?:</input>)"; Pattern p = Pattern.compile(reg); Matcher m = p.matcher(text); while(m.find()) { // group用來提取()分組截獲的字符串 System.out.println(m.group(0));// 整個匹配到的內容 System.out.println(m.group(1));//(<input.*?>) System.out.println(m.group(2));//(.*?) System.out.println(m.group(3));//(</input>) } }
最後推薦個可以檢查寫的正則表達式和對應的字符串匹配時會不會有問題的網站： Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript 。
