看板 Knuckles_note
作者 標題 [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
回列表(←)
分享