主頁 > 知識庫 > 正則表達式的優(yōu)化全面詳解( 三江小渡)

正則表達式的優(yōu)化全面詳解( 三江小渡)

就像之前寫的mysql全面優(yōu)化詳解一樣，就是因為這樣工具應用十分廣泛，所以對這樣的工具全面的進行優(yōu)化策略總結是非常劃算的，因為無論你是PHP、Perl、Python、C++、C#、Java等等語言的程序員，你都是有非常大可能用上Mysql、正則表達式這樣的工具的。

先說一下你可能不知道的一點關于正則表達式的知識，這對我們將來的優(yōu)化是有用的。
大家常見的grep（global regular expression print）算是現(xiàn)在的正則的起源吧（從神經(jīng)學家提出正則概念到數(shù)學家建立模型到被IBM用都沒有大規(guī)模使用，到最終成為grep獨立工具才被更多使用）?，F(xiàn)在大家用的正則被POSIX（portable operating system interface）分為兩個流派：BREs（base regular expressions）和EREs（extended regular expressions）。POSIX程序必須支持兩者之一。這兩者有不同特性需要了解。詳細內(nèi)容請看之前的一片文章shell腳本學習指南[一]中的 “三、常見3中類型正則表達式比較” 部分。

正則的匹配引擎主要可以分為兩大類：DFA和NFA。前者確定性有限自動機，后者是非確定性有限自動機。編譯原理里邊有講，有興趣的另行wiki?，F(xiàn)在正則引擎又分三類：

1、DFA 引擎在線性時狀態(tài)下執(zhí)行，因為它們不要求回溯（并因此它們永遠不測試相同的字符兩次）。DFA 引擎還可以確保匹配最長的可能的字符串。但是，因為 DFA 引擎只包含有限的狀態(tài)，所以它不能匹配具有反向引用的模式；并且因為它不構造顯示擴展，所以它不可以捕獲子表達式。
2、傳統(tǒng)的 NFA 引擎運行所謂的“貪婪的”匹配回溯算法，以指定順序測試正則表達式的所有可能的擴展并接受第一個匹配項。因為傳統(tǒng)的 NFA 構造正則表達式的特定擴展以獲得成功的匹配，所以它可以捕獲子表達式匹配和匹配的反向引用。但是，因為傳統(tǒng)的 NFA 回溯，所以它可以訪問完全相同的狀態(tài)多次（如果通過不同的路徑到達該狀態(tài)）。因此，在最壞情況下，它的執(zhí)行速度可能非常慢。因為傳統(tǒng)的 NFA 接受它找到的第一個匹配，所以它還可能會導致其他（可能更長）匹配未被發(fā)現(xiàn)。
3、POSIX NFA 引擎與傳統(tǒng)的 NFA 引擎類似，不同的一點在于：在它們可以確保已找到了可能的最長的匹配之前，它們將繼續(xù)回溯。因此，POSIX NFA 引擎的速度慢于傳統(tǒng)的 NFA 引擎；并且在使用 POSIX NFA 時，您恐怕不會愿意在更改回溯搜索的順序的情況下來支持較短的匹配搜索，而非較長的匹配搜索。

根據(jù)正則引擎的不同，我們能夠總結出兩條普適的規(guī)則：
1、優(yōu)先選擇最左端的匹配結果。
2、標準的匹配量詞(* + ？ {n，m})是優(yōu)先匹配的。

這里可以先舉些優(yōu)化的簡單例子：
比如'.*[0-9][0-9]‘ 來匹配字符串”abcd12efghijklmnopqrstuvw”，這時候的匹配方式是‘.*'先匹配了整行，但是不能滿足之后的兩個數(shù)字的匹配，所以‘.*'就退還一個字符‘w'，還是無法匹配，繼續(xù)退還一個‘v'，循環(huán)退還字符到‘2'發(fā)現(xiàn)匹配了一個，但是還是無法匹配兩個數(shù)字，所以繼續(xù)退還‘1'。這樣的情況我們了解這一特性后是應該盡量避免的。如果我們希望一個字符串里含有兩個數(shù)字，直接進行兩個數(shù)字的匹配就好了，就不要寫‘.*'這樣的通配符了。對優(yōu)化的學習其實就是對底層實現(xiàn)的學習，因為優(yōu)化就是盡量順著工具的實現(xiàn)方式來實現(xiàn)自己想要的效果，如果你不了解所使用工具的底層，你也無法很好的知道什么情況合適用什么工具高效。

由上邊對DFA和NFA的介紹，我們知道他們之間的差異，簡單來說就是NFA是表達式主導引擎，DFA是文本主導引擎。一般來說：DFA類引擎只會對目標字符串的每個字符匹配一次，但是NFA則會回溯，文本主導的DFA會比表達式主導的NFA快一些。

細心思考的可能會注意到了，如何盡可能的回避NFA的回溯，將會是我們針對正則NFA引擎的優(yōu)化的一大問題。這中間還有一個是否忽略優(yōu)先匹配的問題，也是需要優(yōu)化的一點。關于優(yōu)先匹配也做一個簡單的解釋，因為上邊說的普適規(guī)則里也說到這個點。如果匹配到一個位置，需要做嘗試匹配或者跳過匹配這樣的選擇的時候，對于量詞匹配，引擎會優(yōu)先作出進行嘗試行為，而忽略量詞優(yōu)先的時候則進行跳過嘗試匹配。舉例來說這兩點如何工作的和為什么是需要優(yōu)化的地方：

用ab?c 來匹配 abc，程序流程類似這樣：
先匹配a這沒問題，再匹配到b的時候，引擎會因為？號考慮要不要匹配b，默認是量詞優(yōu)先的，所以先做匹配嘗試，另一種選擇放在備選狀態(tài)。這樣就匹配了ab了，然后又成功匹配到了c，這樣程序就結束了，備選狀態(tài)就放棄了。

如果依然用ab?c來匹配ac，程序運行到b的時候會首先嘗試匹配b，發(fā)現(xiàn)不行，這時候就會回溯，即回到匹配好a了的狀態(tài)，然后程序繼續(xù)運行匹配c，然后成功結束。這個過程就進行了回溯，學過算法的這個過程很好理解。就是類似棧的后進先出，這樣總能比較方便的回溯的上一個合法的狀態(tài)。

再來看忽略優(yōu)先的匹配，如用ab??c 來匹配ac，程序先匹配a，成功然后到b??，這時候會放棄量詞優(yōu)先，跳過b的匹配先匹配c，這樣就匹配成功結束，沒有了之前的回溯過程。

再看一下不成功的匹配，讓ab?x 來匹配abc，你會發(fā)現(xiàn)這次程序匹配a，然后嘗試b，b成了然后嘗試c，c不行回溯到不匹配b的狀態(tài)嘗試匹配x，依然無法匹配。然后回溯，然后移動起始位置從b開始嘗試，不成功再嘗試從c開始這樣最后得出無法匹配的報告。

總的來看，就是你寫的正則需要注意盡量避免回溯和確定你的正則什么地方需要回避優(yōu)先匹配的原則這兩點。上邊例子非常簡單，但是如果避免回溯就能把程序的時間復雜度從平方級O(n*n)降到線性的O(n)，當然這是理想狀態(tài)。

*號和+號的回溯類似上述過程，比如x*，就可以看成x?x?x?x?……這樣或者(x(x(x…?)?)?)? 這樣。試想這樣迭代的深入了很多層，突然來一個不能匹配的x，這是需要一層層向前回溯的。還有就是如果匹配.*[0-9]，這樣的表達式，首先這個匹配會先匹配.*，這使它能匹配完整的整個字符串，然后再一步步回溯，把退回的字符來匹配是否是數(shù)字，其實是可以直接匹配一個數(shù)字的。所以上邊提到.*這樣的通配符，如果非必須，就不要寫這樣的通配符。

另外DFA是不支持忽略優(yōu)先的，只支持匹配優(yōu)先。并且.*這一貪婪特點十分容易忽略，使用不當會得到我們未必需要的結果。比如我們想匹配（.*）括號內(nèi)的內(nèi)容，目標串是 abcd(aaaa)efg(ggg)h，根據(jù).*的天性，會從匹配到的第一個（開始一直匹配到行尾，這時候再根據(jù)）的需求一個字符一個字符的退還以期能匹配），問題就出現(xiàn)了，最終匹配得到的結果是(aaaa)efg(ggg)，這卻不是我們期望的結果。事實上我們需要的正則表達式是([^()]*)。這種錯誤尤其小心發(fā)生在html標簽里，像b>123/b>456b>789/b>，如果你要匹配替換的話，你會錯的很離譜。但是你過你嘗試使用類似([^()]*)這樣的方法，拜托，請你思考一下問題，你這樣會錯的更離譜。比如b>123/b>b/b>, 使用b>[^/b>]/b>，很明顯了，完全無法匹配。你想到辦法了嗎？只需要放棄匹配優(yōu)先這一原則就很好實現(xiàn)了，類似這樣：br />b>.*?/b>，會放棄.*的優(yōu)先嘗試匹配，會先匹配/b>不行的話才讓.*吸收掉?；蛟S你已經(jīng)發(fā)現(xiàn)這樣做仍然有問題，因為針對 b>123b>456/b>,這匹配結果仍然不會是我們所喜歡的，因為匹配回來的是 b>123b>456/b> ，而我們期望得到的是b>456/b>。比較好的解決辦法是使用正則里的環(huán)視功能，需要了解的另行google。

上邊介紹了優(yōu)先嘗試和跳過嘗試兩種模式，使用得當是有助于正則優(yōu)化的，還有一種模式是固化分組（?> expression ）。具體說固化分組與正常的匹配沒有任何差別，但是expression匹配成功的話，會固化這一結果，放棄任何備選狀態(tài)?？匆粋€實例：\w+: ，讓他嘗試匹配helloworld，我們一眼都能看出這是無法匹配的，因為它并不含冒號，為了對比固化匹配，我們還是描述一下這個過程：首先\w會匹配到字符串結束，然后嘗試匹配：號，明顯的d不能匹配，所以/w需要退回下個字符讓：號來匹配，r也不行，最終退到h還是無法匹配然后報告無法匹配這一結果。如果你使用固化分組模式的話(?>\w+):來匹配helloworld的匹配過程：首先會匹配到行尾，然后發(fā)現(xiàn)無法匹配冒號，報告匹配不成功。因為我們知道\w是無法匹配符號的，所以如果\w能夠匹配的內(nèi)容，肯定不會是冒號，所以就沒必要保留\w產(chǎn)生的備選狀態(tài)讓匹配過程產(chǎn)生回溯，固化分組能很好的消除這些備選狀態(tài)。你如果想嘗試，請確保你的工具是支持正則的固化分組。

還有一種占有量詞優(yōu)先：?+ , *+ , ++ , {m,n}+ 。這種模式匹配，量詞會優(yōu)先匹配，與量詞優(yōu)先匹配不同的是這種模式下的量詞匹配的部分不會退回，也就是會移除量詞匹配過程中產(chǎn)生的備選模式。

多結構的匹配類似 a|b|c 這樣的，傳統(tǒng)的NFA都會執(zhí)行順序匹配，每一分支都會窮盡所有備選狀態(tài)。這一有序匹配的特點是能夠發(fā)掘一點優(yōu)化方法的，就是讓匹配成功可能性大的情況盡量放前邊。

上邊說了很多，大多多是跟NFA相關的，正則優(yōu)化的許多工作也就是針對NFA引擎而作的。DFA和NFA在預編譯階段都是把正則表達式轉(zhuǎn)化成各自適合自己算法的規(guī)則式，只是DFA需要較多的內(nèi)存，別且較NFA慢一些，但是正式匹配執(zhí)行的過程中DFA是快于NFA的，甚至有些時候你正則表達式寫的不好，NFA還會陷入無法結束匹配的尷尬境況。但是NFA依然存在依然主流的原因還是它能夠提供DFA不能提供的功能的。比如上邊剛才提到的種種匹配模式，都是DFA不能提供的。

NFA和DFA并非是不能并存的，有些工具是兼具兩種匹配引擎的，來使自身具備DFA的高效和NFA的多功能的。比如GNU的grep和awk，在完成是否匹配的任務的時候使用高效的DFA引擎，完成復雜任務的時候也是盡量使用DFA，如果功能上無法滿足需要就切換成NFA引擎。

上邊算是比較混亂的介紹了DFA和NFA的正則引擎的一些知識和正則優(yōu)化的例子。我們也知道了針對DFA引擎的正則式?jīng)]有太多優(yōu)化策略的，有的是你在書寫正則表達式時的盡可能的準確和盡可能少的匹配嘗試。針對NFA引擎的正則表達式我們是有較大優(yōu)化空間的，但是在這個前邊你要區(qū)分你所使用的工具是基于傳統(tǒng)的NFA還是POSIX NFA。有些問題可能只針對某一引擎存在，對另一種卻沒太大影響。

避免回溯，更要避免指數(shù)級增長的回溯。比如表達式 ([^/]+)*：每次匹配一個字符都要考慮是應該屬于+量詞還是屬于*量詞，這樣如果匹配一個長度為10的字符串，這樣需要回溯1023次，第一次不算回溯，這是2的指數(shù)級增長的速度，如果這個字符串增長到20個，就超過了一百萬種可能，時常若干秒，如果是30個，就超過十億中可能，你要跑數(shù)小時，如果是字符串長超過40個，那要請你等一年多了。這其實給了我們一種判別自己所使用的工具用的正則引擎的所屬：
1、如果某個表達式即便不能匹配，也能給出結果，那么它可能是DFA，只是可能。
2、如果能夠匹配才能很快給出結果，那是傳統(tǒng)NFA。
3、總是很慢的話，那就是POSIX NFA了。

第一個只是說可能，因為經(jīng)過高級優(yōu)化的NFA是能夠迅速給出結果的。

再有一個是多選結構的回溯代價很高，比如：a|b|c|d|e|f 和 [a-f] ，字符數(shù)組[a-f]只需要做簡單的測試，但是該多選結構在匹配時每個位置都將多出6個備選狀態(tài)以便回溯。

現(xiàn)在很多的正則編譯器會進行許多你不知道的優(yōu)化，但是常識性優(yōu)化如果你注意到總是好的，因為你用的工具是否對這塊進行了優(yōu)化是不確定的。

1.如果你的正則工具支持，在不需要引用括號內(nèi)文本的時候使用非捕獲型括號：(?:expression) 。
2.如果括號是非必須的，請不要加括號。
3.不要濫用字符數(shù)組，比如[.],請直接用\. 。
4.使用錨點^ $ ，這會加速定位。
5.從兩次中提取必須元素，如:x+寫成xx*，a{2,4}寫成aa{0,2}。
6.提取多選結構開頭的相同字符，如the|this 改成th(?:e|is)。（如果你的正則引擎不支持這么使用就改成th(e|is)）；尤其是錨點，一定要獨立出來，這樣很多正則編譯器會根據(jù)錨點進行特別的優(yōu)化: ^123|^abc 改成^(?:123|abc)。同樣的$也盡量獨立出來。
7.多選結構后邊的一個表達式放入多選結構內(nèi)，這樣能夠在匹配任何一個多選結構的時候在不退出多選結構的狀態(tài)下查看后一匹配，匹配失敗的更快。這種優(yōu)化需要謹慎使用。
8.忽略優(yōu)先匹配和優(yōu)先匹配需要你視情況而定。如果你不確定，請使用匹配優(yōu)先，它的速度是比忽略優(yōu)先快的。
9.拆分較大正則表達式成一個個小的正則表達式，這是非常有利于提高效率的。
10.模擬錨點，使用合適的環(huán)視結構來預測合適的開始匹配位置，如匹配十二個月份，可以先預查首字符是否匹配：(?=JFMASOND)(?:Jan|Feb|…|Dec)。這種優(yōu)化請根據(jù)實際情況使用，有時候環(huán)視結構開銷可能更大。
11.很多情況下使用固化分組和占有優(yōu)先量詞能夠極大提高速度。
12.避免像(this|that)*這樣的幾乎無盡的匹配。上邊提到的 (…+)*也類似。
13.如果能簡單的匹配大幅縮短目標字符串，可以進行多次正則匹配，經(jīng)過實踐十分有效。
ps：行文可能比較混亂，主要參考[精通正則表達式（第三版）](美)Jeffrey.E.F.Friedl 這本書，另外也看了兩篇別人的blog，基本上這本書函蓋完了。

您可能感興趣的文章:

js中將字符串轉(zhuǎn)換成json的三種方式
jqeury eval將字符串轉(zhuǎn)換json的方法
json對象轉(zhuǎn)字符串如何實現(xiàn)
JS解析json數(shù)據(jù)并將json字符串轉(zhuǎn)化為數(shù)組的實現(xiàn)方法
Json對象與Json字符串互轉(zhuǎn)(4種轉(zhuǎn)換方式)
淺析Js(Jquery)中,字符串與JSON格式互相轉(zhuǎn)換的示例(直接運行實例)
jQuery怎么解析Json字符串(Json格式/Json對象)
js 將json字符串轉(zhuǎn)換為json對象的方法解析
json的定義、標準格式及json字符串檢驗
PHP處理JSON字符串key缺少雙引號的解決方法
正則表達式優(yōu)化JSON字符串的技巧

標簽：衡水大理蚌埠棗莊廣元萍鄉(xiāng) 江蘇衢州

巨人網(wǎng)絡通訊聲明：本文標題《正則表達式的優(yōu)化全面詳解( 三江小渡)》，本文關鍵詞；如發(fā)現(xiàn)本文內(nèi)容存在版權問題，煩請?zhí)峁┫嚓P信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡，涉及言論、版權與本站無關。

佳木斯湛栽影视文化发展公司

正則表達式的優(yōu)化全面詳解( 三江小渡)

QQ咨詢

電話咨詢