东京热无码aⅴ一区二区,91香蕉app下载安装无限看,日本aa大片在线播放免费看

主頁(yè) > 知識(shí)庫(kù) > 正則表達(dá)式的優(yōu)化全面詳解( 三江小渡)

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

就像之前寫(xiě)的mysql全面優(yōu)化詳解一樣，就是因?yàn)檫@樣工具應(yīng)用十分廣泛，所以對(duì)這樣的工具全面的進(jìn)行優(yōu)化策略總結(jié)是非常劃算的，因?yàn)闊o(wú)論你是PHP、Perl、Python、C++、C#、Java等等語(yǔ)言的程序員，你都是有非常大可能用上Mysql、正則表達(dá)式這樣的工具的。

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

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

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

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

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

由上邊對(duì)DFA和NFA的介紹，我們知道他們之間的差異，簡(jiǎn)單來(lái)說(shuō)就是NFA是表達(dá)式主導(dǎo)引擎，DFA是文本主導(dǎo)引擎。一般來(lái)說(shuō)：DFA類(lèi)引擎只會(huì)對(duì)目標(biāo)字符串的每個(gè)字符匹配一次，但是NFA則會(huì)回溯，文本主導(dǎo)的DFA會(huì)比表達(dá)式主導(dǎo)的NFA快一些。

細(xì)心思考的可能會(huì)注意到了，如何盡可能的回避NFA的回溯，將會(huì)是我們針對(duì)正則NFA引擎的優(yōu)化的一大問(wèn)題。這中間還有一個(gè)是否忽略?xún)?yōu)先匹配的問(wèn)題，也是需要優(yōu)化的一點(diǎn)。關(guān)于優(yōu)先匹配也做一個(gè)簡(jiǎn)單的解釋?zhuān)驗(yàn)樯线呎f(shuō)的普適規(guī)則里也說(shuō)到這個(gè)點(diǎn)。如果匹配到一個(gè)位置，需要做嘗試匹配或者跳過(guò)匹配這樣的選擇的時(shí)候，對(duì)于量詞匹配，引擎會(huì)優(yōu)先作出進(jìn)行嘗試行為，而忽略量詞優(yōu)先的時(shí)候則進(jìn)行跳過(guò)嘗試匹配。舉例來(lái)說(shuō)這兩點(diǎn)如何工作的和為什么是需要優(yōu)化的地方：

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

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

再來(lái)看忽略?xún)?yōu)先的匹配，如用ab??c 來(lái)匹配ac，程序先匹配a，成功然后到b??，這時(shí)候會(huì)放棄量詞優(yōu)先，跳過(guò)b的匹配先匹配c，這樣就匹配成功結(jié)束，沒(méi)有了之前的回溯過(guò)程。

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

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

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

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

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

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

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

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

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

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

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

第一個(gè)只是說(shuō)可能，因?yàn)榻?jīng)過(guò)高級(jí)優(yōu)化的NFA是能夠迅速給出結(jié)果的。

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

現(xiàn)在很多的正則編譯器會(huì)進(jìn)行許多你不知道的優(yōu)化，但是常識(shí)性?xún)?yōu)化如果你注意到總是好的，因?yàn)槟阌玫墓ぞ呤欠駥?duì)這塊進(jìn)行了優(yōu)化是不確定的。

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

您可能感興趣的文章:

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

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

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

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

QQ咨詢(xún)

電話(huà)咨詢(xún)