推 cutecpu:推，好文^_^ 10/11 23:42
推 PurpleCrow:再推! good! 10/12 15:32
※ 編輯: knuckles 來自: 111.248.0.200 (10/13 03:33)
※ 編輯: knuckles 來自: 111.248.6.95 (10/13 06:47)
※ [本文轉錄自 PHP 看板 #1Eb53dRp ]
作者: knuckles (那克斯) 看板: PHP
標題: [分享] Regular expression: 貪婪、非貪婪
時間: Tue Oct 11 22:21:23 2011
自己寫的一些筆記，給大家參考一下
我也是初學regex的新手，沒看過書只看了一些網頁教學而已
有什麼錯誤或觀念不對的地方還請大家多多指教 ^^
網頁上色好讀版: http://disp.cc/b/11.cj-2q1S
貪婪與非貪婪
當要抓取一段不固定的字串，例如 <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>
發現符合，結束
參考網頁:
深度分析正則(pcre)最大回溯/遞歸限制 http://www.jb51.net/article/26817.htm
小議正則表達式效率 貪婪、非貪婪與回溯 http://www.jb51.net/article/26816.htm
PHP正則表達式的效率 回溯與固化分組 http://www.jb51.net/article/26814.htm
Regex: long Pattern vs. Short Pattern http://tinyurl.com/3wtx5f3
Once-only subpatterns http://tinyurl.com/3owctlu
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.0.200
※ 編輯: knuckles 來自: 111.248.0.200 (10/11 22:22)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.0.200