1，什么是正則表達(dá)式

正則表達(dá)式使用一些特定的元字符來(lái)檢索、匹配以及替換符合規(guī)則的字符串。

構(gòu)造正則表達(dá)式語(yǔ)法的元字符，由普通字符、標(biāo)準(zhǔn)字符、限定字符（量詞）、定位字符（邊界字符）組成

普通字符

字母[a-zA-Z]、數(shù)字[0-9]、下劃線[-]、漢字、標(biāo)點(diǎn)符號(hào)等。比如，regex=[a-z]匹配從a到z，26個(gè)字母的任意一個(gè)。

標(biāo)準(zhǔn)字符

能夠與“多種普通字符”匹配的簡(jiǎn)單表達(dá)式。比如，\d、\w、\s等，匹配數(shù)字0到9的任意數(shù)字可以用普通字符實(shí)現(xiàn)regex=[0-9]，也可以用標(biāo)準(zhǔn)字符實(shí)現(xiàn)regex=\d。

限定字符（量詞）

用于表示匹配的字符數(shù)量。比如，*、+、？、[n}等，匹配任意1到3位的數(shù)字可以使用regex=\d{1,3}表示。

定位字符（邊界字符）

“零寬”，標(biāo)記匹配符合某種條件的位置。比如，$、^等字符，匹配以Hello開頭的字符串可以使用regex=^Hello表示。

2. 正則表達(dá)式引擎

正則表達(dá)式是一個(gè)用正則符號(hào)寫出的公式，程序?qū)@個(gè)公式進(jìn)行語(yǔ)法分析，建立一個(gè)語(yǔ)法分析樹，再根據(jù)這個(gè)分析樹結(jié)合正則表達(dá)式的引擎生成執(zhí)行程序（這個(gè)執(zhí)行程序我們把它稱作狀態(tài)機(jī)，也叫狀態(tài)自動(dòng)機(jī)），用于字符匹配。

而這里的正則表達(dá)式引擎就是一套核心算法，用于建立狀態(tài)機(jī)。

目前實(shí)現(xiàn)正則表達(dá)式引擎的方式有兩種：DFA 自動(dòng)機(jī)（Deterministic Final Automata 確定有限狀態(tài)自動(dòng)機(jī)）和 NFA 自動(dòng)機(jī)（Non deterministic Finite Automaton 非確定有限狀態(tài)自動(dòng)機(jī)）。

對(duì)比來(lái)看，構(gòu)造 DFA 自動(dòng)機(jī)的代價(jià)遠(yuǎn)大于 NFA 自動(dòng)機(jī)，但 DFA 自動(dòng)機(jī)的執(zhí)行效率高于NFA 自動(dòng)機(jī)。

假設(shè)一個(gè)字符串的長(zhǎng)度是 n，如果用 DFA 自動(dòng)機(jī)作為正則表達(dá)式引擎，則匹配的時(shí)間復(fù)雜度為 O(n)；如果用 NFA 自動(dòng)機(jī)作為正則表達(dá)式引擎，由于 NFA 自動(dòng)機(jī)在匹配過(guò)程中存在大量的分支和回溯，假設(shè) NFA 的狀態(tài)數(shù)為 s，則該匹配算法的時(shí)間復(fù)雜度為 O（ns）。

NFA 自動(dòng)機(jī)的優(yōu)勢(shì)是支持更多功能。例如，捕獲 group、環(huán)視、占有優(yōu)先量詞等高級(jí)功能。這些功能都是基于子表達(dá)式獨(dú)立進(jìn)行匹配，因此在編程語(yǔ)言里，使用的正則表達(dá)式庫(kù)都是基于 NFA 實(shí)現(xiàn)的。

那么 NFA 自動(dòng)機(jī)到底是怎么進(jìn)行匹配的呢？我以下面的字符和表達(dá)式來(lái)舉例說(shuō)明。

text=“aabcab”

regex=“bc”

NFA 自動(dòng)機(jī)會(huì)讀取正則表達(dá)式的每一個(gè)字符，拿去和目標(biāo)字符串匹配，匹配成功就換正則表達(dá)式的下一個(gè)字符，反之就繼續(xù)和目標(biāo)字符串的下一個(gè)字符進(jìn)行匹配。

分解一下過(guò)程。

首先，讀取正則表達(dá)式的第一個(gè)匹配符和字符串的第一個(gè)字符進(jìn)行比較，b 對(duì) a，不匹配；繼續(xù)換字符串的下一個(gè)字符，也是 a，不匹配；繼續(xù)換下一個(gè)，是 b，匹配。

然后，同理，讀取正則表達(dá)式的第二個(gè)匹配符和字符串的第四個(gè)字符進(jìn)行比較，c 對(duì) c，匹配；繼續(xù)讀取正則表達(dá)式的下一個(gè)字符，然而后面已經(jīng)沒(méi)有可匹配的字符了，結(jié)束。

這就是 NFA 自動(dòng)機(jī)的匹配過(guò)程，雖然在實(shí)際應(yīng)用中，碰到的正則表達(dá)式都要比這復(fù)雜，但匹配方法是一樣的。   

NFA 自動(dòng)機(jī)的回溯

用 NFA 自動(dòng)機(jī)實(shí)現(xiàn)的比較復(fù)雜的正則表達(dá)式，在匹配過(guò)程中經(jīng)常會(huì)引起回溯問(wèn)題。大量的

回溯會(huì)長(zhǎng)時(shí)間地占用 CPU，從而帶來(lái)系統(tǒng)性能開銷。我來(lái)舉例說(shuō)明。

text=“abbc”

regex=“ab{1,3}c”

這個(gè)例子，匹配目的比較簡(jiǎn)單。匹配以 a 開頭，以 c 結(jié)尾，中間有 1-3 個(gè) b 字符的字符串。

NFA 自動(dòng)機(jī)對(duì)其解析的過(guò)程是這樣的：

首先，讀取正則表達(dá)式第一個(gè)匹配符 a 和字符串第一個(gè)字符 a 進(jìn)行比較，a 對(duì) a，匹配。

然后，讀取正則表達(dá)式第二個(gè)匹配符 b{1,3} 和字符串的第二個(gè)字符 b 進(jìn)行比較，匹配。但因?yàn)?b{1,3} 表示 1-3 個(gè) b 字符串，NFA 自動(dòng)機(jī)又具有貪婪特性，所以此時(shí)不會(huì)繼續(xù)讀取正則表達(dá)式的下一個(gè)匹配符，而是依舊使用 b{1,3} 和字符串的第三個(gè)字符 b 進(jìn)行比較，結(jié)果還是匹配。

接著繼續(xù)使用 b{1,3} 和字符串的第四個(gè)字符 c 進(jìn)行比較，發(fā)現(xiàn)不匹配了，此時(shí)就會(huì)發(fā)生回溯，已經(jīng)讀取的字符串第四個(gè)字符 c 將被吐出去，指針回到第三個(gè)字符 b 的位置。

那么發(fā)生回溯以后，匹配過(guò)程怎么繼續(xù)呢？程序會(huì)讀取正則表達(dá)式的下一個(gè)匹配符 c，和字符串中的第四個(gè)字符 c 進(jìn)行比較，結(jié)果匹配，結(jié)束。

如何避免回溯問(wèn)題？

既然回溯會(huì)給系統(tǒng)帶來(lái)性能開銷，那如何應(yīng)對(duì)呢？如果你有仔細(xì)看上面那個(gè)案例的話，

你會(huì)發(fā)現(xiàn) NFA 自動(dòng)機(jī)的貪婪特性就是導(dǎo)火索，這和正則表達(dá)式的匹配模式息息相關(guān).

1. 貪婪模式（Greedy）

顧名思義，就是在數(shù)量匹配中，如果單獨(dú)使用 +、 ? 、* 或{min,max} 等量詞，正則表達(dá)式會(huì)匹配盡可能多的內(nèi)容。

例如，上邊那個(gè)例子：

text=“abbc”

regex=“ab{1,3}c”

就是在貪婪模式下，NFA 自動(dòng)機(jī)讀取了最大的匹配范圍，即匹配 3 個(gè) b 字符。匹配發(fā)生了一次失敗，就引起了一次回溯。如果匹配結(jié)果是“abbbc”，就會(huì)匹配成功。

2. 懶惰模式（Reluctant）

在該模式下，正則表達(dá)式會(huì)盡可能少地重復(fù)匹配字符。如果匹配成功，它會(huì)繼續(xù)匹配剩余的字符串。

例如，在上面例子的字符后面加一個(gè)“？”，就可以開啟懶惰模式。

text=“abc”

regex=“ab{1,3}?c”

匹配結(jié)果是“abc”，該模式下 NFA 自動(dòng)機(jī)首先選擇最小的匹配范圍，即匹配 1 個(gè) b 字符，因此就避免了回溯問(wèn)題。

3. 獨(dú)占模式（Possessive）

同貪婪模式一樣，獨(dú)占模式一樣會(huì)最大限度地匹配更多內(nèi)容；不同的是，在獨(dú)占模式下，匹配失敗就會(huì)結(jié)束匹配，不會(huì)發(fā)生回溯問(wèn)題。

還是上邊的例子，在字符后面加一個(gè)“+”，就可以開啟獨(dú)占模式。

text=“abbc”

regex=“ab{1,3}+bc”

結(jié)果是不匹配，結(jié)束匹配，不會(huì)發(fā)生回溯問(wèn)題。

避免回溯的方法就是：使用懶惰模式和獨(dú)占模式。

3,正則表達(dá)式的優(yōu)化

1. 少用貪婪模式，多用獨(dú)占模式

貪婪模式會(huì)引起回溯問(wèn)題，我們可以使用獨(dú)占模式來(lái)避免回溯。

2. 減少分支選擇

分支選擇類型“(X|Y|Z)”的正則表達(dá)式會(huì)降低性能，我們?cè)陂_發(fā)的時(shí)候要盡量減少使用。

如果一定要用，我們可以通過(guò)以下幾種方式來(lái)優(yōu)化：

首先，我們需要考慮選擇的順序，將比較常用的選擇項(xiàng)放在前面，使它們可以較快地被匹配；

其次，我們可以嘗試提取共用模式，例如，將“(abcd|abef)”替換為“ab(cd|ef)”，后者匹配速度較快，因?yàn)?NFA 自動(dòng)機(jī)會(huì)嘗試匹配 ab，如果沒(méi)有找到，就不會(huì)再嘗試任何選項(xiàng)；

最后，如果是簡(jiǎn)單的分支選擇類型，我們可以用三次 index 代替“(X|Y|Z)”，如果測(cè)試的話，你就會(huì)發(fā)現(xiàn)三次 index 的效率要比“(X|Y|Z)”高出一些。

3. 減少捕獲嵌套 （?:exp）

捕獲組是指把正則表達(dá)式中，子表達(dá)式匹配的內(nèi)容保存到以數(shù)字編號(hào)或顯式命名的數(shù)組中，方便后面引用。一般一個(gè) () 就是一個(gè)捕獲組，捕獲組可以進(jìn)行嵌套。

非捕獲組則是指參與匹配卻不進(jìn)行分組編號(hào)的捕獲組，其表達(dá)式一般由（?:exp）組成。

在正則表達(dá)式中，每個(gè)捕獲組都有一個(gè)編號(hào)，編號(hào) 0 代表整個(gè)匹配到的內(nèi)容。

例子：

public static void main(String args[]) {
    String text = "<input high=\"20\" weight=\"70\">test</input>";
    String reg = "(<input.*?>)(.*?)(</input>)";
    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));
    }
}

輸出：

<input high=\"20\" weight=\"70\">test</input>
<input high=\"20\" weight=\"70\">
test
</input>

如果你并不需要獲取某一個(gè)分組內(nèi)的文本，那么就使用非捕獲分組。例如，使用“(?:X)”代替“(X)”

public static void main(String args[]) {
    String text = "<input high=\"20\" weight=\"70\">test</input>";
    String reg="(?:<input.*?>)(.*?)(?:</input>)";
    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));
    }
}

輸出：

<input high=\"20\" weight=\"70\">test</input>
test

綜上：減少不需要獲取的分組，可以提高正則表達(dá)式的性能。

總結(jié)

正則表達(dá)式雖然小，卻有著強(qiáng)大的匹配功能。我們經(jīng)常用到它，比如，注冊(cè)頁(yè)面手機(jī)號(hào)或郵箱的校驗(yàn)。

但很多時(shí)候，我們又會(huì)因?yàn)樗《雎运氖褂靡?guī)則，測(cè)試用例中又沒(méi)有覆蓋到一些特殊用例，導(dǎo)致上線就中招的情況發(fā)生。

如果要使用正則表達(dá)式，要在做好性能排查的前提下；如果不能，那么正則表達(dá)式能不用就不用，以此避免造成更多的性能問(wèn)題。

如果要使用正則表達(dá)式，養(yǎng)成使用獨(dú)占或者懶惰模式的習(xí)慣。

到此這篇關(guān)于java正則表達(dá)式優(yōu)化的文章就介紹到這了,更多相關(guān)java正則表達(dá)式優(yōu)化內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論