西西軟件下載最安全的下載網(wǎng)站、值得信賴的軟件下載站!

首頁編程開發(fā)其它知識 → 精通正則表達(dá)式之正則引擎

精通正則表達(dá)式之正則引擎

相關(guān)軟件相關(guān)文章發(fā)表評論 來源:西西整理時(shí)間:2013/2/6 11:20:47字體大。A-A+

作者:劉亞運(yùn)點(diǎn)擊:0次評論:0次標(biāo)簽: 正則

  • 類型:電子教程大小:9.5M語言:中文 評分:7.5
  • 標(biāo)簽:
立即下載

這一篇就重點(diǎn)講解正則表達(dá)式的核心——正則引擎。

1、正則引擎

正則引擎主要可以分為基本不同的兩大類:一種是DFA(確定型有窮自動機(jī)),另一種是NFA(不確定型有窮自動機(jī))。DFA和NFA都有很長的歷史,不過NFA的歷史更長一些。使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep的多數(shù)版本,甚至還有某些版本的egrep和awk。而采用DFA的工具主要有egrep、awk、lex和flex。也有一些系統(tǒng)采用了混合引擎,它們會根據(jù)任務(wù)的不同選擇合適的引擎(甚至對同一表達(dá)式中的不同部分采用不同的引擎,以求得功能與速度之間的平衡)

NFA和DFA都發(fā)展了很多年了,產(chǎn)生了許多不必要的變體,結(jié)果,現(xiàn)在的情況比較復(fù)雜。POSIX標(biāo)準(zhǔn)的出臺,就是為了規(guī)范這種現(xiàn)象,POSIX標(biāo)準(zhǔn)清楚地規(guī)定了引擎中應(yīng)該支持的元字符和特性。除開表面細(xì)節(jié)不談,DFA已經(jīng)符合新的標(biāo)準(zhǔn),但是NFA風(fēng)格的結(jié)果卻與此不一,所以NFA需要修改才能符合標(biāo)準(zhǔn)。這樣一來,正則引擎可以粗略地分為三類:DFA;傳統(tǒng)型NFA;POSIX NFA。

我們來看使用`to(nite|knight|night)`來匹配文本‘…tonight…’的一種辦法。正則表達(dá)式從我們需要檢查的字符串的首位(這里的位置不是指某個(gè)字符的位置,而是指兩個(gè)相鄰字符的中間位置)開始,每次檢查一部分(由引擎查看表達(dá)式的一部分),同時(shí)檢查“當(dāng)前文本”(此位置后面的字符)是否匹配表達(dá)式的當(dāng)前部分。如果是,則繼續(xù)表達(dá)式的下一部分,如果不是,那么正則引擎向后移動一個(gè)字符的位置,繼續(xù)匹配,如此繼續(xù),直到表達(dá)式的所有部分都能匹配,即整個(gè)表達(dá)式能夠匹配成功。在此例子中,由于表達(dá)式的第一個(gè)元素是`t`,正則引擎將會從需要匹配的字符串的首位開始重復(fù)嘗試匹配,直到在目標(biāo)字符中找到‘t’為止。之后就檢查緊隨其后的字符是否能由`o`匹配,如果能,就檢查下面的元素。下面是`nite`或者`knight`或者`night`。引擎會依次嘗試這3種可能。嘗試`nite`的過程與之前一樣:“嘗試匹配`n`,然后是`i`,然后是`t`,最后是`e`”。如果這種嘗試失敗,引擎就會嘗試另一種可能,如此繼續(xù)下去,直到匹配成功或是報(bào)告失敗。表達(dá)式的控制權(quán)在不同的元素之間轉(zhuǎn)換,所以我們可以稱它為“表達(dá)式主導(dǎo)”。

與表達(dá)式主導(dǎo)的NFA不同,DFA引擎在掃描字符串時(shí)會記錄“當(dāng)前有效”的所有匹配可能。在此例中引擎會對‘…tonight…’進(jìn)行掃描,當(dāng)掃描到t時(shí),引擎會在表達(dá)式里面的t上坐上一個(gè)標(biāo)記,記錄當(dāng)前位置可以匹配,然后繼續(xù)掃描o,同樣可以匹配,繼續(xù)掃描到n,發(fā)現(xiàn)有兩個(gè)可以匹配(knight被淘汰),當(dāng)掃描到g時(shí)就只剩下一個(gè)可以匹配了,當(dāng)h和t匹配完成后,引擎發(fā)現(xiàn)匹配已經(jīng)成功,報(bào)告成功。我們稱這種方式為“文本主導(dǎo)”,因?yàn)樗鼟呙璧淖址械拿總(gè)字符都對引擎進(jìn)行了控制。

從它們匹配的邏輯上我們不難發(fā)現(xiàn):一般情況下,文本主導(dǎo)的DFA引擎要快一些。正則表達(dá)式主導(dǎo)的NFA引擎,因?yàn)樾枰獙ν瑯拥奈谋緡L試不同的子表達(dá)式匹配,可能會浪費(fèi)時(shí)間。在NFA的匹配過程中,目標(biāo)文本的某個(gè)字符可能會被正則表達(dá)式反復(fù)檢測很多遍(每一個(gè)字符被檢測的次數(shù)不確定,所以NFA叫做不確定型有窮自動機(jī))。相反,DFA引擎在匹配過程中目標(biāo)文本中的每個(gè)字符只會最多檢查一遍(每個(gè)字符被檢測的次數(shù)相對確定,所以DFA叫做確定型有窮自動機(jī))。由于DFA取得一個(gè)結(jié)果可能有上百種途徑,但是因?yàn)镈FA能夠同時(shí)記錄它們,選擇哪一個(gè)表達(dá)式并無區(qū)別,也就是說你改變寫法對于效率是沒有影響的。而NFA是表達(dá)式主導(dǎo),改變表達(dá)式的編寫方式可能會節(jié)省很多功夫。

所以后面我們講解的知識都是涉及的NFA的。

2、回溯

何為回溯?先來看一個(gè)例子,我們使用`a(b|c)d`去嘗試匹配字符串“cabb”,正則引擎首先處于字符'c'的前面,開始查看正則表達(dá)式,發(fā)現(xiàn)第一個(gè)為a,不能匹配,然后引擎移動到'c'和'a'之間的位置,繼續(xù)查看表達(dá)式,發(fā)現(xiàn)a可以匹配,然后查看表達(dá)式的后面,發(fā)現(xiàn)有兩條路,引擎會做好標(biāo)記,選擇其中一條路,加入選擇區(qū)匹配b,發(fā)現(xiàn)字符'a'后面就是'b',可以匹配,然偶再次查看表達(dá)式,需要匹配d,發(fā)現(xiàn)字符串后面是'b',不符合條件,這條路失敗,引擎會自動回到之前做選擇的地方,這里就稱作一次回溯。那么引擎會嘗試匹配a后面的c,發(fā)現(xiàn)'a'后面是'b',這條路也走不通,沒有其它的路線了,然后引擎又會移動位置,現(xiàn)在到了'a'和'b'之間,引擎回去嘗試匹配表達(dá)式的a,發(fā)現(xiàn)當(dāng)前位置后面是'b',無法匹配,引擎又開始向后移動位置,直到移動到最后,發(fā)現(xiàn)沒有一次匹配成功,然后引擎才會報(bào)告失敗。而如果中間又一次成功完整匹配了,引擎會自動停止(傳統(tǒng)型NFA會停止,而POSIX NFA還會繼續(xù),把所有可能匹配完,選擇其中一個(gè)),報(bào)告成功。

現(xiàn)在應(yīng)該知道回溯其實(shí)就是引擎在匹配字符串的過程中出現(xiàn)多選的情況,當(dāng)其中一種選擇無法匹配時(shí)再次選擇另種的過程叫做回溯。其實(shí)我們在優(yōu)化正則表達(dá)式的時(shí)候就是考慮的盡量減少回溯的次數(shù)。

2.1回溯 匹配優(yōu)先和忽略優(yōu)先

《精通正則表達(dá)式》這本書里面叫做匹配優(yōu)先和忽略優(yōu)先,網(wǎng)上有很多人叫做貪婪模式和非貪婪模式,反正都一樣,叫法無所謂。

匹配優(yōu)先量詞我們已經(jīng)學(xué)習(xí)了,就是?、+、*、{}這四個(gè)。匹配優(yōu)先量詞在匹配的時(shí)候首先會嘗試匹配,如果失敗后回溯才會選擇忽略。比如`ab?`匹配"abb"會得到"abb"。這里當(dāng)匹配成功'a'后,引擎有兩個(gè)選擇,一個(gè)是嘗試匹配后面的b,一個(gè)是忽略后面的b,而由于是匹配優(yōu)先,所以引擎會嘗試匹配b,發(fā)現(xiàn)可以匹配,得到了"ab",接著引擎又一次遇到了同樣的問題,還是會選擇先匹配,所以得到了"abb",接著引擎發(fā)現(xiàn)后面沒有字符了,就上報(bào)匹配成功。

忽略優(yōu)先量詞使用的是在?、+、*、{}后面添加?組成的,忽略優(yōu)先在匹配的時(shí)候首先會嘗試忽略,如果失敗后回溯才會選擇嘗試。比如`ab??`匹配“abb”會得到‘a(chǎn)’而不是“ab”。當(dāng)引擎匹配成功a后,由于是忽略優(yōu)先,引擎首先選擇不匹配b,繼續(xù)查看表達(dá)式,發(fā)現(xiàn)表達(dá)式結(jié)束了,那么引擎就直接上報(bào)匹配成功。

例子1:

            var reg1=/ab?/;
            var reg2=/ab??/;
            var result1=reg1.exec("abc");
            var result2=reg2.exec("abc");
            document.write(result1+" "+result2);

結(jié)果:

例子2:

            var reg1=/ab+/;
            var reg2=/ab+?/;
            var result1=reg1.exec("abbbc");
            var result2=reg2.exec("abbbc");
            document.write(result1+" "+result2);

結(jié)果:

例子3:

            var reg1=/ab*/;
            var reg2=/ab*?/;
            var result1=reg1.exec("abbbc");
            var result2=reg2.exec("abbbc");
            document.write(result1+" "+result2);

結(jié)果:

例子4:

            var reg1=/ab{2,4}/;
            var reg2=/ab{2,4}?/;
            var result1=reg1.exec("abbbbbbc");
            var result2=reg2.exec("abbbbbbc");
            document.write(result1+" "+result2);

結(jié)果:

下面我們來看稍微復(fù)雜一點(diǎn)的匹配優(yōu)先的情況,使用`c.*d`去匹配字符串“caaadc”,我們發(fā)現(xiàn)當(dāng)c匹配成功后,`.*`會一直匹配到最后的'c',然后再去匹配表達(dá)式里面的d,發(fā)現(xiàn)后面沒有字符可以匹配,這是就會回溯到`.*`匹配'c'的地方,選擇`.*`忽略'c',那么c就留給后面了,但是發(fā)現(xiàn)還是不能匹配d,又得回溯到匹配d的位置,`.*`再次選擇忽略匹配,發(fā)現(xiàn)就可以匹配d了,這是停止匹配,上報(bào)匹配成功,所以結(jié)果是“caaad”。

再看一個(gè)忽略優(yōu)先的情況,使用`a.*?d`去匹配字符串“caaadc”,我們發(fā)現(xiàn)當(dāng)匹配成功a時(shí),引擎有兩條路,會選擇忽略匹配,直接匹配d,但是字符串“caaadc”的a后面是a,所以失敗,回溯到之前的選擇,懸著匹配,獲得“aa”,然后又一次遇到同樣的問題,引擎選擇忽略匹配,發(fā)現(xiàn)后面又是a,不能匹配d,再次回溯,選擇匹配,得到“aaa”,這一次忽略匹配后發(fā)現(xiàn)后匹配成功了d,那么上報(bào)成功,得到“aaad”。

希望這幾個(gè)例子能夠大概講解清楚這兩種不同的情況吧!

2.2回溯 環(huán)視

環(huán)視結(jié)構(gòu)不匹配任何字符,只匹配文本中的特定位置,這一點(diǎn)和單詞分界符`\b`、`^`、`$`相似。

`(?=)`稱作肯定順序環(huán)視,如`x(?=y)`是指匹配x,僅當(dāng)后面緊跟y時(shí),如果符合匹配,則只有x會被記住,y不會被記住。

`(?!)`稱作否定順序環(huán)視,如`x(?!y)`是指匹配x,僅當(dāng)后面不緊跟y時(shí),如果符合匹配,則只有x會被記住,y不會被記住。

在環(huán)視內(nèi)部的備用狀態(tài)一旦退出環(huán)視范圍后立即清除,外部回溯不能回溯到環(huán)視內(nèi)部的備用狀態(tài)。使用`ab\w+c`和`ab(?=\w+)c`來匹配字符串“abbbbc”,第一個(gè)表達(dá)式會成功,而第二個(gè)表達(dá)式會失敗。

例子1:

            var reg=/ab(?=c)/;
            var result1=reg.exec("abcd");
            var result2=reg.exec("abbc");
            document.write(result1+" "+result2);

結(jié)果:

例子2:

            var reg=/ab(?!c)/;
            var result1=reg.exec("abdc");
            var result2=reg.exec("abcd");
            document.write(result1+" "+result2);

結(jié)果:

例子3:

            var reg1=/ab\w+bc/;
            var reg2=/ab(?=\w+)c/;
            var result1=reg1.exec("abbbbbcb");
            var result2=reg2.exec("abbbbbbc");
            document.write(result1+" "+result2);

結(jié)果:

明顯自己都覺得環(huán)視沒講解好,還有肯定逆序環(huán)視和否定逆序環(huán)視,以及固化分組這些都是在解決回溯的問題,回溯算是影響表達(dá)式的罪魁禍?zhǔn)装!這幾個(gè)內(nèi)容看啥時(shí)候有時(shí)間在細(xì)講吧!寫著寫著才發(fā)現(xiàn)想讓人看懂不是那么容易的!體諒一下哦!

3、打造高效正則表達(dá)式

Perl、Java、.NET、Python和PHP,以及我們熟悉的JS使用的都是表達(dá)式主導(dǎo)的NFA引擎,細(xì)微的改變就可能對匹配的結(jié)果產(chǎn)生重大的影響。DFA中不存在的問題對NFA來說卻很重要。因?yàn)镹FA引擎允許用戶進(jìn)行精確控制,所以我們可以用心打造正則表達(dá)式。

3.1先邁好使的腿

對于一般的文本來說,字母和數(shù)字比較多,而一些特殊字符很少,一個(gè)簡單的改動就是調(diào)換兩個(gè)多選分支的順序,也許會達(dá)到不錯(cuò)的效果。如使用`(:|\w)*`和`(\w|:)*`來匹配字符串“ab13_b:bbbb:c34d”,一般說來冒號在文本中出現(xiàn)的次數(shù)少于字母數(shù)字,此例中第一個(gè)表達(dá)式效率低于第二個(gè)。

例子:

            var reg1=/(:|\w)*/;
            var reg2=/(\w|:)*/;
            var result1=reg1.exec("ab13_b:bbbb:c34d");
            var result2=reg2.exec("ab13_b:bbbb:c34d");
            document.write(result1+" "+result2);

3.2無法匹配時(shí)

對于無法匹配的文本,可能它在匹配過程中任然會進(jìn)行許多次工作,我們可以通過某種方式提高報(bào)錯(cuò)的速度。如使用`”.*”!`和`”[^”]*”!`去匹配字符串“The name “McDonald’s” is said “makudonarudo” in Japanese”。我們可以看出第一種回溯的次數(shù)明顯多于第二種。

3.3多選結(jié)構(gòu)代價(jià)高

多選結(jié)構(gòu)是回溯的主要原因之一。例如使用`u|v|w|x|y|z`和`[uvwxyz]`去匹配字符串“The name “McDonald’s” is said “makudonarudo” in Japanese”。最終`[uvwxyz]`只需要34次嘗試就能夠成功,而如果使用`u|v|w|x|y|z`則需要在每個(gè)位置進(jìn)行6次回溯,在得到同樣結(jié)果前總共有206次回溯。

少用多選結(jié)構(gòu)。

3.4消除無必要的括號

如果某種實(shí)現(xiàn)方式認(rèn)為`(?:.)*`與`.*`是完全等價(jià)的,那么請使用后者替換前者,`.*`實(shí)際上更快一些。

3.5消除不需要的字符組

只包含單個(gè)字符的字符組有點(diǎn)多余,因?yàn)樗凑兆址M來處理,而這么做完全沒有必要。所以例如`[.]`可以寫成`\.`。

3.6量詞等價(jià)轉(zhuǎn)換

有人習(xí)慣用`\d\d\d\d`,也有人習(xí)慣使用量詞`\d{4}`。對于NFA來說效率上時(shí)有差別的,但工具不同結(jié)果也不同。如果對量詞做了優(yōu)化,則`\d{4}`會更快一些,除非未使用量詞的正則表達(dá)式能夠進(jìn)行更多的優(yōu)化。

3.7使用非捕獲型括號

如果不需要引用括號內(nèi)的文本,請使用非捕獲型括號`(?:)`。這樣不但能夠節(jié)省捕獲的時(shí)間,而且會減少回溯使用的狀態(tài)的數(shù)量。由于捕獲需要使用內(nèi)存,所以也減少了內(nèi)存的占用。

3.8提取必須的元素

由于很多正則引擎存在著局部優(yōu)化,主要是依靠正則引擎的能力來識別出匹配成功必須的一些文本,所以我們手動的將這些文本“暴露”出來可以提高引擎識別的可能性。 `xx*`替代`x+`能夠暴露必須的‘x’。`-{2,4}`可以寫作`--{0,2}`。用`th(?:is|at)`代替`(?:this|that)`就能暴露必須的`th`。

3.9忽略優(yōu)先和匹配優(yōu)先

通常,使用忽略優(yōu)先量詞還是匹配優(yōu)先量詞取決于正則表達(dá)式的具體需求。例如`^.*:`完全不同于`^.*?:`,因?yàn)榍罢咂ヅ涞阶詈蟮拿疤,而后者匹配到第一個(gè)冒號。但是如果目標(biāo)數(shù)據(jù)中只包含一個(gè)冒號,兩個(gè)表達(dá)式就沒有區(qū)別了。不過并不是任何時(shí)候優(yōu)劣都如此分明,大的原則是:如果目標(biāo)字符串很長,而你認(rèn)為冒號會比較接近字符串的開頭,就使用忽略優(yōu)先量詞;如果你認(rèn)為冒號在接近字符串的末尾位置,你就使用匹配優(yōu)先。如果數(shù)據(jù)是隨機(jī)的,又不知道冒號在哪頭,就使用匹配優(yōu)先量詞,因?yàn)樗鼈兊膬?yōu)化一般來說都要比其他量詞要好一些。

3.10拆分正則表達(dá)式

有時(shí)候,應(yīng)用多個(gè)小正則表達(dá)式的速度比一個(gè)大正則表達(dá)式要快得多。比如你希望檢查一個(gè)長字符串中是否包含月份的名字,依次檢查`January`、`February`、`March`之類的速度要比`January|..|….`快得多。

 還有很多優(yōu)化的方法見《精通正則表達(dá)式》,我在這里只是列舉了部分容易理解的方式。其實(shí)只要理解正則引擎室如何匹配的,理解回溯的邏輯,你就可以對自己寫的表達(dá)式進(jìn)行相應(yīng)的優(yōu)化了!

    相關(guān)評論

    閱讀本文后您有什么感想? 已有人給出評價(jià)!

    • 8 喜歡喜歡
    • 3 頂
    • 1 難過難過
    • 5 囧
    • 3 圍觀圍觀
    • 2 無聊無聊

    熱門評論

    最新評論

    發(fā)表評論 查看所有評論(0)

    昵稱:
    表情: 高興 可 汗 我不要 害羞 好 下下下 送花 屎 親親
    字?jǐn)?shù): 0/500 (您的評論需要經(jīng)過審核才能顯示)
    推薦文章

    沒有數(shù)據(jù)