正則表達(dá)式的應(yīng)用原理
正則表達(dá)式應(yīng)用到目標(biāo)字符串的過程大致分為下面幾步：
- 編譯正則表達(dá)式。檢查正則表達(dá)式的正確性窗轩，如果正確夯秃，將其編譯為內(nèi)部形式座咆。
- 開始傳動(dòng)痢艺。將正則引擎定位到目標(biāo)字符串的起始位置。
- 檢測(cè)元素介陶。
- 引擎開始依次測(cè)試表達(dá)式的各個(gè)元素和目標(biāo)字符串堤舒。
- 在檢測(cè)相連元素時(shí)，引擎會(huì)在某個(gè)元素匹配失敗時(shí)停止哺呜。
- 量詞修飾的元素舌缤，控制權(quán)在量詞和被限定的元素之間輪換。
控制權(quán)在捕獲型括號(hào)內(nèi)外切換會(huì)帶來額外的開銷某残。捕獲型括號(hào)內(nèi)表達(dá)式匹配的文本必須保留国撵，才能通過$1或\1來引用。括號(hào)也可能屬于某個(gè)回溯分支玻墅，括號(hào)內(nèi)的狀態(tài)就是用于回溯的狀態(tài)的一部分介牙，所以進(jìn)入和退出捕獲型括號(hào)時(shí)需要修改狀態(tài)。
- 尋找匹配結(jié)果澳厢。若找到匹配結(jié)果环础，傳統(tǒng)型NFA立即報(bào)告匹配成功（POSIX NFA則在嘗試完所有可能的情況之后，返回最長(zhǎng)的匹配）剩拢。若沒有找到匹配线得，從當(dāng)前傳動(dòng)位置前進(jìn)一位，開始下一輪嘗試徐伐。
- 匹配徹底失敗贯钩。在所有可能的嘗試都失敗之后，報(bào)告失敗办素。
全面考察回溯
下面我們通過幾個(gè)例子來考察回溯在匹配成功和不成功時(shí)的各種細(xì)節(jié)角雷。如表達(dá)式".*"對(duì)字符串The name "McDonald's" is said "makudonarudo" in Japanese的匹配過程如下：
我們知道
".*"!無法匹配上述字符串，但引擎在報(bào)告匹配失敗之前仍會(huì)進(jìn)行多次嘗試：
如果我們將
.換成[^"]摸屠，[^"]*匹配的內(nèi)容就能不包括雙引號(hào)谓罗，這減少了匹配和回溯的次數(shù)：
但是需要注意的是
"[^"]*"和".*"在此例中的匹配結(jié)果并不一樣。
一個(gè)簡(jiǎn)單的例子
假設(shè)字符串"2 \"x3\" likeness"季二，為了匹配雙引號(hào)及之內(nèi)的字符串檩咱，且允許出現(xiàn)轉(zhuǎn)義的雙引號(hào)揭措。"(\\\\.|[^\\"])*"的匹配結(jié)果雖然正確，但在效率方面有所欠缺刻蚯，通過優(yōu)化能加快匹配速度绊含。
調(diào)整多選結(jié)構(gòu)的順序
對(duì)于一般的雙引號(hào)字符串而言，普通字符的數(shù)量要比轉(zhuǎn)義字符多炊汹，將[^\\"]放到\\\\.之前可以有效減少回溯次數(shù)躬充。
調(diào)整分支的順序必須要保證排序與匹配成功無關(guān)。同時(shí)讨便，這種改動(dòng)并不能加快報(bào)告失敗的速度充甚，因?yàn)樵趫?bào)告匹配失敗之前，所有可能的匹配都已經(jīng)被嘗試霸褒。
| 目標(biāo)字符串 | "(\\.|[^\\"])*" | "([^\\"]|\\.)*" |
|---|---|---|
| "2"x3" likeness" | 32次測(cè)試伴找，14次回溯 | 22次測(cè)試，4次回溯 |
| "... 99 more chars ..." | 218次測(cè)試废菱，109次回溯 | 111次測(cè)試技矮，2次回溯 |
| "no "match" here | 124次測(cè)試，86次回溯 | 124次測(cè)試殊轴，86次回溯 |
消除循環(huán)
由于*控制著捕獲型括號(hào)內(nèi)的多選結(jié)構(gòu)衰倦，每次進(jìn)出括號(hào)都意味著狀態(tài)的切換，為避免這部分的消耗旁理，可以通過消除循環(huán)的技巧對(duì)表達(dá)式進(jìn)行改進(jìn)樊零。這項(xiàng)技巧我們將在下文講到，這里給出當(dāng)前例子在消除循環(huán)之后的表達(dá)式是"[^\\"]+(\\\\.[^\\"]+)*"韧拒。
錯(cuò)誤的優(yōu)化
為了減少*的迭代次數(shù)淹接，在[^\\"]后引入+。對(duì)于不存在轉(zhuǎn)義字符的字符串而言叛溢，這樣會(huì)一次性讀入整個(gè)字符串塑悼，而不用進(jìn)行回溯。這改動(dòng)似乎帶來了不錯(cuò)的收益楷掉，在匹配成功的時(shí)候也確是如此厢蒜。但在匹配失敗時(shí)，卻會(huì)造成指數(shù)級(jí)的回溯烹植。例如目標(biāo)字符串是makudonarudo斑鸦，+會(huì)對(duì)字符串做任意長(zhǎng)度的切割，*再在切割的基礎(chǔ)上進(jìn)行多次迭代草雕。長(zhǎng)度為n的字符串巷屿，回溯的次數(shù)是$2^{n+1}$，獨(dú)立測(cè)試的次數(shù)為$2^{n+1}+2^n$墩虹。如"2\"x3\" likeness and makudonarudo這種長(zhǎng)度的目標(biāo)字符串時(shí)就會(huì)造成應(yīng)用程序的未響應(yīng)嘱巾。
常見的優(yōu)化措施
對(duì)于正則引擎憨琳，各流派有自己的實(shí)現(xiàn)和優(yōu)化措施。實(shí)現(xiàn)方案互有差異旬昭，優(yōu)化措施也不盡相同篙螟，但通常可以歸納為兩類：
- 加速某些操作问拘。
-
避免冗余操作遍略。如果引擎認(rèn)為某些操作對(duì)于產(chǎn)生正確的結(jié)果是不必要的，或者某些操作能夠應(yīng)用到比之前更少的文本骤坐，而忽略這些操作可以節(jié)省時(shí)間绪杏。比如以
^、$錨定位置的表達(dá)式只有在行首（尾）才能匹配或油，若匹配失敗寞忿，引擎不會(huì)在其它位置進(jìn)行無謂的嘗試。
對(duì)某個(gè)正則表達(dá)式的改動(dòng)顶岸，在某個(gè)流派的實(shí)現(xiàn)方式中可能帶來收益，而在另一個(gè)實(shí)現(xiàn)方式中卻與期望背道而馳叫编。在進(jìn)行優(yōu)化時(shí)辖佣，檢測(cè)并性能測(cè)試實(shí)際期望應(yīng)用的同類型數(shù)據(jù)，總是有助于判斷改動(dòng)是否有益搓逾。
應(yīng)用正則表達(dá)式之前的優(yōu)化措施
用戶通過Pattern.compile在正則表達(dá)式應(yīng)用之前卷谈，完成對(duì)正則表達(dá)式的編譯。尤其是循環(huán)之前編譯正則表達(dá)式霞篡，可以有效減少構(gòu)建表達(dá)式內(nèi)部形式的次數(shù)世蔗。這種方式，被稱為“面向?qū)ο笫教幚碇械木幾g緩存” 朗兵。此外還有“集成式處理中的編譯緩存” 和“程序式處理中的編譯緩存”污淋，此處就不做介紹了。
通過傳動(dòng)裝置進(jìn)行優(yōu)化
行錨點(diǎn)優(yōu)化余掖。能使用這種優(yōu)化措施的引擎知道寸爆，在錨定位置才能滿足表達(dá)式的匹配條件，傳動(dòng)裝置會(huì)直接略過目標(biāo)字符串中的其它位置的字符盐欺。
優(yōu)化正則表達(dá)式本身
-
消除不必要的括號(hào)赁豆。對(duì)于不需要捕獲的分組，用
(?: expression)代替(expression)冗美。 -
消除不必要的字符組魔种。沒必要對(duì)單個(gè)字符應(yīng)用字符組，特別是
[.]粉洼，完全可以用\.來代替节预。 -
避免指數(shù)級(jí)的回溯甲抖。對(duì)于
(.+)*之類的量詞結(jié)合結(jié)構(gòu)，+和*二者分隔目標(biāo)字符串為任意長(zhǎng)度的子字符串心铃，制造出指數(shù)級(jí)的回溯准谚。 - 使用占有優(yōu)先量詞/固化分組削減狀態(tài)。在確定量詞限定的元素與其之后的元素不會(huì)匹配重疊的情況下去扣，可以使用占有優(yōu)先量詞柱衔，或者固化分組減少存儲(chǔ)的備用狀態(tài)。當(dāng)然這種做法必須建立在引擎支持占有優(yōu)先量詞愉棱，或者固化分組的基礎(chǔ)上唆铐。
-
用字符組代替多選結(jié)構(gòu)。用
[uvwxyz]代替u|v|w|x|y|z奔滑，因?yàn)榍罢咧贿M(jìn)行匹配操作艾岂，而后者可能需要在目標(biāo)字符串的每個(gè)位置進(jìn)行6次回溯。由這個(gè)例子可以看出多選結(jié)構(gòu)或許是造成回溯的主要原因朋其。 - 控制多選結(jié)構(gòu)的順序王浴。將最可能匹配的分支放在前面，減少回溯梅猿。
-
將多選結(jié)構(gòu)中開頭相同的字符提取到多選結(jié)構(gòu)之前氓辣。如
this|that就可以改成th(?:is|at)。這樣th只需檢查一遍袱蚓，只有在確實(shí)需要的時(shí)候才會(huì)用到代價(jià)相對(duì)高昂的多選結(jié)構(gòu)功能钞啸。 -
按實(shí)際情況選擇忽略優(yōu)先量詞和匹配優(yōu)先量詞。忽略優(yōu)先量詞通常要比匹配優(yōu)先量詞要慢（這不是言之確鑿的）喇潘。另外對(duì)大多數(shù)引擎而言体斩，排除型字符組的效率要比忽略優(yōu)先量詞快的多。如
"[^"]*"和".*?"颖低。 - 避免過于復(fù)雜的正則表達(dá)式絮吵。
消除循環(huán)
所謂“循環(huán)”，指得是(this|that|...)*這類表達(dá)式中*代表的意義枫甲。消除循環(huán)這項(xiàng)技巧對(duì)于某些常用的表達(dá)式來說源武，加速效果非常明顯。消除循環(huán)常用的解法是：
opening normal* (special normal*)* closing
這種解法中最重要的是要區(qū)分表達(dá)式中的special和normal部分想幻。一般而言粱栖，對(duì)于目標(biāo)字符串中最常見的部分用normal子表達(dá)式處理，用special子表達(dá)式作為檢查點(diǎn)處理其余不常見的部分脏毯。為避免(special normal*)*中的無休止匹配（即指數(shù)型回溯）闹究，需要確保以下三點(diǎn)：
-
special部分和normal部分匹配的開頭不能重合； -
normal部分必須能匹配至少一個(gè)字符食店； -
special部分是固化的渣淤。當(dāng)存在多種方式匹配同樣的文本時(shí)赏寇，(special normal*)*最終也難免淪為(expression*)*，也就無從避免無休止匹配了价认。
例1：用<B>(?>[^<]*)(?>(?!</?B>)<[^<]*)*</B>代替<B>((?!</?B>).)*</B>嗅定，這里的固化分組不是必須的，但如果只能部分匹配用踩，使用固化分組可以提高速度渠退。
例2：/\*[^*]*\*+([^/*][^*]*\*+)*/匹配java文件中的多行注釋。
回過頭來看消除循環(huán)這項(xiàng)技巧脐彩，它對(duì)表達(dá)式的可讀性和可維護(hù)性造成了一定影響碎乃，但是測(cè)試證明其帶來的速度收益也同樣十分明顯。
