Java正則表達式詳細解析

元字符

1. 正則表達式使用一些特定的元字符來檢索、匹配和替換符合規則的字符串
2. 元字符：普通字符、標準字符、限定字符（量詞）、定位字符（邊界字符）

正則表達式引擎

1. 正則表達式是一個用正則符號寫出來的公式

• 程序對正則表達式進行語法分析，建立語法分析樹
• 再根據語法分析樹結合
  正則表達式引擎生成執行程序（狀態機），用於字符匹配
• 正則表達式引擎是一套核心算法，用於建立狀態機
• 小結
• 正則表達式 => 語法分析樹
• 語法分析樹 + 正則表達引擎 => 狀態機 => 用於字符匹配

1. 目前實現正則表達式引擎的方式有兩種

• DFA自動機（Deterministic Finite Automaton，確定有限狀態自動機）
• NFA自動機（Nondeterministic Finite Automaton，非確定有限狀態自動機）

1. DFA自動機的構造代價遠大於NFA自動機，但DFA自動機的執行效率
   高於NFA自動機

• 假設一個字符串的長度為n，如果採用DFA自動機作為正則表達式引擎，則匹配的時間複雜度為O(n)
• 如果採用NFA自動機作為正則表達式引擎，NFA自動機在匹配過程中存在大量的分支和回溯，假設NFA的狀態數為s，
• 則匹配的時間複雜度為O(ns)

1. NFA自動機的優勢是支持更多高級功能，但都是基於子表達式獨立進行匹配

• 因此在編程語言裡，使用的正則表達式庫都是基於NFA自動機實現的

NFA自動機

匹配過程

1. NFA自動機會讀取正則表達式的每一個字符，拿去和目標字符串匹配
2. 匹配成功則換正則表達式的下一個字符，反之就繼續就和目標字符串的下一個字符進行匹配

text="aabcab"
regex="bc"

回溯

1. 用NFA自動機實現的比較複雜的正則表達式，在匹配過程中經常會引起回溯問題
2. 大量的回溯會長時間佔用CPU，從而帶來系統性能開銷

text="abbc"
regex="ab{1,3}c"

讀取正則表達式第一個匹配符a和字符串第一個字符a進行比較，a對a，匹配

讀取正則表達式第二個匹配符b{1,3}和字符串的第二個字符b進行比較，匹配，但b{1,3}表示1~3個字符，而NFA自動機具有貪婪特性，所以不會讀取正則表達式的下一個匹配符c

使用b{1,3}和字符串的第四個字符c進行比較，發現不匹配，此時就會發生回溯，已經讀取的字符串第四個字符c將被吐出去，指針回到第三個字符b的位置

發生回溯後，讀取正則表達式的下一個匹配符c，和字符串的第四個字符c進行比較，結果匹配

避免回溯

避免回溯的方法：使用懶惰模式和獨佔模式

貪婪模式（Greedy）

1. 在數量匹配中，如果單獨使用+、？、*、{min,max}等量詞，正則表達式會匹配儘可能多的內容
2. text="abbc" , regex="ab{1,3}c"，發生了一次匹配失敗，就會引起一次回溯
3. text="abbbc" , regex="ab{1,3}c"，匹配成功

懶惰模式（Reluctant）

1. 在懶惰模式下，正則表達式會儘可能少地重複匹配字符，如果匹配成功，會繼續匹配剩餘的字符串
2. 使用?開啟懶惰模式，text="abc" , regex="ab{1,3}?c"

• 匹配結果是"abc"，在該模式下NFA自動機首先選擇最小的匹配範圍，即匹配1個b字符，避免了回溯問題

獨佔模式（Possessive）

1. 和貪婪模式一樣，獨佔模式一樣會最大限度地匹配更多內容，但在匹配失敗時會結束匹配，不會發生回溯問題
2. 使用+開啟懶惰模式，text="abbc" , regex="ab{1,3}+bc"

• 結果是不匹配，結束匹配，不會發生回溯問題

代碼

match("ab{1,3}c", "abbc"); // abbc，貪婪模式，產生回溯
match("ab{1,3}c", "abbbc"); // abbbc，貪婪模式，不產生回溯
match("ab{1,3}?", "abbbb"); // ab，懶惰模式，不產生回溯
match("ab{1,3}+bc", "abbc"); // null，獨佔模式，不產生回溯
 

正則表達式的優化

1. 少用貪婪模式，多用獨佔模式（避免回溯）
2. 減少分支選擇，分支選擇類型"(X|Y|Z)"的正則表達式會降低性能，儘量減少使用，如果一定要使用

• 考慮選擇的順序，將比較常用的選擇放在前面，使它們可以較快地被匹配
• 提取共用模式，(abcd|abef) => ab(cd|ef)
• 如果是簡單的分支選擇類型，可以用三次index代替(X|Y|Z)

1. 減少捕獲嵌套

• 捕獲組：把正則表達式中，子表達式匹配的內容保存到以數字編號或顯式命名的數組中，一般一個()就是一個捕獲組
• 每個捕獲組都有一個編號，編號0代表整個匹配到的內容
• 非捕獲組：參與匹配卻不進行分組編號的捕獲組，其表達式一般由(?:exp)組成
• 減少不需要獲取的分組，可以提高正則表達式的性能

捕獲組

String text = "test";
String reg = "()(.*?)()";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while (m.find()) {
 System.out.println(m.group(0));// 整個匹配到的內容
 System.out.println(m.group(1));//()
 System.out.println(m.group(2));//(.*?)
 System.out.println(m.group(3));//()
 // 輸出：
 // test
 // 
 // test
 // 
}

非捕獲組

String text = "test";
String reg = "(?:)(.*?)(?:)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while (m.find()) {
 System.out.println(m.group(0));// 整個匹配到的內容
 System.out.println(m.group(1));//(.*?)
 // 輸出
 // test
 // test
}

小結

在做好性能測試的前提下，可以使用正則表達式，否則能不用就不用，避免造成更多的性能問題.

文章的話到這裡就結束了，希望大家在性能測試中，對正則表達式有自己的認識。今日的性能篇到此結束！

需要更多源碼視頻，面試題，Java技術書籍等學習資料的

可以關注我獲取哦！私信我“學習”；即可領取！

我是小架，我們下篇文章見！