PHP正則表達(dá)式的效率 回溯與固化分組
更新時(shí)間：2011年04月12日 21:31:30 作者：
上文中，我們聊到了一點(diǎn)關(guān)于PHP中（NFA PCRE）正則表達(dá)式匹配優(yōu)先量詞，忽略優(yōu)先量詞的匹配原理了。那么上文留下的問(wèn)題，您的答案是什么呢？
先來(lái)看下問(wèn)題。
字符串
$str = '<script>123456</script>';
正則表達(dá)式為
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
這三個(gè)正則，分別會(huì)造成幾次回溯呢？？
答案：
$strRegex1 = '%<script>.+<\/script>%'; //9次，記得區(qū)別轉(zhuǎn)義符號(hào)。
$strRegex2 = '%<script>.+?<\/script>%'; //5次
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%'; //7次
對(duì)于第一種貪婪匹配的匹配規(guī)則，回溯的9次是正則【】對(duì)字符串“”匹配時(shí)，構(gòu)成的回溯，回溯的次數(shù)，恰好是字符串的長(zhǎng)度。
第二種非貪婪匹配規(guī)則，回溯5次，是正則【.+?】對(duì)字符串“123456”匹配時(shí)構(gòu)成的回溯。回溯的次數(shù)，為字符串長(zhǎng)度減去最小次數(shù)。也就是6-1=5次。如果正則表達(dá)式為【.*?】那么，回溯次數(shù)就是6次了。
第三種正則是零寬斷言，或者叫環(huán)視。（暫且不說(shuō)。）
在NFA正則引擎中，回溯是他的靈魂，所以，不管是貪婪，非貪婪，環(huán)視等寫法中肯定會(huì)有回溯的出現(xiàn)的，這個(gè)我們無(wú)法避免（用詞不太準(zhǔn)確），但是，我們可以減少回溯的次數(shù)，或者保護(hù)其中一部分匹配的規(guī)則不進(jìn)行回溯。
對(duì)于上篇BLOG上提到的鳥(niǎo)哥談到一個(gè)非貪婪引起的大量回溯問(wèn)題，大家可以知道，回溯，確實(shí)是浪費(fèi)資源的罪魁禍?zhǔn)祝敲?，我們能否不讓其回溯呢?
答案是肯定的，NFA引擎中，有個(gè)概念，叫固化分組。引用一下書上的概念
具體來(lái)說(shuō)，使用「(?>…)」的匹配與正常的匹配并無(wú)差別，但是如果匹配進(jìn)行到此結(jié)構(gòu)之后（也就是，進(jìn)行到閉括號(hào)之后），那么此結(jié)構(gòu)體中的所有備用狀態(tài)都會(huì)被放棄。也就是說(shuō)，在固化分組匹配結(jié)束時(shí)，它已經(jīng)匹配的文本已經(jīng)固化為一個(gè)單元，只能作為整體而保留或放棄。括號(hào)內(nèi)的子表達(dá)式中未嘗試過(guò)的備用狀態(tài)都不復(fù)存在了，所以回溯永遠(yuǎn)也不能選擇其中的狀態(tài)（至少是，當(dāng)此結(jié)構(gòu)匹配完成時(shí)，“鎖定（locked in）”在其中的狀態(tài)）。
那么，固化分組到底有什么用處呢？我們來(lái)舉個(gè)例子。（找不到合適的例子，俺只好借用一下書上的例子了）
比如要處理一批數(shù)據(jù)，原來(lái)格式為123.456，后來(lái)因?yàn)楦↑c(diǎn)數(shù)顯示問(wèn)題，部分?jǐn)?shù)據(jù)格式變?yōu)?23.456000000789這種，，要求做到只保留小數(shù)點(diǎn)后面2-3位，但是，最后一位不能為0，這個(gè)正則如何寫呢？（下面直接考慮小數(shù)點(diǎn)后面的數(shù)字），寫出正則之后，我們還要用這個(gè)正則去匹配數(shù)據(jù)，把原來(lái)的數(shù)據(jù)替換成匹配的結(jié)果。
首先，我們可以立刻寫出這樣的正則【\.\d\d[1-9]?\d*】，PHP代碼為
$str = preg_replace('\.(\d\d[1-9]?)\d*','\\1',$str); //匹配結(jié)果的group1進(jìn)行反向引用
很明顯，這種寫法，對(duì)于部分?jǐn)?shù)據(jù)格式為123.456的這種格式，白白的處理了一遍，為了提高效率，我們還要對(duì)這個(gè)正則進(jìn)行處理。從123.456這個(gè)字符串跟其他的比較一下，我們發(fā)現(xiàn)，是疑問(wèn)123.456這個(gè)數(shù)據(jù)后面沒(méi)數(shù)字了，所以，白白處理一遍。那好辦，我們對(duì)這個(gè)正則改造一下，把后面的量詞*改成+，這樣對(duì)于123.45 小數(shù)點(diǎn)后面1，2位數(shù)字的，不會(huì)去白白處理，而且，對(duì)三位以上數(shù)字的，處理正常。其PHP代碼為
$str = preg_replace('\.(\d\d[1-9]?)\d+','\\1',$str);
好了，這個(gè)正則真的沒(méi)問(wèn)題嗎？？確定嗎？上篇博文，我們了解了匹配原理，那么，我們也分析一下這個(gè)正則的匹配過(guò)程吧。
字符串"123.456",正則表達(dá)式為【\.(\d\d[1-9]?)\d+】，我們來(lái)看下
首先（小數(shù)點(diǎn)前123不說(shuō)了），【\.】匹配"."，匹配成功，把控制權(quán)給下一個(gè)【\d】，【\d】匹配“4”成功，把控制權(quán)給第二個(gè)【\d】，這個(gè)【\d】匹配“5”成功，然后，把控制權(quán)給了【[1-9]?】，由于量詞是【?】，正則表達(dá)式遵循“量詞優(yōu)先匹配”，而且，此處是【?】，還會(huì)留下一個(gè)回溯點(diǎn)。然后匹配"6"成功，然后把控制權(quán)給【\d+】，【\d+】發(fā)現(xiàn)后面沒(méi)字符了，最遵循“后進(jìn)先出”規(guī)則，回到上一個(gè)回溯點(diǎn)，進(jìn)行匹配，這時(shí)，【[1-9]?】會(huì)交還出其匹配的字符“6”，【[1-9]?】匹配“6”成功。匹配完成了。大家發(fā)現(xiàn)【(\d\d[1-9]?)】匹配的結(jié)果確是"45",并不是我們想要的“456”，“6”被【\d+】匹配去了。那么，我們?cè)撊绾无k呢？ 能否讓【[1-9]?】匹配一旦成功，不進(jìn)行回溯呢？這就用到了我們上面說(shuō)的"固化分組", PHP（preg_replace函數(shù)）中使用的正則引擎支持固化分組，我們根據(jù)固化分組的寫法，可以把代碼改成如下方式
$str = preg_replace('\.(\d\d(?>[1-9]?))\d+','\\1',$str);
改成這樣的話，那字符串“123.456“是不符合要求，不會(huì)被匹配的。那我們就可以實(shí)現(xiàn)我們的要求了。
從上面的例子中，知道了固化分組的作用，那么對(duì)于鳥(niǎo)哥BLOG上寫的那個(gè)非貪婪的回溯問(wèn)題，我們能否也對(duì)其改造，使得其不回溯呢？
先看下鳥(niǎo)哥給的答案
/<script>[^<]*<\/script>/is
鳥(niǎo)哥寫的很精悍。排除“<”之外的所有字符都符合，而且，中間部分不回溯，效率高?？墒牵绻虚g有字符“<“的話（如下代碼）
<script>
if a < b
</script>
那鳥(niǎo)哥的這個(gè)正則就不能匹配，就不能實(shí)現(xiàn)我們想要的功能了。
那我們可以根據(jù) 固化分組、環(huán)視(零寬斷言)來(lái)實(shí)現(xiàn)這個(gè)要求，最后，CFC4N給出的正則以及PHP代碼事例如下
$reg = '%<script>(?>[^<]*)(?>(?!</?script>)<[^<]*)*</script>%is';
$str = str_pad("<script>", 111111, "*"); //字符長(zhǎng)度大于PHP回溯限制的100000
$str .= 'if a < b ; if b > c;</script>'; //隨便加幾個(gè)包含 < > 的測(cè)試字符
$ret = preg_replace($reg, "OK", $str);
print_r($ret); //打印結(jié)果 OK，證明匹配正確
var_dump(preg_last_error()); //上一次匹配錯(cuò)誤。其輸出為 int(0)
嗨，同學(xué)，你看明白了嗎？
以上為小菜CFC4N的愚文，如有錯(cuò)誤，歡迎指出。
字符串
復(fù)制代碼 代碼如下:
$str = '<script>123456</script>';
正則表達(dá)式為
復(fù)制代碼 代碼如下:
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
這三個(gè)正則，分別會(huì)造成幾次回溯呢？？
答案：
復(fù)制代碼 代碼如下:
$strRegex1 = '%<script>.+<\/script>%'; //9次，記得區(qū)別轉(zhuǎn)義符號(hào)。
$strRegex2 = '%<script>.+?<\/script>%'; //5次
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%'; //7次
對(duì)于第一種貪婪匹配的匹配規(guī)則，回溯的9次是正則【】對(duì)字符串“”匹配時(shí)，構(gòu)成的回溯，回溯的次數(shù)，恰好是字符串的長(zhǎng)度。
第二種非貪婪匹配規(guī)則，回溯5次，是正則【.+?】對(duì)字符串“123456”匹配時(shí)構(gòu)成的回溯。回溯的次數(shù)，為字符串長(zhǎng)度減去最小次數(shù)。也就是6-1=5次。如果正則表達(dá)式為【.*?】那么，回溯次數(shù)就是6次了。
第三種正則是零寬斷言，或者叫環(huán)視。（暫且不說(shuō)。）
在NFA正則引擎中，回溯是他的靈魂，所以，不管是貪婪，非貪婪，環(huán)視等寫法中肯定會(huì)有回溯的出現(xiàn)的，這個(gè)我們無(wú)法避免（用詞不太準(zhǔn)確），但是，我們可以減少回溯的次數(shù)，或者保護(hù)其中一部分匹配的規(guī)則不進(jìn)行回溯。
對(duì)于上篇BLOG上提到的鳥(niǎo)哥談到一個(gè)非貪婪引起的大量回溯問(wèn)題，大家可以知道，回溯，確實(shí)是浪費(fèi)資源的罪魁禍?zhǔn)祝敲?，我們能否不讓其回溯呢?
答案是肯定的，NFA引擎中，有個(gè)概念，叫固化分組。引用一下書上的概念
復(fù)制代碼 代碼如下:
具體來(lái)說(shuō)，使用「(?>…)」的匹配與正常的匹配并無(wú)差別，但是如果匹配進(jìn)行到此結(jié)構(gòu)之后（也就是，進(jìn)行到閉括號(hào)之后），那么此結(jié)構(gòu)體中的所有備用狀態(tài)都會(huì)被放棄。也就是說(shuō)，在固化分組匹配結(jié)束時(shí)，它已經(jīng)匹配的文本已經(jīng)固化為一個(gè)單元，只能作為整體而保留或放棄。括號(hào)內(nèi)的子表達(dá)式中未嘗試過(guò)的備用狀態(tài)都不復(fù)存在了，所以回溯永遠(yuǎn)也不能選擇其中的狀態(tài)（至少是，當(dāng)此結(jié)構(gòu)匹配完成時(shí)，“鎖定（locked in）”在其中的狀態(tài)）。
那么，固化分組到底有什么用處呢？我們來(lái)舉個(gè)例子。（找不到合適的例子，俺只好借用一下書上的例子了）
比如要處理一批數(shù)據(jù)，原來(lái)格式為123.456，后來(lái)因?yàn)楦↑c(diǎn)數(shù)顯示問(wèn)題，部分?jǐn)?shù)據(jù)格式變?yōu)?23.456000000789這種，，要求做到只保留小數(shù)點(diǎn)后面2-3位，但是，最后一位不能為0，這個(gè)正則如何寫呢？（下面直接考慮小數(shù)點(diǎn)后面的數(shù)字），寫出正則之后，我們還要用這個(gè)正則去匹配數(shù)據(jù)，把原來(lái)的數(shù)據(jù)替換成匹配的結(jié)果。
首先，我們可以立刻寫出這樣的正則【\.\d\d[1-9]?\d*】，PHP代碼為
復(fù)制代碼 代碼如下:
$str = preg_replace('\.(\d\d[1-9]?)\d*','\\1',$str); //匹配結(jié)果的group1進(jìn)行反向引用
很明顯，這種寫法，對(duì)于部分?jǐn)?shù)據(jù)格式為123.456的這種格式，白白的處理了一遍，為了提高效率，我們還要對(duì)這個(gè)正則進(jìn)行處理。從123.456這個(gè)字符串跟其他的比較一下，我們發(fā)現(xiàn)，是疑問(wèn)123.456這個(gè)數(shù)據(jù)后面沒(méi)數(shù)字了，所以，白白處理一遍。那好辦，我們對(duì)這個(gè)正則改造一下，把后面的量詞*改成+，這樣對(duì)于123.45 小數(shù)點(diǎn)后面1，2位數(shù)字的，不會(huì)去白白處理，而且，對(duì)三位以上數(shù)字的，處理正常。其PHP代碼為
復(fù)制代碼 代碼如下:
$str = preg_replace('\.(\d\d[1-9]?)\d+','\\1',$str);
好了，這個(gè)正則真的沒(méi)問(wèn)題嗎？？確定嗎？上篇博文，我們了解了匹配原理，那么，我們也分析一下這個(gè)正則的匹配過(guò)程吧。
字符串"123.456",正則表達(dá)式為【\.(\d\d[1-9]?)\d+】，我們來(lái)看下
首先（小數(shù)點(diǎn)前123不說(shuō)了），【\.】匹配"."，匹配成功，把控制權(quán)給下一個(gè)【\d】，【\d】匹配“4”成功，把控制權(quán)給第二個(gè)【\d】，這個(gè)【\d】匹配“5”成功，然后，把控制權(quán)給了【[1-9]?】，由于量詞是【?】，正則表達(dá)式遵循“量詞優(yōu)先匹配”，而且，此處是【?】，還會(huì)留下一個(gè)回溯點(diǎn)。然后匹配"6"成功，然后把控制權(quán)給【\d+】，【\d+】發(fā)現(xiàn)后面沒(méi)字符了，最遵循“后進(jìn)先出”規(guī)則，回到上一個(gè)回溯點(diǎn)，進(jìn)行匹配，這時(shí)，【[1-9]?】會(huì)交還出其匹配的字符“6”，【[1-9]?】匹配“6”成功。匹配完成了。大家發(fā)現(xiàn)【(\d\d[1-9]?)】匹配的結(jié)果確是"45",并不是我們想要的“456”，“6”被【\d+】匹配去了。那么，我們?cè)撊绾无k呢？ 能否讓【[1-9]?】匹配一旦成功，不進(jìn)行回溯呢？這就用到了我們上面說(shuō)的"固化分組", PHP（preg_replace函數(shù)）中使用的正則引擎支持固化分組，我們根據(jù)固化分組的寫法，可以把代碼改成如下方式
復(fù)制代碼 代碼如下:
$str = preg_replace('\.(\d\d(?>[1-9]?))\d+','\\1',$str);
改成這樣的話，那字符串“123.456“是不符合要求，不會(huì)被匹配的。那我們就可以實(shí)現(xiàn)我們的要求了。
從上面的例子中，知道了固化分組的作用，那么對(duì)于鳥(niǎo)哥BLOG上寫的那個(gè)非貪婪的回溯問(wèn)題，我們能否也對(duì)其改造，使得其不回溯呢？
先看下鳥(niǎo)哥給的答案
復(fù)制代碼 代碼如下:
/<script>[^<]*<\/script>/is
鳥(niǎo)哥寫的很精悍。排除“<”之外的所有字符都符合，而且，中間部分不回溯，效率高?？墒牵绻虚g有字符“<“的話（如下代碼）
復(fù)制代碼 代碼如下:
<script>
if a < b
</script>
那鳥(niǎo)哥的這個(gè)正則就不能匹配，就不能實(shí)現(xiàn)我們想要的功能了。
那我們可以根據(jù) 固化分組、環(huán)視(零寬斷言)來(lái)實(shí)現(xiàn)這個(gè)要求，最后，CFC4N給出的正則以及PHP代碼事例如下
復(fù)制代碼 代碼如下:
$reg = '%<script>(?>[^<]*)(?>(?!</?script>)<[^<]*)*</script>%is';
$str = str_pad("<script>", 111111, "*"); //字符長(zhǎng)度大于PHP回溯限制的100000
$str .= 'if a < b ; if b > c;</script>'; //隨便加幾個(gè)包含 < > 的測(cè)試字符
$ret = preg_replace($reg, "OK", $str);
print_r($ret); //打印結(jié)果 OK，證明匹配正確
var_dump(preg_last_error()); //上一次匹配錯(cuò)誤。其輸出為 int(0)
嗨，同學(xué)，你看明白了嗎？
以上為小菜CFC4N的愚文，如有錯(cuò)誤，歡迎指出。
相關(guān)文章
正則表達(dá)式下全部符號(hào)，對(duì)于書寫正則表達(dá)式的朋友一定要了解下，才能更好的發(fā)揮正則的作用于閱讀別人的代碼，先從基本來(lái)。2010-07-07
Java中使用正則表達(dá)式處理文本數(shù)據(jù)
正則表達(dá)式就是一個(gè)字符串，但和普通的字符串不同的是，正則表達(dá)式是對(duì)一組相似字符串的抽象。本文將給大家介紹java中使用正則表達(dá)式處理文本數(shù)據(jù)的相關(guān)的資料，感興趣的朋友一起看看吧2015-10-10
這篇文章主要為大家分享了最全的常用正則表達(dá)式大全，包括校驗(yàn)數(shù)字、字符、一些特殊的需求等等，感興趣的小伙伴們可以參考一下2015-12-12
正則表達(dá)式是一種符號(hào)表示法，被用來(lái)識(shí)別文本模式。在某種程度上，它們與匹配文件和路徑名的shell通配符比較相似，但其規(guī)模更大。許多命令行工具和大多數(shù)編程語(yǔ)言都支持正則表達(dá)式，以此來(lái)幫助解決操作文本的問(wèn)題。2018-05-05
臨時(shí)記錄：一個(gè)正則...2006-12-12
這篇文章主要為大家介紹下VBS中的正則表達(dá)式的一些使用方法，需要的朋友可以參考下2006-10-10
這篇文章主要介紹了正則表達(dá)式詳析+常用示例，正則表達(dá)式就是用來(lái)操作字符串的一種邏輯公式，下面小編將用示例的方法來(lái)介紹正則表達(dá)式的相關(guān)內(nèi)容，需要的小伙伴可以參考一下2022-01-01
日常編程經(jīng)常會(huì)用到正則表達(dá)式,躲不開(kāi)這個(gè)陷阱,本文主要介紹了淺談?wù)齽t表達(dá)式回溯陷阱,具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11
常用的正則驗(yàn)證代碼，非常的全面，但因?yàn)槭轻槍?duì)以前的版本，例如手機(jī)等，學(xué)習(xí)正則與使用正則驗(yàn)證表單的朋友絕對(duì)值得參考。2010-08-08
使用正則表達(dá)式去除所有html標(biāo)簽只保留文字
這篇文章主要介紹了使用正則表達(dá)式去除所有html標(biāo)簽只保留文字效果，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2018-07-07