目前越來越多的網(wǎng)站圆存、編輯器、編程語言都已支持一種叫“正則表達式”的字符串查找“公式”仇哆，有過編程經(jīng)驗的同學(xué)都應(yīng)該了解正則表達式（Regular Expression 簡寫regex）是什么東西沦辙，它是一種字符串匹配的模式（pattern），更像是一種邏輯公式讹剔。
使用正則表達式去匹配字符串Hello World 中的 Hello
偽代碼：/Hello/, "Hello World"
輸出：Hello
如何寫好一篇關(guān)于 正則表達式 的文章油讯，我思考了一周的時間详民，從未有一篇文章能讓豬哥如此費神。
因為我覺得正則表達式 ：難記憶撞羽、難描述阐斜、廣而深且不受重視衫冻，有人說正則表達式既好寫也難寫诀紊！
- 好寫：無非寫一些常用、實用的案例隅俘，說實話你們每個人都能寫出這種：在網(wǎng)上百度一下然后結(jié)合一點自己的實際經(jīng)驗邻奠，一篇文章就出來了。
- 難寫：很多人都認為正則簡單为居，不用記碌宴，要用就百度一下。但是絕大多數(shù)人了解的只是正則的一個小面蒙畴，真正的精髓卻很少關(guān)注贰镣！
豬哥希望大家能了解到正則的知識點其實非常非常多，尤其是正則引擎執(zhí)行原理以及正則優(yōu)化膳凝，這算是正則表達式的進階知識點碑隆，面試中也可能會被問到。
[圖片上傳失敗...(image-3b0c77-1582103764783)]
一蹬音、起源與發(fā)展
我們在學(xué)習(xí)一門技術(shù)的時候有必要了解其起源與發(fā)展過程上煤，這對我們?nèi)ダ斫饧夹g(shù)本身有一定的幫助！
20世紀40年代：正則表達式最初的想法來自兩位神經(jīng)學(xué)家：沃爾特·皮茨與麥卡洛克著淆，他們研究出了一種用數(shù)學(xué)方式來描述神經(jīng)網(wǎng)絡(luò)的模型劫狠。
1956年：一位名叫Stephen Kleene的數(shù)學(xué)科學(xué)家發(fā)表了一篇題目是《神經(jīng)網(wǎng)事件的表示法》的論文，利用稱之為正則集合的數(shù)學(xué)符號來描述此模型永部，引入了正則表達式的概念独泞。正則表達式被作為用來描述其稱之為“正則集的代數(shù)”的一種表達式，因而采用了“正則表達式”這個術(shù)語苔埋。
1968年：C語言之父阐肤、UNIX之父肯·湯普森把這個“正則表達式”的理論成果用于做一些搜索算法的研究，他描述了一種正則表達式的編譯器讲坎，于是出現(xiàn)了應(yīng)該算是最早的正則表達式的編譯器qed（這也就成為后來的grep編輯器）孕惜。
Unix使用正則之后，正則表達式不斷的發(fā)展壯大晨炕，然后大規(guī)模應(yīng)用于各種領(lǐng)域衫画，根據(jù)這些領(lǐng)域各自的條件需要，又發(fā)展出了許多版本的正則表達式瓮栗，出現(xiàn)了許多的分支削罩。我們把這些分支叫做“流派”瞄勾。
1987年：Perl語言誕生了，它綜合了其他的語言弥激，用正則表達式作為基礎(chǔ)进陡，開創(chuàng)了一個新的流派，Perl流派微服。之后很多編程語言如：Python趾疚、Java、Ruby以蕴、.Net糙麦、PHP等等在設(shè)計正則式支持的時候都參考Perl正則表達式。
[圖片上傳失敗...(image-665425-1582103764784)]
到這里我們也就知道為什么眾多編程語言的正則表達式基本一樣丛肮，因為他們都師從Perl赡磅。
注：Perl語言是一種擅長處理文本的語言，但因晦澀語法和古怪符號不利于理解和記憶導(dǎo)致很多開發(fā)者并不喜歡宝与。
二焚廊、語法
完整的正則表達式由兩種字符構(gòu)成：特殊字符（元字符）和普通字符。
ps：元字符表示正則表達式功能的最小單位习劫，如 * ^ $ \d 等等
關(guān)于語法部分豬哥并不想過多的講解咆瘟，給大家做一個詳細的歸納整理，供大家日后快速查找吧榜聂！
[圖片上傳失敗...(image-ce0ca5-1582103764784)]
如果想系統(tǒng)學(xué)習(xí)正則表達式的語法部分搞疗，豬哥推薦 菜鳥教程： https://www.runoob.com/regexp/regexp-tutorial.html
[圖片上傳失敗...(image-37202f-1582103764784)]
三、匹配原理
匹配原理是豬哥想要重點講解的部分须肆，也希望同學(xué)們可以認真了解這部分的內(nèi)容匿乃。
很多人覺得開車沒必要了解車的構(gòu)造原理，但是我們學(xué)編程的還真的需要了解原理豌汇。
因為了解原理幢炸，你才能調(diào)優(yōu)，這往往也是初級工程師與中高級工程師之間的差別點之一拒贱！
1.執(zhí)行過程
正則表達是的執(zhí)行宛徊，是由正則表達引擎編譯執(zhí)行的，大致的執(zhí)行流程豬哥也花了一個流程圖給大家看看逻澳。
[圖片上傳失敗...(image-3b5f71-1582103764784)]
這里給大家提一點就是：預(yù)編譯（pre-use compile）
豬哥建議大家在生產(chǎn)環(huán)境中使用預(yù)編譯功能闸天，為什么呢？
以Python語言內(nèi)置re模塊舉例：
- 通過
re.compile(pattern)預(yù)編譯返回Pattern對象斜做，在后面代碼中可以直接引用苞氮。 - 通過
re.match(pattern, text)即用編譯，雖然也會有緩存Pattern對象瓤逼，但是每次使用都需要去緩存中取出笼吟，比預(yù)編譯多一步取操作库物。
豬哥也通過實際測試來 驗證預(yù)編譯 確實比 即用編譯 要快！
pattern = r'http:\/\/(?:.?\w+)+'
text = '<a
[圖片上傳失敗...(image-1500a8-1582103764784)]
2.引擎
既然正則表達式由執(zhí)行引擎執(zhí)行贷帮，那我們就來講講正則表達式的引擎吧戚揭，這一塊是重點，希望大家仔細看看撵枢，弄懂了理解了才行民晒！
正則引擎主要可以分為基本不同的兩大類：
- DFA (Deterministic finite automaton) 確定型有窮自動機
- NFA (Non-deterministic finite automaton) 非確定型有窮自動機
ps：當(dāng)然還有一種引擎為：POSIX NFA，這是根據(jù)NFA引擎出的規(guī)范版本诲侮，但因為使用較少所以我們這里也就不重點講解镀虐。
這里需要和大家解釋下何為確定型箱蟆、有窮沟绪、自動機這幾個名詞：
- 確定型與非確定型：假設(shè)有一個字符串（text=abc）需要匹配，在沒有編寫正則表達式的前提下空猜，就直接可以確定字符匹配順序的就是確定型绽慈，不能確定字符匹配順序的則為非確定型。
- 有窮：有窮即表示有限的意思辈毯，這里表示有限次數(shù)內(nèi)能得到結(jié)果坝疼。
- 自動機：自動機便是自動完成，在我們設(shè)置好匹配規(guī)則后由引擎自動完成谆沃，不需要人為干預(yù)钝凶！
根據(jù)上面的解釋我們可得知DFA引擎 和 NFA引擎 的區(qū)別就在于：在沒有編寫正則表達式的前提下，是否能確定字符執(zhí)行順序唁影！
DFA引擎執(zhí)行原理：
為了大家能很清楚的理解DFA引擎執(zhí)行原理耕陷，豬哥制作了一個簡易的動態(tài)執(zhí)行過程圖給大家看看
根據(jù)上面的動圖我們可以得出DFA引擎的一些特點：
- 文本主導(dǎo)：按照文本的順序執(zhí)行，這也就能說明為什么DFA引擎是確定型(deterministic)了据沈，穩(wěn)定哟沫！
-
記錄當(dāng)前有效的所有可能：我們看到當(dāng)執(zhí)行到
(d|b)時，同時比較表達式中的d和b锌介，所以會需要更多的內(nèi)存嗜诀。 - 每個字符只檢查一次：這提高了執(zhí)行效率，而且速度與正則表達式無關(guān)孔祸。
- 不能使用反向引用等功能：因為每個字符只檢查一次隆敢，文本零寬度（位置）只記錄當(dāng)前比較值，所以不能使用反向引用崔慧、環(huán)視等一些功能拂蝎！
NFA引擎執(zhí)行原理：
豬哥同樣畫了一個簡易的NFA引擎執(zhí)行過程圖方便大家理解
根據(jù)上面的動圖我們可以得出NFA引擎的一些特點：
- 文表達式主導(dǎo)：按照表達式的一部分執(zhí)行，如果不匹配換其他部分繼續(xù)匹配尊浪，直到表達式匹配完成匣屡。
-
會記錄某個位置：我們看到當(dāng)執(zhí)行到
(d|b)時封救，NFA引擎會記錄字符的位置（零寬度），然后選擇其中一個先匹配捣作。 -
單個字符可能檢查多次：我們看到當(dāng)執(zhí)行到
(d|b)時誉结，比較d后發(fā)現(xiàn)不匹配，于是NFA引擎換表達式的另一個分支b券躁，同時文本位置回退惩坑，重新匹配字符'b'。這也是NFA引擎是非確定型的原因也拜，同時帶來另一個問題效率可能沒有DFA引擎高以舒。 - 可實現(xiàn)反向引用等功能：因為具有回退這一步，所以可以很容易的實現(xiàn)反向引用慢哈、環(huán)視等一些功能蔓钟！
針對兩種引擎的區(qū)別，豬哥進行了比較
[圖片上傳失敗...(image-5884f8-1582103764784)]
關(guān)于這兩種引擎的總結(jié)卵贱，豬哥引用《精通正則表達式》書本中的一句話來概括：
DFA（是電動機） 和NFA（汽油機） 都有很長的歷史滥沫，不過，正如汽油機一樣键俱，NFA 的歷史更長一些兰绣。也有些系統(tǒng)采用了混合引擎，它們會根據(jù)任務(wù)的不同選擇合適的引擎（甚至對同一表達式中的不同部分采用不同的引擎编振，以求得功能與速度之間的最佳平衡）缀辩。 ——《精通正則表達式》
3.回溯
作為絕大多數(shù)編程語言都選擇的引擎——NFA (非確定型有窮自動機) 引擎，我們當(dāng)然要再詳細了解一下它的精髓——回溯踪央。
動圖中臀玄，我們可以看到當(dāng)某個正則分支匹配不成功之后，文本的位置需要回退杯瞻，然后換另一個分支匹配镐牺，而回退這步專業(yè)術(shù)語就叫：回溯。
回溯的原理類似我們走迷宮時走過的路設(shè)置一個標(biāo)志物魁莉，如果不對則原路返回睬涧，換另一條路。
[圖片上傳失敗...(image-5d21a0-1582103764784)]
回溯機制不但需要重新計算正則表達式和文本的對應(yīng)位置旗唁，也需要維護括號內(nèi)的子表達式所匹配文本的狀態(tài)（b匹配成功）畦浓，保存到內(nèi)存中以數(shù)字編號的組中，這就叫捕獲組检疫。
保存括號內(nèi)的匹配結(jié)果之后讶请，我們在后面的正則表達式中就可以使用，這就是我們所說的反向引用，在上面的案例中只有一個捕獲夺溢，所以$1=b论巍。
回溯陷阱：講到回溯必須提到回溯陷阱，它導(dǎo)致的結(jié)果就是機器CPU使用率爆滿(超100%)风响，機器就卡死了嘉汰。
舉個例子：text=aaaaa，pattern=/^(a*)b$/状勤，匹配過程大致是
- (a*)：匹配到了文本中的aaaaa
- 匹配正則中的b鞋怀，但是失敗，因為(a*)已經(jīng)把text都吃了
- 這時候引擎會要求(a*)吐出最后一個字符(a)持搜，但是無法匹配b
- 第二次是吐出倒數(shù)第二個字符(還是a)密似，依然無法匹配
- 就這樣引擎會要求(a*)逐個將吃進去的字符都吐出來
- 但是到最后都無法匹配b
這里的重點就在于 引擎會要求*匹配的東西一點一點吐回，我們假設(shè)如果文本長度為幾萬葫盼，那引擎就要回溯幾萬次残腌，這對機器的CPU來說簡直是災(zāi)難。
有些復(fù)雜的正則表達式可能有多個部分都要回溯剪返，那回溯次數(shù)就是指數(shù)型废累。如果文本長度為500邓梅，一個表達式有兩部分都要回溯脱盲，那次數(shù)可能是500^2=25萬次，這誰受得了日缨！
關(guān)于更多更詳細的回溯介紹钱反，推薦大家可以閱讀《精通正則表達式》這本書！
四匣距、優(yōu)化
編寫巧妙的正則表達式不僅僅是一種技能面哥，而且還是一種藝術(shù)。
上面我們了解到毅待，絕大多數(shù)的編程語言都采用的是NFA引擎尚卫，而NFA引擎的特點是：功能強大、但有回溯機制所以效率慢尸红。所以我們需要學(xué)習(xí)一些NFA引擎的一些優(yōu)化技巧吱涉，以減少引擎回溯次數(shù)以及更直接的匹配到結(jié)果！
針對NFA引擎的可優(yōu)化的點其實挺多的外里，為了方便大家記憶怎爵，豬哥也畫幅結(jié)構(gòu)圖歸納一下，方便大家收藏細看盅蝗。
[圖片上傳失敗...(image-a79797-1582103764784)]
在面試過程中也許會被問到關(guān)于正則的優(yōu)化鳖链，大家記住幾點就可以。
五墩莫、推薦
上面我們講解了關(guān)于正則表達式的誕生和發(fā)展芙委、引擎逞敷、優(yōu)化等知識，但是關(guān)于正則表達式的知識點遠遠不止這些灌侣，所以最后豬哥推薦一些好的學(xué)習(xí)資料兰粉，大家有空可以了解學(xué)習(xí)下。
1.書
推薦正則表達式的書顶瞳，那必然是《精通正則表達式》 玖姑，目前這本書已經(jīng)出了第三版，豆瓣評分8.9慨菱。
內(nèi)容雖然稍有啰嗦焰络，但是對于正則新手很友好，唯一不足是Python案例少符喝。
[圖片上傳失敗...(image-b109f6-1582103764784)]
2.博客
入門：菜鳥教程：https://www.runoob.com/regexp/regexp-tutorial.html
深入：某不知名大佬：https://blog.csdn.net/lxcnn
3.在線測試工具
https://regex101.com/闪彼，這個網(wǎng)站可以選擇不同編程語言的正則支持，有語義分析协饲、匹配測試畏腕、參考列表等，非常實用茉稠。
[圖片上傳失敗...(image-6d81cc-1582103764784)]
4.常用案例
一些簡單常用的小案例匯總描馅，菜鳥教程：http://c.runoob.com/front-end/854
[圖片上傳失敗...(image-e90a78-1582103764784)]
最后祝愿大家都能搞定正則表達式，處理文本可以得心應(yīng)手而线！
更多優(yōu)質(zhì)教程可關(guān)注豬哥微信公眾號「裸睡的豬」铭污！
