A Sobering Example
首先來看一個真正體現回溯和效率的重要性的例子。在198頁，我們用「〞（\\.|[^\\〞]）＊〞」來匹配引號字符串，其中容許出現轉義的雙引號。這個表達式沒有錯，但如果我們使用NFA引擎，對每個字符都應用多選結構的效率就會很低。對字符串中每個「正常」（非轉義、非引用）的字符來說，這個引擎需要測試「\\.」，遇到失敗後回溯，最終由「[^\\〞]」匹配。如果效率不容忽視，就應該做些改動來加快匹配速度。
稍加修改——先邁最好使的腿
A Simple Change—Placing Your Best Foot Forward
對於一般的雙引號字符串來說，普通字符的數量比轉義字符要多，一個簡單的改動就是調換兩個多選分支的順序，把「[^\\〞]」放到「\\.」之前。這樣，只有在遇到字符串中的轉義字符時才會按照多選結構進行回溯（還有一次回溯是星號無法匹配引起的，此時所有的多選分支都匹配失敗，所以整個多選結構無法匹配）。圖6-1說明了其中的差異。箭頭數量的減少，說明第一個多選分支的成功匹配次數增加了，也就是說回溯的次數減少了。
圖6-1：多選分支排列順序的影響（傳統型NFA）
請從下面幾個方面評價這個修改：
●哪種引擎從中獲益？傳統型NFA，或者POSIX NFA，或是兩者？
●什麼情況下，這種修改帶來的收益最大？在文本能夠匹配時，無法匹配時，還是所有時候。
ϖ 請思考這些問題，翻到下一頁查看答案。在閱讀下一節以前，務必理解答案（及原因）。
效率vs準確性
Efficiency Versus Correctness
為提高效率修改正則表達式時最需要考慮的問題是，改動是否會影響匹配的準確性。像上面那樣重新安排多選分支的順序，只有在排序與匹配成功無關時才不會影響準確性。前一章出現的「〞（\\.|[^〞]）＊〞」（☞197）的例子是有缺陷的。如果正則表達式只需要（should）應用於格式正確的字符串，此問題永遠也不會暴露出來。如果認為這個表達式很不錯，改動的確提高了效率，我們就會遇到真正的問題。交換多選分支，把「[^〞]」放在前面，避免表達式進行不正確的匹配，如果目標字符串包含一個轉義的雙引號：
所以，在關注效率的時候，萬不可忘記準確性。
繼續前進——限制匹配優先的作用範圍
Advancing Further—Localizing the Greediness
從圖6-1可以看出，在任意正則表達式中，星號會對每個普通字符進行迭代（或者說「重複」），重複進入-退出多選結構（和括號）。這需要成本，也就是額外的處理——如果可能，我們必須避免這些額外處理。
有一次，在處理這類正則表達式時，我想到一個優化的辦法，考慮到「[^\\〞]」匹配「普通」（非引號，非反斜線）的情況，使用「[^\\〞]+」會在（…）＊的一次迭代中讀入盡可能多的字符。對沒有轉義字符的字符串來說，這樣會一次讀入整個字符串。於是就幾乎不會進行回溯，也就把星號迭代的次數減少到最小。我很為自己的發現而高興。
我們會在本章更深入地考察這個例子，不過看一眼統計數據會清楚地發現好處。圖6-2展示了傳統型 NFA 上應用這個例子的情況。比較原來的「〞（\\.|[^\\〞]）＊〞」（上面的兩個表達式），與多選結構相關的回溯和星號迭代都減少了。下面的兩個例子說明，結合之前的重排序技巧，這種修改會帶來更多的收益。
圖6-2：添加加號的結果（傳統型NFA）
新增的加號大大減少了多選結構回溯的次數，以及星號的迭代次數。星號量詞作用於括號內的子表達式，每次迭代都需要進入然後再退出括號，這都需要成本，因為引擎需要記錄括號內的子表達式匹配的文本（本章會深入探討此問題）。
表6-1與第224頁答案中的表格類似，不過表達式不同，另外還給出了星號的迭代次數。在每種情況下，獨立測試次數和回溯次數的增加都很有限，但是迭代次數有了顯著降低，這是很大的進步。
表6-1：傳統型NFA的匹配效率
實測
Reality Check
是的，我對自己的發現頗為得意。但這個看起來很奇妙的「改動」不過是場還未爆發的災難。你可能注意到了，在考察它的各項指標時，我沒有給出POSIX NFA的統計數據。如果這樣做，你可能會很驚奇地發現〞 
〞的匹配需要超過 3 億億億次（實際上是324 518 553 658 426 726 783 156 020 576 256）回溯。說簡單點就是，回溯是個天文數字。這需要超過50百億億（quintillion）年，或者是若干千萬億個千年（注1）。
確實很出乎意料！那麼，為什麼會發生這種情況呢？簡單地說，原因在於——這個正則表達式中某個元素受加號限定的同時，還受括號外的星號限定，無法區分哪個量詞控制哪個特殊的字符。這種不確定性就是癥結。下一節給出了詳細解釋。
「指數級」匹配
沒有添加星號時，「[^\\〞]」是星號的約束對象，真正的「（[^\\〞]）＊」能夠匹配的字符是有限的。它先匹配一個字符，然後匹配下一個字符，如此繼續，最多就是匹配目標文本中的每個字符。它也可能無法匹配目標字符串中的所有字符，不過，充其量，匹配字符的個數與目標字符串的長度成線性關係。目標字符串越長，可能的工作量相對也越大。
但是，對正則表達式的「（[^\\〞]+）＊」來說，加號和星號二者分割（pvy up）字符串的可能性是成指數形式增長的。如果目標字符串是 makudonarudo，是星號會迭代12次，每一次迭代中「[^\\〞]+」匹配一個字符（就像這樣
）？還是星號迭代3次，內部的「[^\\〞]+」分別匹配 5、3、4 個字符（
』）？或者 2、2、5、3 個字符（『
』）？還是其他……
你現在知道，存在許多種可能（對長度為12的字符串存在4 096種可能）。字符串中的每個字符，都存在兩種可能，POSIX NFA在給出結果之前必須嘗試所有可能。這就是「指數級匹配」的來歷。我還聽說過一個不錯的名字：「超線性（super-linear）」。
無論叫什麼名字，終歸都是回溯，大量的回溯（注2）！12個字符需要4 096種可能，這可能不需要多久時間，不過20個字符需要超過一百萬種可能，時間長達若干秒。30個字符，就需要超過十億種可能，長達若干小時，如果是40個字符，就需要一年多的時間。這顯然不是什麼好事情。
你可能會想，「沒關係，POSIX NFA 並不常見。我知道我的工具用的是傳統型NFA，所以這問題對我不存在。」的確，POSIX NFA和傳統型NFA的主要差別在於，傳統型NFA在遇到第一個完整匹配可能時會停止。如果沒有完整匹配，即使是傳統型NFA也需要嘗試所有的可能，在找到之前。即使是前面提到的〞No·〞match〞·here這樣短短的字符串，在報告失敗之前，也需要嘗試8 192種可能。
在正則引擎忙於嘗試這些數量龐大的可能時，整個程序看起來好像「鎖死（lock up）」了。我第一次遇到這種情況時，以為自己發現了程序的bug，不過現在我理解了，現在我把這個正則表達式加入自己的正則表達式工具包裡，用來測試引擎的類型。
●如果其中的某個表達式，即使不能匹配，也能很快給出結果，那可能就是DFA。
●如果只有在能夠匹配時才很快出結果，那就是傳統型NFA。
●如果總是很慢，那就是POSIX NFA。
第一個判斷中我使用了「可能」這個單詞，因為經過高級優化的NFA沒準能檢測並且避免這些指數級的無休止（neverending）匹配（詳見本章後文☞250）。同樣，我們會見到各種方法來改進或重寫這些表達式，加快它們匹配或報錯的速度。
前面列出的幾點表明，如果排除某些高級優化的影響，就能根據正則表達式的相對性能判斷引擎的類型。這就是第4章中（☞146）我們能用某些正則表達式來「測試引擎的類型」的原因。
當然，不是每點改動都會帶來像本例一樣的災難性後果，不過除非知道正則表達式的幕後原理，否則在實際運行之前永遠不能判斷後果。為此，本章考察了各種例子的效率和後果。不過，對許多事來說，牢固理解基本概念對深入學習是非常重要的；所以，在講解指數級匹配之前，我們不妨仔細複習複習回溯。