粗略探究一下正則表達(dá)式的實(shí)現(xiàn)原理
轉(zhuǎn)自我的個(gè)人微博
會(huì)進(jìn)來(lái)看這篇分享的同學(xué)映穗，應(yīng)該已經(jīng)大概知道正則表達(dá)式是什么了（以下簡(jiǎn)稱 RE），而且應(yīng)該多多少少有使用過(guò)薇宠，感受過(guò) RE 的用途似炎。所以我就直接進(jìn)入正題势决，從 RE 的三大基本操作開(kāi)始介紹蟹瘾。
RE 三個(gè)基本操作：選擇贾费，連接和閉包
RE 對(duì)于大部分程序員來(lái)說(shuō)并不陌生吕世，但當(dāng)提到 RE 的三個(gè)基本操作的時(shí)候就沒(méi)什么概念了碑幅。所謂基本操作戴陡，就是構(gòu)成 RE 的基石，只要實(shí)現(xiàn)了這幾個(gè)基本操作沟涨，理論上就可以通過(guò)這幾個(gè)操作的拼接和嵌套來(lái)應(yīng)付（幾乎）所有的表達(dá)式恤批。他們就是下面這三個(gè)操作：
- 選擇：即取并集。符號(hào)為
|裹赴，即我們常在 RE 中看到的A|B喜庞，意為匹配A或者B中的一個(gè) - 連接：表達(dá)式之間的連接。即我們常在 RE 中看到的
AB棋返，意為匹配一個(gè)B出現(xiàn)在一個(gè)A之后的模式 - 閉包：自身連接0次或者多次延都。符號(hào)為
*,即我們常在 RE 中看到的A*【ⅲ可能有人會(huì)疑惑為什么只有*而沒(méi)有?和+晰房，這部分同學(xué)可以帶著這個(gè)問(wèn)題看下去就懂了。
上述三個(gè)就是 RE 的三個(gè)基本操作，同學(xué)們可以想象一下是否“所有”的表達(dá)式都可以看成是上述三個(gè)操作的拼接和嵌套殊者。這里“所有”打上引號(hào)是因?yàn)椴⒎钦娴氖撬杏刖常驗(yàn)檎齽t表達(dá)式發(fā)展至今已經(jīng)不是最初的樣子，技術(shù)人員為了方便不斷給 RE 添加新功能猖吴，所以現(xiàn)在有好幾個(gè)不同版本的正則表達(dá)式標(biāo)準(zhǔn)摔刁，有些新功能的實(shí)現(xiàn)方式并不能通過(guò)上述三個(gè)操作來(lái)實(shí)現(xiàn)，但是我們今天不討論這些或巧妙或復(fù)雜的新技術(shù)排除在外海蔽，只討論原始樸素的正則表達(dá)式共屈。
用有限狀態(tài)自動(dòng)機(jī)實(shí)現(xiàn) RE
現(xiàn)在我們知道了 RE 的三大基本操作，所以目標(biāo)就是想辦法實(shí)現(xiàn)這三種基本操作党窜。這時(shí)候就需要用到有限狀態(tài)自動(dòng)機(jī)（Finite Status Automaton拗引，F(xiàn)SA）這個(gè)工具了。有 ASR 或者 NLP 經(jīng)驗(yàn)的同學(xué)應(yīng)該比較熟悉自動(dòng)機(jī)的概念刑然。簡(jiǎn)單來(lái)說(shuō)寺擂，F(xiàn)SA 就是一個(gè)規(guī)定了事物在不同狀態(tài)之間達(dá)到什么條件才會(huì)轉(zhuǎn)換的機(jī)制暇务。下面我畫(huà)了一個(gè) HO 在兩個(gè)不同狀態(tài)之間轉(zhuǎn)換的簡(jiǎn)易 FSA 示意圖（不是很嚴(yán)謹(jǐn)泼掠，僅供理解）：
我們可以看到，把上述這種 FSA 寫(xiě)成代碼流程也是比較自然的過(guò)程垦细，只要用條件判斷控制（if()）狀態(tài)轉(zhuǎn)換就行择镇。那么， 怎么用 FSA 來(lái)表示 RE 的匹配過(guò)程呢括改？
用 FSA 表示 RE 基本操作
先從連接操作開(kāi)始說(shuō)起腻豌。假設(shè)我們就想匹配字符串“ab”，對(duì)應(yīng)的正則表達(dá)式就是 ab嘱能。相當(dāng)于用 FSA 表示如下：
如果輸入字符串能從狀態(tài) 0 轉(zhuǎn)換到狀態(tài) 2吝梅，就返回匹配成功，反之就是匹配失敗惹骂，該字符串和正則表達(dá)式不匹配苏携。
上述正則表達(dá)式 ab 相當(dāng)于是 [匹配字符串 “a”] 和 [匹配字符串 “b”] 這兩個(gè)子表達(dá)式進(jìn)行連接操作。所以更一般的对粪，如果我們想連接兩個(gè)子表達(dá)式 A 和 B（而不是單純的連接字符串 “a” 和 “b”）右冻，我們可以像這樣表示：
其中的 表示不需要任何條件就能跳轉(zhuǎn)。上面那幅圖簡(jiǎn)化一下就是這樣：
以此類推纱扭，兩個(gè)子表達(dá)式的選擇操作（A|B）就可以表示成這樣：
上面這個(gè) FSA 表示儡遮，輸入的表達(dá)式只需要有一條路（通過(guò)子表達(dá)式 A 或者通過(guò)表達(dá)式 B）能從狀態(tài) 0 轉(zhuǎn)換到狀態(tài) 1 就算匹配成功乳蛾。
然后到閉包。可能還有一些同學(xué)在像為啥閉包只要討論 * 而不管 ? 和 +肃叶，畢竟每次要用到這三個(gè)操作的時(shí)候我們一般都是一起考慮然后在這三個(gè)里面挑一個(gè)最合適的忆首。那么我們就先從 ? 開(kāi)始討論。
A? 表示表達(dá)式 A 匹配 1 次或者 0 次被环。用 FSA 可以這樣表示：
A+ 表示表達(dá)式 A 匹配 1 次或一次以上：
最后糙及， A* 表示表達(dá)式 A 匹配 0 次 或 0 次以上，它的 FSA 我就不畫(huà)了筛欢，可能想象力比較好的同學(xué)已經(jīng)自己腦海里有圖像了浸锨，一時(shí)想象不出來(lái)的同學(xué)可以自己動(dòng)手畫(huà)一下看看。其實(shí)就算上述兩個(gè) FSA 的結(jié)合版姑。
至此我們已經(jīng)能用 FSA 表示出正則表達(dá)式的三個(gè)基本操作柱搜，接下來(lái)我們實(shí)際應(yīng)用一把，感受一下如何用 FSA 來(lái)解決實(shí)際的正則表達(dá)式剥险。
用 FSA 實(shí)現(xiàn)表達(dá)式 A(B|C)*
首先聪蘸，最開(kāi)始的 A 用 FSA 畫(huà)出來(lái)就是：
然后，回憶一下 B|C 應(yīng)該長(zhǎng)什么樣:
接下來(lái)就用到了我們上面推出來(lái)的閉包 (B|C)*表制，這里把 (B|C) 看成一個(gè)整體就跟上一節(jié)討論的 A* 一樣健爬，來(lái)看看跟你想的（畫(huà)的）是不是一樣:
最后，就只要把 A 和 (B|C)* 做一個(gè)連接操作就行：
至此么介，正則表達(dá)式 A(B|C)* 的有限狀態(tài)機(jī)就構(gòu)造完成了娜遵。不過(guò)可能大部分同學(xué)都會(huì)覺(jué)得這個(gè)圖看著很別扭，好像有哪里不對(duì)壤短，但是看上去又完全符合要求设拟。是的，上圖確實(shí)找不到任何“錯(cuò)誤”久脯，但是又有很多不合理的地方纳胧。眼尖的同學(xué)可能一眼就已經(jīng)看出，上述狀態(tài)圖中的狀態(tài) 1 和狀態(tài) 2 完全就是等價(jià)的嘛帘撰，3跑慕，4也是。確實(shí)如此骡和，上述設(shè)計(jì)雖然不回導(dǎo)致字符串的異常匹配相赁，但是匹配效率上還有很大的可提升空間。
接下來(lái)我們就討論 FSA 的優(yōu)化過(guò)程慰于。
從 NFA 到 DFA
我們還是從表達(dá)式 a(b|c)* 開(kāi)始討論钮科，注意我這里沒(méi)有用大寫(xiě)的字母 ABC 來(lái)表示子表達(dá)式，因?yàn)樽颖硎緯?huì)把表達(dá)式內(nèi)部的狀態(tài)給隱藏掉婆赠，所以我這里舉的例子就是直接用小寫(xiě)得字母 abc 來(lái)表示他們的原始含義绵脯，即單純的匹配“字母 a 后面接0個(gè)或多個(gè) b 再接0個(gè)或多個(gè) c ”的字符串佳励。對(duì)應(yīng)的 FSA 如下所示，跟上一節(jié)最后的圖很像蛆挫，只是這個(gè)圖里沒(méi)有子表達(dá)式赃承，都是一個(gè)個(gè)的狀態(tài)加轉(zhuǎn)換條件。還有下圖中我加了個(gè)長(zhǎng)得不一樣的狀態(tài) 5悴侵，像這種樣式的狀態(tài)我們稱之為接受態(tài)或終止態(tài)瞧剖，一旦達(dá)到這種狀態(tài)意味著匹配成功，前面我都沒(méi)有加是因?yàn)閷?duì)前面講的內(nèi)容沒(méi)有影響可免，但是接受態(tài)在后面 FSA 的優(yōu)化過(guò)程中很關(guān)鍵抓于，請(qǐng)大家留個(gè)心眼。
注意觀察上述示意圖浇借，我們可以看到兩個(gè)特征：
- 圖中有很多可任意跳轉(zhuǎn)的邊捉撮，即 epsilon 邊
- 給一個(gè)跳轉(zhuǎn)條件，可以跳轉(zhuǎn)到的狀態(tài)是不確定的妇垢。
上述第一點(diǎn)顯而易見(jiàn)巾遭。第二點(diǎn)稍微解釋一下，我舉個(gè)例子闯估，假設(shè)現(xiàn)在狀態(tài) 0灼舍，且滿足條件 a，然后它能跳轉(zhuǎn)到狀態(tài) 1睬愤、4片仿、5 中的一個(gè)，就是說(shuō)它最終跳轉(zhuǎn)到哪個(gè)狀態(tài)是不能確定的尤辱。對(duì)于這種自動(dòng)狀態(tài)機(jī)，我們就叫它“非確定性有限狀態(tài)自動(dòng)機(jī)（Non-deterministic Finite Automaton, NFA）”厢岂。
想要優(yōu)化它需要用到“子集構(gòu)造算法”光督。 該算法的專業(yè)定義如下，不過(guò)不結(jié)合實(shí)例看這個(gè)定義基本是看不懂的塔粒，所以后面我直接用上述例子（a(b|c)*）演示一遍结借。
子集構(gòu)造算法：從將初始狀態(tài)劃分為一個(gè)初始狀態(tài)子集開(kāi)始,構(gòu)造狀態(tài)子集(經(jīng)過(guò)零個(gè)或多個(gè)空字符串ε轉(zhuǎn)移到的狀態(tài)和已在子集中的狀態(tài)都是構(gòu)造的新的狀態(tài)子集),存在c屬于字母表Σ,經(jīng)過(guò)一個(gè)c的轉(zhuǎn)移(必須有c的轉(zhuǎn)移),能夠使得從狀態(tài)子集 i轉(zhuǎn)移到狀態(tài)子集 j, 則在DFA中有在c的輸入下從狀態(tài)子集 i 轉(zhuǎn)移到狀態(tài)子集 j 的轉(zhuǎn)移.直到最后不再有新的狀態(tài)子集出現(xiàn).根據(jù)狀態(tài)子集的轉(zhuǎn)移依次構(gòu)造DFA.
先構(gòu)建初始狀態(tài)子集（定義見(jiàn)上），說(shuō)白了就是從初始狀態(tài) 0 出發(fā)卒茬，可以通過(guò) 0 條或多條 邊能到達(dá)的所有狀態(tài)的集合（這就是子集的概念船老，后面每一步都會(huì)用到）。上述例子中我們看到圃酵，狀態(tài) 0 通過(guò)
邊哪里都去不了柳畔，所以初始狀態(tài)子集只有狀態(tài) 0 一個(gè)元素。我們構(gòu)造這么一個(gè)表格郭赐，來(lái)方便看出各個(gè)狀態(tài)子集通過(guò)不同的邊能到達(dá)的狀態(tài)集合薪韩。
可以看到，通過(guò)初始狀態(tài)“零”通過(guò)邊 a，能夠到達(dá)的狀態(tài)有狀態(tài) 1俘陷、4罗捎、5，而通過(guò)邊 b 和 c 都不能到達(dá)任何狀態(tài)拉盾。所以我們又得到了一個(gè)狀態(tài)子集 {1, 4, 5}桨菜。
重復(fù)上述過(guò)程，知道沒(méi)有新的狀態(tài)產(chǎn)生捉偏。最后我們得到這樣的表格雷激。
如此，我們得到了 4 種新?tīng)顟B(tài)以及他們之間的轉(zhuǎn)換關(guān)系告私。因此我們可以構(gòu)建新的 FSA屎暇。
再看 NFA 的兩個(gè)特征：
- 圖中有很多可任意跳轉(zhuǎn)的邊，即 epsilon 邊
- 給一個(gè)跳轉(zhuǎn)條件驻粟，可以跳轉(zhuǎn)到的狀態(tài)是不確定的根悼。
對(duì)比上述這個(gè)新的 FSA，是不是上述兩條都已經(jīng)不滿足了蜀撑。我們稱這種新的 FSA 為 “確定性有限狀態(tài)自動(dòng)機(jī)（Deterministic Finite Automaton, DFA）” 挤巡。我們可以自己拿例子過(guò)一遍這個(gè)自動(dòng)機(jī)，驗(yàn)證它是否滿足 a(b|c)*酷麦。這里可能令人不解的點(diǎn)是：這個(gè)圖怎么有三個(gè)接受態(tài)矿卑。。沃饶。母廷？沒(méi)錯(cuò)，F(xiàn)SA 并沒(méi)有規(guī)定接受態(tài)只能有一個(gè)糊肤，只要能轉(zhuǎn)移到任何一個(gè)接受態(tài)琴昆，此次匹配就算成功」萑啵“那业舍。。升酣。憑什么狀態(tài)一舷暮、二、三可以是接受態(tài)呢噩茄？”下面。這就要看上面那個(gè)表格了，原來(lái)的 NFA 中的接受態(tài)是狀態(tài) 5巢墅，因此只要包含了原狀態(tài) 5的狀態(tài)子集在 DFA 中也是接受態(tài)诸狭。
從 DFA 到 DFA
可能有人覺(jué)得上述優(yōu)化后的 DFA 已經(jīng)足夠簡(jiǎn)潔券膀，沒(méi)有優(yōu)化的空間了。事實(shí)是它還能優(yōu)化的跟簡(jiǎn)潔驯遇，達(dá)到更快的匹配效率芹彬。這種優(yōu)化方法被稱為等價(jià)狀態(tài)集合劃分。照例叉庐，先給定義舒帮。
等價(jià)狀態(tài)集合劃分：一開(kāi)始只有兩個(gè)狀態(tài)集,一個(gè)接受（終止）狀態(tài)集合,一個(gè)非接受（非終止）狀態(tài)集合.對(duì)于每一個(gè)狀態(tài)集合Sp,如果存在c屬于字母表Σ,使得Sp中的狀態(tài)轉(zhuǎn)移到不同的狀態(tài)集合(包括沒(méi)有轉(zhuǎn)移的空狀態(tài)集合),則拆分Sp,使得拆分后的狀態(tài)集合中的每一個(gè)狀態(tài)不可能轉(zhuǎn)移到不同的狀態(tài)集合.其中狀態(tài)集合之間的轉(zhuǎn)移構(gòu)成最小化DFA中的轉(zhuǎn)移.
我們繼續(xù)還是已上述的例子來(lái)演示（雖然這不是個(gè)好例子）。
第一步就是分兩個(gè)狀態(tài)集陡叠，判斷標(biāo)準(zhǔn)是該狀態(tài)是否為接受態(tài)玩郊。因此我們把狀態(tài)零（只有它不是接受態(tài)）單獨(dú)分為一個(gè)狀態(tài)集 Sp，而狀態(tài)一枉阵、二译红、三分為另一個(gè)狀態(tài)集 Sp
。
然后兴溜，判斷是否存在邊 c 連接了不同的狀態(tài)集侦厚，如果有的話，把相關(guān)的狀態(tài)單獨(dú)分出來(lái)拙徽。但是我們這個(gè)例子中沒(méi)有這種邊（所以我說(shuō)這不是個(gè)很好的例子刨沦，同學(xué)們感興趣的話可以自己找別的例子試一試），因此不需要任何迭代膘怕。所以我們最終得到的 FSA 示意圖長(zhǎng)這樣想诅。
是不是出乎意料的簡(jiǎn)潔，但是帶入例子驗(yàn)證之后確實(shí)是邏輯合理的岛心。
這個(gè)最終優(yōu)化出來(lái)的 FSA 我們稱之為 “最小確定性有限狀態(tài)自動(dòng)機(jī)（Minimal deterministic Finite Automaton, DFA°）”来破。
總結(jié)
至此，我們的正則表達(dá)式探索之旅也接近尾聲了鹉梨。我們可以看到讳癌，NFA 構(gòu)造起來(lái)最簡(jiǎn)單，但是也是構(gòu)造出來(lái)的狀態(tài)機(jī)冗余操作很多存皂，匹配的時(shí)候甚至需要用到回溯（因?yàn)樗牟淮_定性）；而 DFA° 構(gòu)造過(guò)程很長(zhǎng)逢艘，需要一步一步推出來(lái)旦袋，但是構(gòu)造好之后，推理過(guò)程也是前面兩種 FSA 難以比擬的它改。目前常用的 RE 引擎基本都是 DFA 和 DFA° 兩種混用的解決方案疤孕，根據(jù)具體的使用場(chǎng)景來(lái)定具體的實(shí)現(xiàn)方式。
