Techniques for Faster Expressions
之前的數頁介紹了我見過的傳統型NFA引擎使用的各種優化。沒有任何程序同時具備所有這些優化，而且無論你愛用的程序目前支持哪些，情況也會隨時間而改變。但是，理解可能進行的各種優化，我們就能寫出效率更高的表達式。如果你還理解傳統型NFA的工作原理，把這些知識結合起來，就可以從三方面獲益：
●編寫適於優化的正則表達式 編寫適應已知（或者未來會支持的）優化措施的表達式。舉例來說，「xx＊」比「x+」能適用的優化措施更多，例如檢查目標字符串中必須出現的字符（☞245），或者開頭字符識別（☞247）。
●模擬優化 有時候我們知道所用的程序沒有特殊的優化措施，但是通過手工模擬，我們還是能節省大量的時間。比如在「this|that」之前添加「（？=t）」，這樣即使系統無法預知任何匹配結果必須以『t』開頭，我們還是能模擬開頭字符識別（☞247），下文還會深入討論這個例子。
●主導引擎的匹配 使用關於傳統型 NFA 引擎工作原理的知識，能夠主導引擎更快地匹配。拿「this|that」來說。每個多選分支都以「th」開頭，如果第一個多選分支不能匹配「th」，第二個顯然也不行，所以不必白費工夫。因此，我們可以使用「th（？：is|at）」。這樣，「th」就只要檢查一遍，只由在確實需要的時候才會用到代價相對高昂的多選結構功能。而且，「th（？：is|at）」開頭的純文字字符就是「th」，所以存在進行其他優化的可能。
重要的是認識到，效率和優化有時候處理起來比較麻煩。在閱讀本節其他內容的時候，請不要忘記下面幾點：
●進行看來確實有幫助的改動，有時反而事與願違，因為這樣可能禁止了你所不知道的，已經生效的其他優化。
●添加一些內容模擬你知道的不存在的優化措施，可能出現的情況是，處理那些添加內容的時間多於節省下來的時間。
●添加一些內容模擬一個目前未提供的優化，如果將來升級以後的軟件支持此優化，反而會影響或者重複真正的優化。
●同樣，控制表達式嘗試觸發某種當前可用的優化，將來某些軟件升級之後可能無法進行某些更高級的優化。
●為提高效率修改表達式，可能導致表達式難以理解和維護。
●具體的修改帶來的好處（或是壞處）的程度，基本上取決於表達式應用的數據。對某類數據來說有益的修改，可能對另一類數據來說是有害的。
我來舉個極端點的例子：你在 Perl 腳本中找到「（000|999）$」，並決定把這些捕獲型括號替換為非捕獲型括號。你覺得這樣速度更快，因為不再需要捕獲文本的開銷。但是奇怪的是，這個微小而且看起來有益的改動反而會把表達式的速度降低許多個數量級（比之前慢幾千倍）。怎麼會這樣呢？原來在這裡有若干因素共同作用，使用非捕獲型括號時，字符串結束/行錨點優化（☞246）會被關閉。我不希望勸阻讀者在Perl中使用捕獲型括號——絕大多數情況下，使用他們都是有益的，但是在某些情況下，會帶來災難性的後果。
所以，檢測並性能測試你期望實際應用的同類型的數據，有助於判斷改動是否值得，但是，你仍然必須自己權衡眾多因素。就說這麼多，下面我開始講解一些技巧，你能夠用它們來挖掘引擎效率的最後一點潛能。
常識性優化
Common Sense Techniques
只需要依靠常識，就能進行一些極有成效的優化。
避免重新編譯
編譯和定義正則表達式的次數應該盡可能的少。在面向對像式處理中（☞95），用戶能夠精確控制這一點。舉例來說，如果你希望在循環中應用正則表達式，就應該在循環外創建這個正則表達式對象，在循環中重複使用。
在函數式處理——例如GNU Emacs和Tcl——的情況下，應盡量保證循環中使用的正則表達式的數目少於工具所能緩存的上限（☞244）。
如果使用的是集成式處理，例如Perl，應盡量避免在循環內的正則表達式中使用變量插值，因為這樣每次循環都需要重新生成正則表達式，即使值沒有變化（不過，Perl提供了高效的辦法來避免這個問題☞348）。
使用非捕獲型括號
如果不需要引用括號內的文本，請使用非捕獲型括號「（？：…）」（☞45）。這樣不但能夠節省捕獲的時間，而且會減少回溯使用的狀態的數量，從兩方面提高速度。而且能夠進行進一步的優化，例如消除無必要括號（☞248）。
不要濫用括號
在需要的時候使用括號，在其他時候使用括號會阻止某些優化措施。除非你需要知道「.＊」匹配的最後一個字符，否則請不要使用「（.）＊」。這似乎很顯而易見，但是別忘了，本節的標題是「常識性優化」。
不要濫用字符組
這一點看起來也很顯而易見，但是我經常在缺乏經驗的程序員的表達式中看到「^.＊[：]」。我不知道為什麼他們會使用只包含單個字符的字符組——這樣需要付出處理字符組的代價，但並不需要用到字符組提供的多字符匹配功能。我認為，當一個字符是元字符時——例如「[.]」或者「[＊]」，可能作者不知道通過轉義把它們轉換為「\.」和「\＊」。我經常在寬鬆排列模式（☞111）下見到它們與空白字符一起出現。
同樣，讀過本書第一版的Perl用戶可能有時候寫出「^[Ff][Rr][Oo][Mm]：」，而不是用不區分大小寫的「^from：」。老版本的 Perl 在進行不區分大小寫的匹配時效率很低，所以我推薦使用字符組。但現在這種做法已不再適用，因為不區分大小寫匹配效率低下的問題在好幾年前就修正了。
使用起始錨點
除非是極其罕見的情況，否則以「.＊」開頭的正則表達式都應該在最前面添加「^」或者「\A」（☞129）。如果這個正則表達式在某個字符串的開頭不能匹配，那麼顯然在其他位置它也不能匹配。添加錨點（無論是手工添加，還是通過優化自動添加☞246）都能夠配合開頭字符/字符串/字串識別優化，節省大量不必要的工作。
將文字文本獨立出來
Expose Literal Text
我們在本章見過的許多局部優化，主要是依靠正則引擎的能力來識別出匹配成功必須的一些文字文本。某些引擎在這一點上做得比其他引擎要好，所以這裡提供了一些手動優化措施，有助於「暴露」文字文本，提高引擎識別的可能性，配合與文字文本有關的優化措施。
從量詞中「提取」必須的元素
用「xx＊」替代「x+」能夠暴露匹配必須的『x』。同樣的道理，「-{5，7}」可以寫作「------{0，2}」。
「提取」多選結構開頭的必須元素
用「th（？：is|at）」替代「（？：this|that）」，就能暴露出必須的「th」。如果不同多選分支的結尾部分相同，我們也可以從右面「提取」，例如「（？：optim|standard）ization」。我們會在下一節中看到，如果提取出來的部分包括錨點，這麼做就非常有價值。
將錨點獨立出來
Expose Anchors
某些效果明顯的內部優化措施是利用錨點（例如「^」、「$」和「\G」），把表達式「綁定」在目標字符串的某一端。使用這些優化時，某些引擎的效果不如其他引擎，但是有一些技巧能夠提供幫助。
在表達式前面獨立出^和\G
「^（？：abc|123）」和「^abc|^123」在邏輯上是等價的，但是許多正則引擎只會對第一個表達式使用開頭字符/字符串/字串識別優化（☞246）。所以，第一種辦法的效率要高得多。PCRE （還包括使用它的工具）中兩者的效率是一樣的，但是大多數其他NFA工具中第一個表達式的效率更高。
比較「（^abc）」和「^（abc）」我們能發現另一個區別。前者的設置並不很合適，錨點「藏」在捕獲型括號內，在檢測錨點之前，必須首先進入括號，在許多系統上，這樣做的效率很低。某些系統（PCRE、Perl、.NET）中兩者的效率相當，但是在其他系統中（Ruby 和 Sun 的Java regex package）只會對後者進行優化。
Python 似乎不會進行錨點優化，所以這些技巧目前不適用於 Python。當然，本章介紹的大多數優化都不適用於Tcl（☞243）。
在表達式末尾獨立出$
此措施與上一節的優化思想非常類似，雖然「abc$|123$」和「（？：abc|123）$」在邏輯上是等價的，但優化的表現可能不同。目前，這種優化還只適用於 Perl，因為現在只有 Perl 提供了「字符串結束/行錨點優化」（☞246）。優化只對「（…|…）$」起作用，對「（…$|…$）」不起作用。
忽略優先還是匹配優先？具體情況具體分析
Lazy Versus Greedy:Be Specific
通常，使用忽略優先量詞還是匹配優先量詞取決於正則表達式的具體需求。舉例來說，「^.＊：」完全不同於「^.＊？：」，因為前者匹配到最後的冒號，而後者匹配到第一個冒號。但是，如果目標數據中只包含一個分號，兩個表達式就沒有區別了（匹配到唯一的分號為止），所以選擇速度更快的表達式可能更合適。
不過並不是任何時候優劣都如此分明，大的原則是，如果目標字符串很長，而你認為分號會比較接近字符串的開頭，就使用忽略優先量詞，這樣引擎能更快地找到分號。如果你認為分號在接近字符串末尾的位置，就使用匹配優先量詞。如果數據是隨機的，又不知道分號究竟會靠近哪一頭，就使用匹配優先的量詞，因為它們的優化一般來說都要比其他量詞要好，尤其是表達式的後面部分禁止進行「忽略優先量詞之後的字符優化」（☞248）時，更是如此。
如果待匹配的字符串很短，差別就不那麼明顯了。這時候，兩個正則表達式的速度都很快，不過如果你很在乎那一點點速度差別，就對典型數據做個性能測試吧。
一個與此有關的問題是，在忽略優先量詞和排除型字符組之間（「^.＊？：」與「^[^：]＊：」），應該如何選擇？答案還是取決於所使用的編程語言和應用的數據，但是對大多數引擎來說，排除型字符組的效率比忽略優先量詞高的多。Perl是個例外，因為它能對忽略優先量詞之後的字符進行優化。
拆分正則表達式
Split Into Multiple Regular Expressions
有時候，應用多個小正則表達式的速度比一個大正則表達式要快得多。舉個極端的例子，如果你希望檢查一個長字符串中是否包含月份的名字，依次檢查「January」、「February」、「March」之類的速度，要比「January|February|March|…」快得多。因為對後者來說，不存在匹配成功必須的文字內容，所以不能進行「內嵌文字字符串檢查優化」（☞247）。「大而全」的正則表達式必須在目標文本中的每個位置測試所有的自表達式，速度相當慢。
撰寫本章時，我遇到了一個有趣的情況。用 Perl 寫一個數據處理模塊時，我意識到客戶端程序有個bug，導致它發送奇怪的數據，類似『HASH（0x80f60ac）』而不是真正的數據。所以，我打算修正這個模塊，尋找怪異數據的來源，並報告錯誤。我使用的正則表達式相當直白：「\b（？：SCALAR|ARRAY|…|HASH）\（0x[0-9a-fA-F]+\）」。
在這裡，效率是非常關鍵的。這個表達式的速度如何？Perl的調試模式（debugging mode）能夠告訴你它對特定表達式使用的某些優化（☞361），所以我進行了檢查。我希望啟用了預查必須字符/字符串優化（☞245），因為足夠先進的引擎應該能夠明白『（0x』是任何匹配所必須的。因為這個正則表達式所應用的數據幾乎不包含『（0x』，我相信預查能夠節省許多時間。不幸的是，Perl沒有這樣做，所以程序必須在每個目標字符串的每個字符那裡測試整個正則表達式的眾多多選分支。速度達不到我的要求。
因為正在研究和撰寫與優化有關的內容，所以我冥思苦想，這個表達式應該怎樣寫才能得到優化。一個辦法是以複雜的方式
[0-9a-fA-F]+\）」。這樣，一旦「\（0x」匹配之後，肯定型順序環視（下畫線標注部分）就能確保之前匹配的是需要的文本，再檢查之後的文本是否符合期望。費這番周折的原因在於，讓正則表達式獲得必須出現的文字文本「\（0x」，這樣就能進行多種優化。尤其是，我希望進行預查必須字符串優化，以及開頭字符/字符組/子串識別優化（☞247）。我確定這樣速度會很快，但是Perl不支持長度不定的逆序環視（☞133），所以我得想辦法來繞開它。
不過我發覺，如果Perl不會自動預查「\（0x」，我可以自己動手：
「\（0x」的檢查事實上會過濾大部分文本，相對較慢的完整正則表達式只對有可能匹配的行進行檢測，這樣就在效率（非常高）和可讀性（非常高）之間達到了完美的平衡（注7）。
模擬開頭字符識別
Mimic Initial-Character Discrimination
如果你的實現方式沒有進行開頭字符識別優化（☞247），則可以親自動手，在表達式的開頭添加合適的環視結構（☞133）。在正則表達式的其他部分匹配之前，環視結構可以進行「預查」，選擇合適的開始位置。
如果正則表達式為「Jan|Feb|…|Dec」，對應的就是「（？=[JFMASOND]）（？：Jan|Feb|…|Dec）」。開頭的「[JFMASOND]」代表了英文中月份單詞可能的開始字母。不過這種技巧並不是所有情況下都適用的，因為，環視結構的開銷可能大於節省的時間。在這個例子中，因為多數多選分支都可能匹配失敗，預查對我測試的大多數系統（Java、Perl、Python、Ruby、.NET）都是有用的，因為它們都不能自動從「Jan|Feb|…|Dec」得到開頭的「[JFMASOND]」。
在默認情況下，PHP/PCRE並不會進行這種優化，但是如果使用PCRE的pcre_study（也就是PHP中的模式修飾符S，☞478）則可以。而Tcl顯然能夠完美地做到這一點（☞243）。
如果正則引擎能自動進行「[JFMASOND]」的檢測，速度當然會比用戶手工指定快得多。我們有沒有辦法讓引擎自動進行檢測呢？在許多系統上，我們可以用下面這個複雜得要命的表達式：
「[JFMASOND](?:(?＜=J)an|(?＜=F)eb|…|(?＜=D)ec)」
我可不指望你能看一眼就明白這個表達式，但是花點時間仔細琢磨倒是很值得的。表達式開頭的字符組可以被大多數系統的開頭字符識別優化所利用，這樣傳動裝置就能夠高效地預查「[JFMASOND]」。如果目標字符串不包含匹配字符，結果會比原來的「Jan|…|Dec」或是手工添加環視功能的表達式要快。但是，如果目標字符串中包含許多字符組能夠匹配的字符，那麼額外的逆序環視可能反而會減慢匹配的速度。最主要的問題是，這個正則表達式顯然很難看懂。但是，這個例子倒是很有意思，也很啟發人。
不要在Tcl中這麼做
上面的優化例子其實降低了表達式的可讀性。243頁的補充內容提到，不同形式的正則表達式在Tcl中的表現是相同的，所以在Tcl中，大多數優化並沒有意義。不過，有個例子中優化確實有影響。根據我的測試，手動添加「（？=[JFMASOND]）」會把速度降低到原來的1/100。
不要在PHP中這麼做
之前我們已經提到過，不應該在PHP中進行優化，因為我們能夠使用PHP的「study」功能——模式修飾符S——來啟用優化。詳見第10章第478頁。
使用固化分組和佔有優先量詞
Use Atomic Grouping and Possessive Quantifiers
在許多情況下，固化分組（☞139）和佔有優先量詞（☞142）能夠極大地提高匹配速度，而且它們不會改變匹配結果。舉例來說，如果「^[^：]+：」中的冒號第一次嘗試時無法匹配，那麼任何回溯其實都是沒有意義的，因為根據定義，回溯「交還」的任何字符都不可能是冒號。使用固化分組「^（？＞[^：]+）：」或者佔有優先量詞「^[^：]++：」就能夠直接拋棄備用狀態，或者根本不會創造多少備用狀態。因為引擎沒有內容狀態可以回溯，就不會進行不必要的回溯（第251頁的補充內容說明，足夠聰明的引擎能夠自動進行這種優化）。
不過，我必須強調，這兩種結構運用不當，就會在不經意間改變匹配結果，所以必須極為小心。如果不用「^.＊：」而用「^（？＞.＊）：」，結果必然會失敗。整行文本都會被「.＊」匹配，後面的「：」就無法匹配任何字符。固化分組阻止最後的「：」匹配必須進行的回溯，所以匹配必定失敗。
主導引擎的匹配
Lead the Engine to a Match
提高正則表達式匹配效率的另一個辦法是盡可能準確地設置匹配過程中的「控制權」。我們曾經看過的用「th（？：is|at）」取代「this|that」的例子。在後一個表達式中，多選結構獲得最高級別的控制權，而在前一個表達式中，相對代價更高昂的多選結構只有在「th」匹配之後才獲得控制權。
下一節「消除循環」是這種技巧的高級形式，此處再介紹些簡單的技巧。
將最可能匹配的多選分支放在前頭
在本書中我們看到，許多時候多選分支的擺放順序非常重要（☞28、176、189、216）。在這些情況下，擺放順序比優化更重要，但相反，如果順序與匹配正確無關，就應該把最可能匹配的多選分支放在首位。
舉例來說，在匹配主機名的正則表達式（☞205）中，有人可能習慣把後綴按照字母順序排序，例如「（？：aero|biz|com|coop|…）」。不過，某些排在前頭的後綴應用並不廣泛，匹配極有可能失敗，為什麼要把他們排在前頭呢？如果按照分佈數量的排序：「（？：com|edu|org|net|…）」，更有可能獲得更迅速更常見的匹配。
當然，這只有對傳統型NFA引擎才適用，而且只有存在匹配的時候才適用。如果使用POSIX NFA，或是不存在匹配，此時所有的多選分支都必須檢測，所以順序是無關緊要的。
將結尾部分分散到多選結構內
接下來我們比較「（？：com|edu|…|[a-z][a-z]）\b」和「com\b|edu\b|…\b|[a-z][a-z]\b」。在後一個表達式中，多選結構之後的「\b」被分散到每個多選分支。可能的收益就是，它可能容許一個多選分支能夠匹配，但多選分支之後的「\b」可能導致這個匹配不成功，把「\b」加到多選結構之內，匹配失敗的更快。這樣不需要退出多選結構就能發現失敗。
要說明這個技巧的價值，這可能還不是最好的辦法，因為它只是適用於一種特殊情形，即多選分支可能能夠匹配，但是之後緊接的字符可能令匹配失敗。在本章中我們會看到一個更合適的例子——請參考280頁關於$OTHER＊的討論。
這個優化是有風險的。切記，使用這個功能時要小心，不要因此阻止了本來可以進行的其他優化。舉例來說，如果「分散的」子表達式是文字文本，那麼把「（？：this|that）：）」更換為「this：|that：」就違背了「將文字文本獨立出來」（☞255）中的某些思想。各種優化都是平等的，所以在優化時請務必小心，不要因小失大。
在能夠進行獨立結尾錨點（☞256）的系統上把正則表達式末尾的「$」分散，也會遇到這種問題。在這些系統上，「（？：com|edu|…）$」比「com$|edu$|…$」快得多（我測試了各種系統，只有Perl使用了這種優化）。