【第977期】正則表達式回溯法原理

2021-02-21 前端早讀課

前言

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

正文從這開始～

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

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

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

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

內容包括：

1. 沒有回溯的匹配

2. 有回溯的匹配

3. 常見的回溯形式

1. 沒有回溯的匹配

假設我們的正則是/ab{1,3}c/，其可視化形式是：

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

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

2. 有回溯的匹配

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

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

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

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

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

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

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

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

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

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

3. 常見的回溯形式

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

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

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

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

3.1 貪婪量詞

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

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

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

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

var string = "12345";

var regex = /(\d{1,3})(\d{1,3})/;
console.log( string.match(regex) );

其中，前面的\d{1,3}匹配的是"123"，後面的\d{1,3}匹配的是"45"。

3.2 惰性量詞

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

var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );

其中\d{1,3}?只匹配到一個字符"1"，而後面的\d{1,3}匹配了"234"。

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

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

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

3.3 分支結構

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

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

比如正則：

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

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

後記

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

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

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

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

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

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

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

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

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

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

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

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

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

關於本文

作者：@老姚

原文：https://zhuanlan.zhihu.com/p/27417442

相關焦點

  • 第四章 正則表達式回溯法原理
    第四章 正則表達式回溯法原理學習正則表達式，是需要懂點兒匹配原理的。
  • php正則表達式基本知識與應用詳解
    常用的語言基本上都有正則表達式，如JavaScript、Java等。其實，只有了解一種語言的正則使用，其他語言的正則使用起來，就相對簡單些。文本主要圍繞解決下面問題展開。>⑫ 正則表達式之回溯與固態分組⑬ 正則優缺點有哪些正則表達式的基本知識匯總行定位符（^與$）行定位符是用來描述字符串的邊界。
  • Python正則表達式入門到入魔
    2、20世紀50年代一位名叫Stephen Kleene的數學科學家發表了一篇題目是《神經網事件的表示法》的論文，利用稱之為正則集合的數學符號來描述此模型，引入了正則表達式的概念。正則表達式被作為用來描述其稱之為「正則集的代數」的一種表達式，因而採用了「正則表達式」這個術語。
  • Matlab 正則表達式
    正則表達式是一個非常重要的編程概念，主流的程式語言都對正則表達式進行了很好的支持，Matlab也不例外。本期推文就讓我們來總結一下Matlab提供的正則表達式吧！3 字符串匹配3.1 多次匹配元字符及其特殊字符的匹配，每次只能匹配一個字符，如果需要匹配多個字符，即字符串的匹配，那麼就要重複好幾次元字符的表達式。比如，匹配 mmm，那麼就可以用正則表達式 mmm, 但還有一種更簡單的表示法 m{3}。
  • 看完你就會正則表達式了
    最近看了一篇關於正則表達式的學習筆記，覺得講的非常好，更有圖形化的神器相助，想不學會都難，所以想轉給大家看看。話說不是開發為啥要學正則表達式這種看似很晦澀的東西呢，因為現在很多搜索的場景都是支持正則表達式的，學會了正則表達式就有如一把利劍在手。本文較長，建議抽40分鐘完整的時間一次讀完再慢慢消化。
  • Java正則表達式基礎知識--5個學習步驟
    了解正則表達式概念及基本構造元素(本文目標);2. 通過練習能夠編寫出準確的可讀性較好的正則表達式，熟悉常用正則表達式;3. 理解正則引擎的內部機制及實現，能夠分析正則表達式的效率;4. 能夠編寫效率更高的正則表達式(以準確性和可讀性為前提);5. 能夠運用正則表達式去處理複雜的文本處理問題。1.
  • 刨根究底正則表達式(1):開篇
    正則表達式目前市面上並不缺乏專業著作，比如那本被譽為正則表達式學習聖經的《精通正則表達式》就很值得一讀，另外該書的譯者餘晟先生所寫的《正則指引》也不錯。如果僅用於入門，則《正則表達式必知必會》肯定不能錯過，還有網上流傳極廣的《正則表達式30分鐘入門教程》也是不錯的入門資料。但是，結合我自身痛苦的正則表達式學習經歷和運用體會，僅有這些是遠遠不夠的。
  • python正則表達式
    微信公眾號：學點啥玩點啥小白友好型python正則表達式 1#第7章 模式匹配與正則表達式
  • 給JAVA程式設計師的正則表達式一課
    正則基礎正則表達式（Regex，簡稱RE）是一種根據字符串集中的每個字符串的共同特徵來描述字符串集的方法。可用於搜索，編輯或處理文本和數據。簡單來說，正則表達式是幫助我們根據特定格式驗證或匹配字符串的方式。可以類比資料庫的SQL語言，sql是搜索數據，RE是搜索字符串。正則表達式和SQL語言是開發界的兩個偉大發明。
  • Python正則表達式總結
    正則表達式 的起源、發展、流派、語法、引擎、優化等相關知識，今天我們主要來學習一下 正則表達式在 Python語言 中的應用！9.TEMPLATE語法： re.TEMPLATE  或簡寫為 re.T作用： 豬哥也沒搞懂TEMPLATE的具體用處，源碼注釋中寫著：disable backtracking(禁用回溯)，有了解的同學可以留言告知！10.
  • 正則表達式在VBA中間是如何應用?正則表達式的實現方式?
    Hi，大家好，本章節開始將會從零開始和大家用圖文的方式，讓你從零基礎學會正則表達式！有興趣的小夥伴可以持續關注我，或者在專欄中進行查看自我學習，願與君攜手前行！在上一個章節說到正則表達式的入門級知識點，本節將會與大家分享一下正則表達式的是具體實現方式是怎麼樣的？
  • 正則表達式替換函數
    導讀在上篇推文《正則表達式匹配和提取函數》中簡單介紹了正則表達式的匹配和提取函數，並用一些簡單的例子向大家說明如何利用正則表達式匹配和提取文本。
  • JavaScript高級什麼是正則以及正則表達式的簡單運用
    在實際開發中 ，經常會用到一些表單的驗證 ，提交表單的時候一般都會預校驗 ，比如手機號填寫是否合格 ，用戶暱稱填寫是否規範等 ，這些就要用到正則表達式什麼是正則表達式？用於匹配規律規則的表達式，正則表達式最初是科學家對人類神經系統的工作原理的早期研究，現在在程式語言中有廣泛的應用。正則表通常被用來檢索、替換那些符合某個模式(規則)的文本。
  • Python 正則表達式
    最簡單的正則表達式就是普通字符串，可以匹配其自身。比如，正則表達式 『hello』 可以匹配字符串 『hello』。要注意的是，正則表達式並不是一個程序，而是用於處理字符串的一種模式，如果你想用它來處理字符串，就必須使用支持正則表達式的工具，比如 Linux 中的 awk, sed, grep，或者程式語言 Perl, Python, Java 等等。
  • 程式設計師入門基礎:python的正則表達式
    正則表達式是一個特殊的字符序列，它能幫助我們方便的檢查一個字符串是否與某種模式匹配。Python提供Perl 風格的正則表達式模式。re 模塊使 Python 語言擁有全部的正則表達式功能。一、正則表達式1、字符元素（可跳過）字符的匹配元素，比較瑣碎，簡單了解後即可，後期邊用邊查就記住了。
  • 教程精選:正則表達式快速入門<二>
    在上篇文章裡，我們介紹了正則表達式的模式修正符與元字符，細心的讀者也許會發現，這部分介紹的非常簡略，而且很少有實際的例子的講解。這主要是因為網上現有的正則表達式資料都對這部分都有詳細的介紹和眾多的例子，如果覺得對前一部分缺乏了解可以參看這些資料。本文希望可以儘可能多涉及一些較高級的正則表達式特性。
  • 正則表達式
    在我看來，正則表達式的主要用途有兩種：①查找特定的信息②查找並編輯特定的信息，也就是我們經常用的替換。。比如我們要在Word，記事本等裡面使用快捷鍵Ctrl+F，進行查找一個特定的字符，或者替換一個字符，這就使用了正則表達式。         正則表達式的功能非常強大，尤其是在文本數據進行處理中顯得更加突出。
  • python面試題匯總第06期-正則表達式(內附7題及答案)
    1.python正則表達式中匹配（match）和查找（search）的區別答：正則表達式中match和search的方法比較相似相同點：都是在一個字符串s中尋找pat子字符串，如果能找到，就返回一個Match對象，如果找不到，就返回None。不同點：mtach方法是從頭開始匹配，而search方法，可以在s字符串的任一位置查找。
  • python正則表達式,看完這篇文章就夠了...
    正則表達式，是一個特殊的字符序列，又稱規則表達式（英語：Regular Expression，在代碼中常簡寫為regex、regexp 或RE），本質而言是一種小型的，高度專業化的程式語言。Python 自1.5版本起增加了re 模塊，re 模塊使Python語言擁有全部的正則表達式功能。關於正則語法表，別想其他的都背過就行了。
  • Python正則表達式,這一篇就夠了!
    大多數程式語言的正則表達式設計都師從Perl，所以語法基本相似，不同的是每種語言都有自己的函數去支持正則，今天我們就來學習 Python中關於 正則表達式的函數。re模塊主要定義了9個常量、12個函數、1個異常，每個常量和函數豬哥都會通過實際代碼案例講解，讓大家能更直觀的了解其作用！註：為避免出現代碼格式錯亂，豬哥儘量使用代碼截圖演示哦。