正則表達(dá)式
正則表達(dá)式是計(jì)算機(jī)科學(xué)的一個(gè)概念岛抄，使用一些特定的元字符進(jìn)行檢索匹配及替換符合規(guī)則的字符串广匙，很多語言實(shí)現(xiàn)了正則表達(dá)式袱院。
構(gòu)造正則表達(dá)式語法的元字符由普通字符平斩、標(biāo)準(zhǔn)字符亚享、限定字符(量詞)、定位字符(邊界字符)組成绘面。如圖：
正則表達(dá)式引擎
正則表達(dá)式是一個(gè)用正則符號(hào)寫出的公式欺税，程序?qū)@個(gè)公式進(jìn)行語法分析，建立一個(gè)語法分析樹揭璃，再根據(jù)分析樹結(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 Automation 確定有限狀態(tài)自動(dòng)機(jī))
- NFA自動(dòng)機(jī)(Non Deterministic Finite Automation 非確定有限狀態(tài)自動(dòng)機(jī))
以下是兩種狀態(tài)機(jī)的對(duì)比：
| 狀態(tài)機(jī) | 構(gòu)造代價(jià) | 執(zhí)行效率 |
|---|---|---|
| DFA | 遠(yuǎn)大于NFA | 高 |
| NFA | 遠(yuǎn)小于DFA | 低 |
假設(shè)，有字符串長度為n情组，若用DFA自動(dòng)機(jī)作為正則表達(dá)式燥筷，則匹配的時(shí)間復(fù)雜度為O(n)；若用NFA自動(dòng)機(jī)作為正則表達(dá)式引擎院崇，由于NFA自動(dòng)機(jī)在匹配過程中存在大量分支和回溯肆氓，假設(shè)NFA的狀態(tài)數(shù)為s，則該匹配算法的時(shí)間復(fù)雜度為O(ns)底瓣。
NFA自動(dòng)機(jī)的優(yōu)勢是支持更多的功能谢揪。例如，捕獲group捐凭、環(huán)視拨扶、占有優(yōu)先量詞等高級(jí)功能。這些功能都是基于子表達(dá)式獨(dú)立進(jìn)行匹配柑营，因此在編程語言里屈雄，使用的正則表達(dá)式庫都是基于NFA實(shí)現(xiàn)的。
那么NFA自動(dòng)機(jī)是如何進(jìn)行匹配的官套？
text = "aabcab";
regex = "bc";
首先酒奶，讀取正則表達(dá)式的第一個(gè)匹配符b和字符串的第一個(gè)字符a進(jìn)行比較，不匹配奶赔；繼續(xù)換字符串的下一個(gè)匹配字符a惋嚎，不匹配；繼續(xù)換下一個(gè)b站刑，匹配另伍。
然后，同理，讀取正則表達(dá)式的第二個(gè)匹配符c和字符串的第四個(gè)字符c比較摆尝，匹配温艇；繼續(xù)讀取正則表達(dá)式的下一個(gè)字符，下一個(gè)字符為空堕汞，沒有可以匹配的字符勺爱，匹配結(jié)束。
以上就是NFA自動(dòng)機(jī)的匹配過程讯检，在實(shí)際使用中琐鲁，碰到的正則表達(dá)式都要比這個(gè)例子復(fù)雜，但匹配的過程是相同的人灼。
NFA自動(dòng)機(jī)的回溯
用NFA自動(dòng)機(jī)實(shí)現(xiàn)的比較復(fù)雜的正則表達(dá)式围段，在匹配過程中經(jīng)常會(huì)引起回溯問題。大量的回溯會(huì)長時(shí)間占用CPU投放，帶來系統(tǒng)性能開銷奈泪。
舉例：
text = "abbc";
regex = "ab{1,3}c"
這個(gè)例子，匹配的規(guī)則比較簡單灸芳。以a開頭段磨，以c結(jié)尾，中間包含1-3個(gè)b的字符串耗绿。NFA自動(dòng)機(jī)對(duì)其解析的過程如下:
首先，讀取正則表達(dá)式第一個(gè)匹配符a和字符串第一個(gè)字符a比較砾隅，匹配误阻。
然后，讀取正則表達(dá)式第二個(gè)匹配符b{1晴埂，3}和字符串的第二個(gè)字符b進(jìn)行比較究反，匹配。
由于b{1,3}表示1-3個(gè)字符串儒洛，NFA的貪婪特性不會(huì)繼續(xù)讀取正則表達(dá)式的下一個(gè)匹配符精耐，而是依舊使用b{1,3}和字符串的第三個(gè)字符b進(jìn)行比較，結(jié)果還是匹配琅锻。
接著繼續(xù)使用b{1,3}和字符串的第4個(gè)字符c進(jìn)行比較卦停，發(fā)現(xiàn)不匹配，此時(shí)就會(huì)發(fā)生回溯恼蓬，已經(jīng)讀取的字符串第四個(gè)字符c將會(huì)被吐出去惊完，指針回到第三個(gè)字符b的位置。
發(fā)生回溯后处硬，程序會(huì)讀取正則表達(dá)式的下一個(gè)匹配符c小槐，和字符串的第四個(gè)字符c進(jìn)行比較，結(jié)果匹配荷辕，正則判斷結(jié)束凿跳。
如何減少回溯問題
從上面的案例可知件豌，回溯的原因是NFA自動(dòng)機(jī)的貪婪特性，這和正則表達(dá)式的匹配模式息息相關(guān)控嗜。
貪婪模式(Greedy)
故名思意茧彤，就是在數(shù)量匹配中，如果單獨(dú)使用+躬审、棘街？、*或{min,max}等量詞承边，正則表達(dá)式會(huì)匹配盡可能多的內(nèi)容遭殉。
例如上邊的例子，在貪婪模式下博助，NFA自動(dòng)機(jī)讀取了最大的匹配范圍险污，匹配發(fā)生了一次失敗，就引發(fā)了一次回溯富岳。-
懶惰模式(Reluctant)
在該模式下蛔糯，正則表達(dá)式會(huì)盡可能少地匹配字符。如果匹配成功窖式，則繼續(xù)匹配剩余的字符串蚁飒。在上例的字符串后加一個(gè)'?'就可以開啟懶惰模式。
若匹配的字符串是"abc"萝喘。
該模式下NFA自動(dòng)機(jī)首選匹配'abc'淮逻，即最小范圍的匹配一個(gè)b字符，因此避免了回溯問題阁簸。
懶惰模式是無法完全避免回溯的爬早，上例中匹配字符為"abbc"，那么启妹，首先正則會(huì)讀取第一個(gè)匹配符a和字符串中第一個(gè)字符a匹配筛严，成功。然后讀取第二個(gè)匹配符b{1,3}和字符串的第二個(gè)字符b進(jìn)行比較饶米，匹配桨啃。
image.png其次，懶惰模式下檬输，正則表達(dá)式會(huì)盡可能少的匹配重復(fù)字符优幸，則匹配字符放棄匹配b，轉(zhuǎn)而匹配c褪猛。
image.png此時(shí)网杆，匹配字符c與字符串中第二個(gè)字符b不匹配，此時(shí)會(huì)發(fā)生回溯，這次的回溯與貪婪模式相反碳却，回溯的是匹配字符c队秩。
image.png -
獨(dú)占模式
同貪婪模式一樣，獨(dú)占模式會(huì)最大限度地匹配更多的內(nèi)容昼浦，不同的是馍资，獨(dú)占模式匹配失敗就會(huì)結(jié)束匹配，不會(huì)發(fā)生回溯問題关噪。上例中鸟蟹，在字符串后加一個(gè)"+"就可以開啟獨(dú)占模式。text = "abbc"; regex = "ab{1,3}+bc";結(jié)果是不匹配使兔，不會(huì)發(fā)生回溯問題建钥。
同樣，獨(dú)占模式也不能避免回溯的發(fā)生虐沥，如上例text = "abbc"; regex = "ab{1,3}+c";結(jié)果是匹配的熊经，因?yàn)楠?dú)占模式會(huì)最大限度的匹配更多的內(nèi)容，完成所有的b欲险，再去匹配c镐依。
優(yōu)化
- 少用貪婪模式，多用獨(dú)占模式
貪婪模式會(huì)引起回溯問題天试，我們可以使用獨(dú)占模式避免回溯槐壳。 - 減少分支選擇
分支選擇類型"(X|Y|Z)"的正則表達(dá)式會(huì)降低性能，開發(fā)時(shí)需要盡量減少使用喜每。如果一定要使用宏粤，我們可以通過以下幾種方式來優(yōu)化：
a. 首先，需要考慮選擇的順序灼卢，將比較常用的選擇項(xiàng)放在前面，使其可以優(yōu)先匹配来农；
b. 我們可以嘗試提取共用模式鞋真，如將"(abcd|abef)"替換為"ab(cd|ef)"，NFA自動(dòng)機(jī)如果沒有匹配到ab將不會(huì)繼續(xù)匹配沃于。
c. 如果是簡單的分支選擇類型涩咖，使用三次index的效率要高一些。 - 減少捕獲嵌套
捕獲組：把正則表達(dá)式中繁莹，子表達(dá)式匹配的內(nèi)容保存到以數(shù)字編號(hào)或顯示命名的數(shù)組中檩互，方便后面引用。捕獲組可以進(jìn)行嵌套咨演。
非捕獲組：參與匹配卻不進(jìn)行分組編號(hào)的捕獲組闸昨，表達(dá)式一般由(?:exp)組成。
在正則表達(dá)式中，每個(gè)捕獲組都有一個(gè)編號(hào)饵较，編號(hào)0代表整個(gè)匹配到的內(nèi)容拍嵌。
運(yùn)行結(jié)果：public static void mian(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));//整個(gè)匹配到的內(nèi)容 System.out.println(m.group(1));//(<input.*?>) System.out.println(m.group(2));//(.*?) System.out.println(m.group(3));//(</input>) } }
如果并不需要獲取某個(gè)分組內(nèi)的文本，那么就使用非捕獲分組循诉。例如使用"(?:X)"代替"(X)"<input hight=\'20\' weight=\'70\'>test</input> <input hight=\'20\' weight=\'70\'> test </input>
運(yùn)行結(jié)果：public static void mian(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));//整個(gè)匹配到的內(nèi)容 System.out.println(m.group(1));//(.*?) } }
減少不需要獲取的分組横辆，可以提高正則表達(dá)式的性能。<input hight=\'20\' weight=\'70\'>test</input> test
總結(jié)
如果正則表達(dá)式能使代碼簡潔方便茄猫，那么在做好性能排除的前提下狈蚤，可以使用；如果能划纽，那么正則表達(dá)式能不用就不用脆侮，以此避免性能問題。
