正則表達式回溯法原理

前言

一般很多人對待表達式都是要用的時候，取查一下，你是嗎？今日早讀文章由@老姚授權分享。

正文從這開始～

學習正則表達式，是需要懂點兒匹配原理的。

而研究匹配原理時，有兩個字出現的頻率比較高：「回溯」。

聽起來挺高大上，確實還有很多人對此不明不白的。

因此，本文就簡單扼要地說清楚回溯到底是什麼東西。

內容包括：

1. 沒有回溯的匹配

2. 有回溯的匹配

3. 常見的回溯形式

1. 沒有回溯的匹配

假設我們的正則是/abc/，其可視化形式是：

而當目標字元串是"abbbc"時，就沒有所謂的「回溯」。其匹配過程是：

其中子表達式b表示「b」字元連續出現1到3次。

2. 有回溯的匹配

如果目標字元串是"abbc"，中間就有回溯。

圖中第5步有紅顏色，表示匹配不成功。此時b已經匹配到了2個字元「b」，準備嘗試第三個時，結果發現接下來的字元是「c」。那麼就認為b就已經匹配完畢。然後狀態又回到之前的狀態（即第6步，與第4步一樣），最後再用子表達式c，去匹配字元「c」。當然，此時整個表達式匹配成功了。

圖中的第6步，就是「回溯」。

你可能對此沒有感覺，這裡我們再舉一個例子。正則是：

目標字元串是"abbbc"，匹配過程是：

其中第7步和第10步是回溯。第7步與第4步一樣，此時b匹配了兩個"b"，而第10步與第3步一樣，此時b只匹配了一個"b"，這也是b的最終匹配結果。

這裡再看一個清晰的回溯，正則是：

目標字元串是："acd"ef，匹配過程是：

圖中省略了嘗試匹配雙引號失敗的過程。可以看出「.*」是非常影響效率的。

為了減少一些不必要的回溯，可以把正則修改為/"[^"]"/。

3. 常見的回溯形式

正則表達式匹配字元串的這種方式，有個學名，叫回溯法。

回溯法也稱試探法，它的基本思想是：從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有「狀態」，當一條路走到「盡頭」的時候（不能再前進），再後退一步或若干步，從另一種可能「狀態」出發，繼續搜索，直到所有的「路徑」（狀態）都試探過。這種不斷「前進」、不斷「回溯」尋找解的方法，就稱作「回溯法」。（copy於百度百科）。

本質上就是深度優先搜索演算法。其中退到之前的某一步這一過程，我們稱為「回溯」。從上面的描述過程中，可以看出，路走不通時，就會發生「回溯」。即，嘗試匹配失敗時，接下來的一步通常就是回溯。

道理，我們是懂了。那麼JS中正則表達式會產生回溯的地方都有哪些呢？

3.1 貪婪量詞

之前的例子都是貪婪量詞相關的。比如b，因為其是貪婪的，嘗試可能的順序是從多往少的方向去嘗試。首先會嘗試"bbb"，然後再看整個正則是否能匹配。不能匹配時，吐出一個"b"，即在"bb"的基礎上，再繼續嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了。

雖然局部匹配是貪婪的，但也要滿足整體能正確匹配。否則，皮之不存，毛將焉附？

此時我們不禁會問，如果當多個貪婪量詞挨著存在，並相互有衝突時，此時會是怎樣？

答案是，先下手為強！因為深度優先搜索。測試如下：

varstring="12345";

varregex=/(d)(d)/;

console.log(string.match(regex));

// => ["12345", "123", "45", index: 0, input: "12345"]

其中，前面的d匹配的是"123"，後面的d匹配的是"45"。

3.2 惰性量詞

惰性量詞就是在貪婪量詞後面加個問號。表示儘可能少的匹配，比如：

varstring="12345";

varregex=/(d?)(d)/;

console.log(string.match(regex));

// => ["1234", "1", "234", index: 0, input: "12345"]

其中d?只匹配到一個字元"1"，而後面的d匹配了"234"。

雖然惰性量詞不貪，但也會有回溯的現象。比如正則是：

目標字元串是"12345"，匹配過程是：

知道你不貪、很知足，但是為了整體匹配成，沒辦法，也只能給你多塞點了。因此最後d?匹配的字元是"12"，是兩個數字，而不是一個。

3.3 分支結構

我們知道分支也是惰性的，比如/Java|JavaScript/，去匹配字元串"JavaScript"，得到的結果是"Java"，因為分支會一個一個嘗試，如果前面的滿足了，後面就不會再試驗了。

分支結構，可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續嘗試剩下的分支。這種嘗試也可以看成一種回溯。

比如正則：

目標字元串是"candy"，匹配過程：

上面第5步，雖然沒有回到之前的狀態，但仍然回到了分支結構，嘗試下一種可能。所以，可以認為它是一種回溯的。

後記

其實回溯法，很容易掌握的。

簡單總結就是，正因為有多種可能，所以要一個一個試。直到，要麼到某一步時，整體匹配成功了；要麼最後都試完後，發現整體匹配不成功。

1. 貪婪量詞「試」的策略是：買衣服砍價。價錢太高了，便宜點，不行，再便宜點。

2. 惰性量詞「試」的策略是：賣東西加價。給少了，再多給點行不，還有點少啊，再給點。

3. 分支結構「試」的策略是：貨比三家。這家不行，換一家吧，還不行，再換。

既然有回溯的過程，那麼匹配效率肯定低一些。相對誰呢？相對那些DFA引擎。

而JS的正則引擎是NFA，NFA是「非確定型有限自動機」的簡寫。

大部分語言中的正則都是NFA，為啥它這麼流行呢？

答：你別看我匹配慢，但是我編譯快啊，而且我還有趣哦。

感謝你看到這裡，本文也要結束了。

雖然本文大部分都是圖片，沒多少代碼，但也要說，

此時，我們該想到，陸遊詩人對前端做出的最大貢獻是：

紙上得來終覺淺，絕知此事要躬行。

關於本文

作者：@老姚

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！