看板 Knuckles_note
作者 Knuckles (站長 那克斯)
標題 [PHP] Regular expression: 貪婪、非貪婪
時間 2011年10月10日 Mon. AM 07:04:03
貪婪與非貪婪
當要抓取一段不固定的字串,例如 <b> 與 </b> 中間的字
最常看到的方法就是使用正規表示式 regular expression (以下簡稱 regex):
/
<b>(.*?)<\/b>/
其中
. 代表任意字元
* 代表前面的字元會出現0~∞次
? 代表使用非貪婪(non-greedy)的方法
( ) 代表將匹配的結果輸出到要抓取的第一個字串$1
若使用 /
<b>(.*)<\/b>/ 則是代表使用貪婪(greedy)的方法
貪婪代表所有可能的匹配結果中,取字元數最多的
非貪婪就是取字元數最少的
如果整個字串確定就只有一組 <b> </b> 的話那匹配的結果就一樣
但若是像這樣的字串:
$string = "000
<b>abc
</b>1234
<b>xxx
</b>5678
<b>yyy
</b>0000";
貪婪抓到的 <----------------------------->
非貪婪抓到的 <->
可以看出使用非貪婪的方法才會抓到正確的結果
非貪婪的效能問題
其實非貪婪還蠻好用的,符號也很簡潔,剛開始學會這個就可以應付大部份的情況了
但使用非貪婪的效能不好,當遇到 $string = "
<b>很長很長的文章.....
</b>" 時
preg_replace("/
<b>(.*?)<\/b>/","$1",$string) 可能會直接傳出null
一開始還以為是要抓取的字串有長度限制...其實不是,是使用非貪婪造成回溯(backtracking)次數過多
只要regex改用 /
<b>([^<]*)<\/b>/ 這種排除型字符組(Negated Character Classes/Set)就好了
其中
[^<]* 代表除了
< 以外的所有字元,可能有0~∞個
這樣就可以使用貪婪的方法,但又不會抓到超過
</b> 的字元了
為什麼使用非貪婪會造成回溯次數過多呢,這要先知道regex匹配字串的方法
舉例來說,當 $string = "
<b>1234567890
</b>"
使用貪婪法 regex 為 /
<b>(.*)<\/b>/ 時
$string = "
<b>1234567890
</b>"
<-> 符合regex一開始的
<b>,交給下一個符號
.*
<------------> 因為
.* 是貪婪,會抓取所有的可能,然後交給下一個符號
<
^ 發現下一個字元不是
<,回溯
<----------->^
.* 吐一個字元出來給
<,還是不符合,回溯
<---------->^
.* 吐一個字元出來給
<,還是不符合,回溯
<--------->^
.* 吐一個字元出來給
<,還是不符合,回溯
<-------->^
.* 吐一個字元出來給
<,符合了,交給下個符號
<-> 後面的
\/b> 也符合,結束
使用非貪婪法 regex 為 /
<b>(.*?)<\/b>/ 時
$string = "
<b>1234567890
</b>"
<-> . . 符合regex一開始的
<b>,交給下一個符號
.*?
^ . . 因為
.*?非貪婪,空字元就符合了,交給下個符號
<
^ . . 發現下一個字元不是
<,回溯
^ . .
.*?抓了一個字元後,交給下個符號
<,但下個字元不是
<,回溯
^ . .
.*?再抓一個字元後,交給下個符號
<,但下個字元不是
<,回溯
.......
^ .
.*?再抓一個字元後,交給下個符號
<
^ . 下個字元符合
<,交給下個符號
<-> 後面的
\/b>也符合,結束
由以上過程可以知道,使用非貪婪法時,要抓取的字串有多少個,就相當於要回溯多少次
所以要抓取的字串很長很長時,自然就爆表了
就算沒爆表但效率不佳所以也不是個好方法
排除型字符組的問題
如果使用 /
<b>([^<]*)<\/b>/ 這種抓到
<之前為止的貪婪法
好像就沒有回溯問題了? 但這又會產生另一個問題
若 $string = "
<b>12345<i>italic</i>67890
</b>"
會匹配失敗,什麼都抓不到
所以必需要明確的定義我們要的是抓到
</b> 之前的字串,而不是只看到
< 就算了
這時候就要用到 lookahead assertion 了
regex的寫法為 /
<b>((?:(?!<\/b>).)*)<\/b>/
其中
. 為任意字元
(?!<\/b>) 代表接下來的字串不可以是
</b>
接在
. 的左邊所以
. 與
. 右邊三個字元不可以是
</b>
(?: ) 只是用來把
(?!<\/b>) 與
. 包起來,加上 ?: 是為了避免變成要抓取的字串之一
* 代表
(?:(?!<\/b>).) 這個任意但不會是
<後面接
/b>的字元,可能會出現 0~∞ 次
終級解決法: once-only + lookahead assertion
但改成這樣效率還是不夠好,因為要判斷每個字元以及他的下三個字元是否為
</b>
能不能只要先檢查字元是否為
< 就好,不是的話就檢查下一個字元,是的話再看後面三個字元是否為
/b> 呢?
這樣就要用到
Once-only subpatterns 或叫固化分組
用法:
(?>pattern
) 其中的pattern只要成功的匹配到一次,就確定用這個匹配的結果
交給下一個符號後,若下一個符號無法匹配,也不會再回溯到pattern尋找其它的可能
ps. 類似
(?: ) ,pattern 不會被當作要抓取的字串之一
所以再將以上例子的regex改寫為
/
<b>((?>[^
<]*
)(?><(?!\/b>)[^
<]*
)*)<\/b>/
用在 $string = "<b>xxxxxx<i>iiiii</i>xxxxxx</b>" 時
<->. . . . 符合一開始的
<b>
<---->. . . 符合接下來的
(?>[^
<]*
) 因為有加
?> 不會再回溯到這裡
. ^ . . 符合
<(?!\/b>) 也就是一個後面不是接
/b> 的
< 字元
. <-----> . 符合 [^
<]*
. <------> . 上面兩個合起來就是
(?><(?!\/b>)[^
<]*
),有加
?>不再回溯
. <--------> 第二個
(?><(?!\/b>)[^
<]*
)
. . 也就是
<開頭到下個
<的前一個字元,但不是
</b>開頭的字串
. . 因為這樣的字串可能有 0~∞ 個,所以再加個
*
. .
<----------------------> 最後再用
( ) 將整塊包起來當作要抓取的第一個字串
^遇到
< 但後面是接
/b> ,不符合
(?!<\/b>)<
所以交給後面的符號
<\/b> ,發現符合,結束
因為有點複雜,所以寫成 function 比較好用
function reg_not($pattern){
$head = substr($pattern,0,1); // <
$body = substr($pattern,1); // \/b>
return "(?>[^$head]*)(?>$head(?!$body)[^$head]*)*";
}
使用方法,例如要將 <b>xxx</b> 換成 <strong>xxx</strong>
$result = preg_replace('/<b>('.reg_not('<\/b>').')<\/b>/','<strong>$1</strong>',$string);
參考網頁:
深度分析正則(pcre)最大回溯/遞歸限制
小議正則表達式效率 貪婪、非貪婪與回溯
PHP正則表達式的效率 回溯與固化分組
Regex: long Pattern vs. Short Pattern
--
--
※ 作者: Knuckles 時間: 2011-10-10 07:04:03
※ 編輯: Knuckles 時間: 2016-04-13 04:46:57