亚洲欧美日韩综合系列在线_91精品人妻一区二区_欧美大肥婆一级特大AA片_九色91视频免费观看_亚洲综合国产精品_av中文字幕在线不卡_久久精品色综合网_看黄色视频的软件_无卡无码高清中文字幕码2024_亚洲欧美日韩天堂网

周末快到了，今天為大家送上一篇很有意思的小文章，具有提神醒腦之功效。作者是來(lái)自阿里巴巴LAZADA產(chǎn)品技術(shù)部的申徒童鞋。

1. 血案由來(lái)

近期我在為L(zhǎng)azada賣(mài)家中心做一個(gè)自助注冊(cè)的項(xiàng)目，其中的shop name校驗(yàn)規(guī)則較為復(fù)雜，要求：
1. 英文字母大小寫(xiě)
2. 數(shù)字
3. 越南文
4. 一些特殊字符，如“&”，“-”，“_”等
看到這個(gè)要求的時(shí)候，自然而然地想到了正則表達(dá)式。于是就有了下面的表達(dá)式（寫(xiě)的比較齪）：

在測(cè)試環(huán)境，這個(gè)表達(dá)式從功能上符合業(yè)務(wù)方的要求，就被發(fā)布到了馬來(lái)西亞的線上環(huán)境。結(jié)果上線之后，發(fā)現(xiàn)線上機(jī)器時(shí)有發(fā)生CPU飆到100%的情況，導(dǎo)致整個(gè)站點(diǎn)響應(yīng)異常緩慢。通過(guò)dump線程trace，才發(fā)現(xiàn)線程全部卡在了這個(gè)正則表達(dá)式的校驗(yàn)上：

一開(kāi)始難以置信，一個(gè)正則表達(dá)式的匹配過(guò)程怎么可能引發(fā)CPU飚高呢？抱著懷疑的態(tài)度去查了資料才發(fā)現(xiàn)小小的正則表達(dá)式里面竟然大有文章，平時(shí)寫(xiě)起來(lái)都是淺嘗輒止，只要能夠滿(mǎn)足功能需求，就認(rèn)為達(dá)到目的了，完全忽略了它可能帶來(lái)的性能隱患。

引發(fā)這次血案的就是所謂的正則“回溯陷阱（Catastrophic Backtracking）”。下面詳細(xì)介紹下這個(gè)問(wèn)題，以避免重蹈覆轍。

2. 正則表達(dá)式引擎

說(shuō)起回溯陷阱，要先從正則表達(dá)式的引擎說(shuō)起。正則引擎主要可以分為基本不同的兩大類(lèi)：一種是DFA（確定型有窮自動(dòng)機(jī)），另一種是NFA（不確定型有窮自動(dòng)機(jī)）。簡(jiǎn)單來(lái)講，NFA 對(duì)應(yīng)的是正則表達(dá)式主導(dǎo)的匹配，而 DFA 對(duì)應(yīng)的是文本主導(dǎo)的匹配。

DFA從匹配文本入手，從左到右，每個(gè)字符不會(huì)匹配兩次，它的時(shí)間復(fù)雜度是多項(xiàng)式的，所以通常情況下，它的速度更快，但支持的特性很少，不支持捕獲組、各種引用等等；而NFA則是從正則表達(dá)式入手，不斷讀入字符，嘗試是否匹配當(dāng)前正則，不匹配則吐出字符重新嘗試，通常它的速度比較慢，最優(yōu)時(shí)間復(fù)雜度為多項(xiàng)式的，最差情況為指數(shù)級(jí)的。但NFA支持更多的特性，因而絕大多數(shù)編程場(chǎng)景下（包括java，js），我們面對(duì)的是NFA。以下面的表達(dá)式和文本為例，

在NFA匹配時(shí)候，是根據(jù)正則表達(dá)式來(lái)匹配文本的，從t開(kāi)始匹配a，失敗，繼續(xù)，直到文本里面的第一個(gè)t，接著比較o和e，失敗，正則回退到 t，繼續(xù)，直到文本里面的第二個(gè)t，然后 o和文本里面的o也匹配，繼續(xù)，正則表達(dá)式后面有三個(gè)可選條件，依次匹配，第一個(gè)失敗，接著二、三，直到匹配。

而在DFA匹配時(shí)候，采用的是用文本來(lái)匹配正則表達(dá)式的方式，從a開(kāi)始匹配t，直到第一個(gè)t跟正則的t匹配，但e跟o匹配失敗，繼續(xù)，直到文本里面的第二個(gè) t 匹配正則的t，接著o與o匹配，n的時(shí)候發(fā)現(xiàn)正則里面有三個(gè)可選匹配，開(kāi)始并行匹配，直到文本中的g使得第一個(gè)可選條件不匹配，繼續(xù)，直到最后匹配。

可以看到，DFA匹配過(guò)程中文本中的字符每一個(gè)只比較了一次，沒(méi)有吐出的操作，應(yīng)該是快于NFA的。另外，不管正則表達(dá)式怎么寫(xiě)，對(duì)于DFA而言，文本的匹配過(guò)程是一致的，都是對(duì)文本的字符依次從左到右進(jìn)行匹配，所以，DFA在匹配過(guò)程中是跟正則表達(dá)式無(wú)關(guān)的，而 NFA 對(duì)于不同但效果相同的正則表達(dá)式，匹配過(guò)程是完全不同的。

3. 回溯

說(shuō)完了引擎，我們?cè)賮?lái)看看到底什么是回溯。對(duì)于下面這個(gè)表達(dá)式，相信大家很清楚它的意圖，

也就是說(shuō)中間的b需要匹配1~3次。那么對(duì)于文本“abbbc”，按照第1部分NFA引擎的匹配規(guī)則，其實(shí)是沒(méi)有發(fā)生回溯的，在表達(dá)式中的a匹配完成之后，b恰好和文本中的3個(gè)b完整匹配，之后是c發(fā)生匹配，一氣呵成。如果我們把文本換成“abc”呢？無(wú)非就是少了一個(gè)字母b，卻發(fā)生了所謂的回溯。匹配過(guò)程如下圖所示（橙色為匹配，黃色為不匹配），

1~2步應(yīng)該都好理解，但是為什么在第3步開(kāi)始，雖然已經(jīng)文本中已經(jīng)有一個(gè)b匹配了b{1,3}，后面還會(huì)拉著字母c跟b{1,3}做比較呢？這個(gè)就是我們下面將要提到的正則的貪婪特性，也就是說(shuō)b{1,3}會(huì)竭盡所能的匹配最多的字符。在這個(gè)地方我們先知道它一直要匹配到撞上南墻為止。 在這種情況下，第3步發(fā)生不匹配之后，整個(gè)匹配流程并沒(méi)有走完，而是像棧一樣，將字符c吐出來(lái)，然后去用正則表達(dá)式中的c去和文本中的c進(jìn)行匹配。這樣就發(fā)生了一次回溯。

4. 貪婪、懶惰與獨(dú)占

我們?cè)賮?lái)看一下究竟什么是貪婪模式。

下面的幾個(gè)特殊字符相信大家都知道它們的用法：

i. ?: 告訴引擎匹配前導(dǎo)字符0次或一次。事實(shí)上是表示前導(dǎo)字符是可選的。
ii. +: 告訴引擎匹配前導(dǎo)字符1次或多次。
iii. *: 告訴引擎匹配前導(dǎo)字符0次或多次。
iv. {min, max}: 告訴引擎匹配前導(dǎo)字符min次到max次。min和max都是非負(fù)整數(shù)。如果有逗號(hào)而max被省略了，則表示max沒(méi)有限制；如果逗號(hào)和max都被省略了，則表示重復(fù)min次。

默認(rèn)情況下，這個(gè)幾個(gè)特殊字符都是貪婪的，也就是說(shuō)，它會(huì)根據(jù)前導(dǎo)字符去匹配盡可能多的內(nèi)容。這也就解釋了為什么在第3部分的例子中，第3步以后的事情會(huì)發(fā)生了。

在以上字符后加上一個(gè)問(wèn)號(hào)（？）則可以開(kāi)啟懶惰模式，在該模式下，正則引擎盡可能少的重復(fù)匹配字符，匹配成功之后它會(huì)繼續(xù)匹配剩余的字符串。在上例中，如果將正則換為

則匹配過(guò)程變成了下面這樣（橙色為匹配，黃色為不匹配），

由此可見(jiàn)，在非貪婪模式下，第2步正則中的b{1,3}?與文本b匹配之后，接著去用c與文本中的c進(jìn)行匹配，而未發(fā)生回溯。

如果在以上四種表達(dá)式后加上一個(gè)加號(hào)（+），則會(huì)開(kāi)啟獨(dú)占模式。同貪婪模式一樣，獨(dú)占模式一樣會(huì)匹配最長(zhǎng)。不過(guò)在獨(dú)占模式下，正則表達(dá)式盡可能長(zhǎng)地去匹配字符串，一旦匹配不成功就會(huì)結(jié)束匹配而不會(huì)回溯。我們以下面的表達(dá)式為例，

如果我們用文本"abbc"去匹配上面的表達(dá)式，匹配的過(guò)程如下圖所示（橙色為匹配，黃色為不匹配），

可以發(fā)現(xiàn)，在第2和第3步，b{1,3}+會(huì)將文本中的2個(gè)字母b都匹配上，結(jié)果文本中只剩下一個(gè)字母c。那么在第4步時(shí)，正則中的b和文本中的c進(jìn)行匹配，當(dāng)無(wú)法匹配時(shí)，并不進(jìn)行回溯，這時(shí)候整個(gè)文本就無(wú)法和正則表達(dá)式發(fā)生匹配。如果將正則表達(dá)式中的加號(hào)（+）去掉，那么這個(gè)文本整體就是匹配的了。

把以上三種模式的表達(dá)式列出如下，

5. 總結(jié)

現(xiàn)在再回過(guò)頭看看文章開(kāi)頭的那個(gè)很長(zhǎng)的正則表達(dá)式，其實(shí)簡(jiǎn)化之后，就是一個(gè)形如

的表達(dá)式。該字符集大小約為250，而+號(hào)表示至少出現(xiàn)一次。按照上面說(shuō)到的NFA引擎貪婪模式，在用戶(hù)輸入一個(gè)過(guò)長(zhǎng)字符串進(jìn)行匹配時(shí)，一旦發(fā)生回溯，計(jì)算量將是巨大的。后來(lái)采用了獨(dú)占模式，CPU 100%的問(wèn)題也得到了解決。

因此，在自己寫(xiě)正則表達(dá)式的時(shí)候，一定不能大意，在實(shí)現(xiàn)功能的情況下，還要仔細(xì)考慮是否會(huì)帶來(lái)性能隱患。

關(guān)于正則表達(dá)式，你有哪些想要分享的特殊技能？歡迎在下面留言，一起交流探討。

原文地址http://www.cnblogs.com/study-everyday/p/7426862.html