正則表達(dá)式的應(yīng)用原理

正則表達(dá)式應(yīng)用到目標(biāo)字符串的過(guò)程大致分為下面幾步：

• 編譯正則表達(dá)式。檢查正則表達(dá)式的正確性，如果正確，將其編譯為內(nèi)部形式。
• 開(kāi)始傳動(dòng)。將正則引擎定位到目標(biāo)字符串的起始位置。
• 檢測(cè)元素。

1. 引擎開(kāi)始依次測(cè)試表達(dá)式的各個(gè)元素和目標(biāo)字符串。
2. 在檢測(cè)相連元素時(shí)，引擎會(huì)在某個(gè)元素匹配失敗時(shí)停止。
3. 量詞修飾的元素，控制權(quán)在量詞和被限定的元素之間輪換。

控制權(quán)在捕獲型括號(hào)內(nèi)外切換會(huì)帶來(lái)額外的開(kāi)銷(xiāo)。捕獲型括號(hào)內(nèi)表達(dá)式匹配的文本必須保留，才能通過(guò)$1或\1來(lái)引用。括號(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)的匹配）。若沒(méi)有找到匹配，從當(dāng)前傳動(dòng)位置前進(jìn)一位，開(kāi)始下一輪嘗試。
• 匹配徹底失敗。在所有可能的嘗試都失敗之后，報(bào)告失敗。

全面考察回溯

下面我們通過(guò)幾個(gè)例子來(lái)考察回溯在匹配成功和不成功時(shí)的各種細(xì)節(jié)。如表達(dá)式".*"對(duì)字符串The name "McDonald's" is said "makudonarudo" in Japanese的匹配過(guò)程如下：

<small>圖1</small>

<small>圖2</small>

<small>圖3</small>

一個(gè)簡(jiǎn)單的例子

假設(shè)字符串"2 \"x3\" likeness"，為了匹配雙引號(hào)及之內(nèi)的字符串，且允許出現(xiàn)轉(zhuǎn)義的雙引號(hào)。"(\\\\.|[^\\"])*"的匹配結(jié)果雖然正確，但在效率方面有所欠缺，通過(guò)優(yōu)化能加快匹配速度。

調(diào)整多選結(jié)構(gòu)的順序

對(duì)于一般的雙引號(hào)字符串而言，普通字符的數(shù)量要比轉(zhuǎn)義字符多，將[^\\"]放到\\\\.之前可以有效減少回溯次數(shù)。

<small>圖4</small>

消除循環(huán)

由于*控制著捕獲型括號(hào)內(nèi)的多選結(jié)構(gòu)，每次進(jìn)出括號(hào)都意味著狀態(tài)的切換，為避免這部分的消耗，可以通過(guò)消除循環(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)似乎帶來(lái)了不錯(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)。

常見(jiàn)的優(yōu)化措施

對(duì)于正則引擎，各流派有自己的實(shí)現(xiàn)和優(yōu)化措施。實(shí)現(xiàn)方案互有差異，優(yōu)化措施也不盡相同，但通?？梢詺w納為兩類(lèi)：

• 加速某些操作。
• 避免冗余操作。如果引擎認(rèn)為某些操作對(duì)于產(chǎn)生正確的結(jié)果是不必要的，或者某些操作能夠應(yīng)用到比之前更少的文本，而忽略這些操作可以節(jié)省時(shí)間。比如以^、$錨定位置的表達(dá)式只有在行首（尾）才能匹配，若匹配失敗，引擎不會(huì)在其它位置進(jìn)行無(wú)謂的嘗試。

對(duì)某個(gè)正則表達(dá)式的改動(dòng)，在某個(gè)流派的實(shí)現(xiàn)方式中可能帶來(lái)收益，而在另一個(gè)實(shí)現(xiàn)方式中卻與期望背道而馳。在進(jìn)行優(yōu)化時(shí)，檢測(cè)并性能測(cè)試實(shí)際期望應(yīng)用的同類(lèi)型數(shù)據(jù)，總是有助于判斷改動(dòng)是否有益。

應(yīng)用正則表達(dá)式之前的優(yōu)化措施

用戶(hù)通過(guò)Pattern.compile在正則表達(dá)式應(yīng)用之前，完成對(duì)正則表達(dá)式的編譯。尤其是循環(huán)之前編譯正則表達(dá)式，可以有效減少構(gòu)建表達(dá)式內(nèi)部形式的次數(shù)。這種方式，被稱(chēng)為“面向?qū)ο笫教幚碇械木幾g緩存” 。此外還有“集成式處理中的編譯緩存” 和“程序式處理中的編譯緩存”，此處就不做介紹了。

通過(guò)傳動(dòng)裝置進(jìn)行優(yōu)化

行錨點(diǎn)優(yōu)化。能使用這種優(yōu)化措施的引擎知道，在錨定位置才能滿(mǎn)足表達(dá)式的匹配條件，傳動(dòng)裝置會(huì)直接略過(guò)目標(biāo)字符串中的其它位置的字符。

優(yōu)化正則表達(dá)式本身

• 消除不必要的括號(hào)。對(duì)于不需要捕獲的分組，用(?: expression)代替(expression)。
• 消除不必要的字符組。沒(méi)必要對(duì)單個(gè)字符應(yīng)用字符組，特別是[.]，完全可以用\.來(lái)代替。
• 避免指數(shù)級(jí)的回溯。對(duì)于(.+)*之類(lèi)的量詞結(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)中開(kāi)頭相同的字符提取到多選結(jié)構(gòu)之前。如this|that就可以改成th(?:is|at)。這樣th只需檢查一遍，只有在確實(shí)需要的時(shí)候才會(huì)用到代價(jià)相對(duì)高昂的多選結(jié)構(gòu)功能。
• 按實(shí)際情況選擇忽略?xún)?yōu)先量詞和匹配優(yōu)先量詞。忽略?xún)?yōu)先量詞通常要比匹配優(yōu)先量詞要慢（這不是言之確鑿的）。另外對(duì)大多數(shù)引擎而言，排除型字符組的效率要比忽略?xún)?yōu)先量詞快的多。如"[^"]*"和".*?"。
• 避免過(guò)于復(fù)雜的正則表達(dá)式。

消除循環(huán)

所謂“循環(huán)”，指得是(this|that|...)*這類(lèi)表達(dá)式中*代表的意義。消除循環(huán)這項(xiàng)技巧對(duì)于某些常用的表達(dá)式來(lái)說(shuō)，加速效果非常明顯。消除循環(huán)常用的解法是：

opening normal* (special normal*)* closing

這種解法中最重要的是要區(qū)分表達(dá)式中的special和normal部分。一般而言，對(duì)于目標(biāo)字符串中最常見(jiàn)的部分用normal子表達(dá)式處理，用special子表達(dá)式作為檢查點(diǎn)處理其余不常見(jiàn)的部分。為避免(special normal*)*中的無(wú)休止匹配（即指數(shù)型回溯），需要確保以下三點(diǎn)：

• special部分和normal部分匹配的開(kāi)頭不能重合；
• normal部分必須能匹配至少一個(gè)字符；
• special部分是固化的。當(dāng)存在多種方式匹配同樣的文本時(shí)，(special normal*)*最終也難免淪為(expression*)*，也就無(wú)從避免無(wú)休止匹配了。

例1：用<B>(?>[^&lt;]*)(?>(?!</?B>)<[^&lt;]*)*</B>代替<B>((?!</?B>).)*</B>，這里的固化分組不是必須的，但如果只能部分匹配，使用固化分組可以提高速度。
例2：/\*[^*]*\*+([^/*][^*]*\*+)*/匹配java文件中的多行注釋。
回過(guò)頭來(lái)看消除循環(huán)這項(xiàng)技巧，它對(duì)表達(dá)式的可讀性和可維護(hù)性造成了一定影響，但是測(cè)試證明其帶來(lái)的速度收益也同樣十分明顯。