顯示廣告
隱藏 ✕
看板 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
※ 看板: KnucklesNote 文章推薦值: 2 目前人氣: 0 累積人氣: 4191 
※ 本文也出現在看板: BadApple xxxx9659
※ 文章分類: 網頁程式 PHP
分享網址:
( ̄︶ ̄)b tails, xxxx9659 說讚!
qwan 轉錄至看板 BadApple (使用連結) 時間:2011-12-27 18:41:38
xxxx9659 轉錄至看板 xxxx9659 (使用連結) 時間:2013-02-16 11:34:27
r)回覆 e)編輯 d)刪除 M)不收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇