正則表達(dá)式測試平臺:

最近，我正在為Lazada賣方中心進行自我注冊項目. 店鋪名稱驗證規(guī)則更加復(fù)雜. 要求是:

1. 英文字母大小寫

2. 數(shù)字

3. 越南語

4. 一些特殊字符，例如“＆”，“-”，“ _”等.

當(dāng)我看到這個要求時，我自然想到了正則表達(dá)式. 因此，有以下表達(dá)式（以比較形式編寫）:

^（[A-Za-z0-9 ._（）＆'\-] | [aAàà???áá????????????????a??????????bBcCdD??eEèè????éé??ê??êfê??????????FFgGhHiIìì????íí??jJkKlLmMnNoOòò????óó???????????????????????????pPQQrRsStTuTu]

在測試環(huán)境中，此表達(dá)式在功能上滿足了業(yè)務(wù)方的要求，并已發(fā)布到馬來西亞的環(huán)境中. 結(jié)果聯(lián)機后，發(fā)現(xiàn)聯(lián)機計算機的CPU飆升至100％，這導(dǎo)致整個站點的響應(yīng)速度異常緩慢. 通過轉(zhuǎn)儲線程跟蹤，發(fā)現(xiàn)所有線程都卡在此正則表達(dá)式的驗證中:

一開始令人難以置信，正則表達(dá)式匹配過程如何導(dǎo)致CPU變高？我以懷疑的態(tài)度搜索了數(shù)據(jù)，發(fā)現(xiàn)小的正則表達(dá)式中有很多文章. 它們通常以輕松的方式編寫. 只要他們能夠滿足功能要求，他們就會認(rèn)為自己已經(jīng)實現(xiàn)了目標(biāo)，并且完全忽略了可能帶來的后果. 隱藏的性能.

正是造成這種流血罪行的所謂常規(guī)“災(zāi)難性回溯”. 下面將詳細(xì)描述此問題，以避免重復(fù)相同的錯誤.

說到回溯陷阱，讓我們從正則表達(dá)式引擎開始. 常規(guī)引擎可以分為兩個基本類別: 一類是DFA（確定性有限自動機），另一類是NFA（不確定的有限自動機）. 簡而言之，NFA對應(yīng)于以正則表達(dá)式為主導(dǎo)的匹配，而DFA對應(yīng)于以文本為主導(dǎo)的匹配.

DFA從匹配的文本開始，從左到右，每個字符將不匹配兩次，其時間復(fù)雜度是多項式，因此通常更快，但是支持的功能很少，不支持捕獲組，各種引用，等等. ; NFA從正則表達(dá)式開始，并連續(xù)讀取字符以嘗試匹配當(dāng)前的正則性，并吐出字符以在不匹配時重試. 通常情況下，速度較慢且時間最佳. 復(fù)雜度是多項式，最壞的情況是指數(shù). 但是NFA支持更，因此在大多數(shù)編程方案（包括Java，js）中，我們都面臨NFA. 以下面的表達(dá)式和文字為例，

text =“今晚之后” regex =“ to（nite | nighta | night）”

當(dāng)NFA匹配時，根據(jù)正則表達(dá)式匹配文本. 從t匹配a，失敗，繼續(xù)直到文本中的第一個t，然后將o和e比較，失敗，常規(guī)回退到t，繼續(xù)直到文本中的第二個t，然后文本中的o和o也匹配，繼續(xù)，正則表達(dá)式后面有三個可選條件，依次匹配，第一個失敗，然后兩個java正則表達(dá)式詳解，三個直到匹配.

匹配DFA時，文本用于匹配正則表達(dá)式，從a到t匹配，直到第一個t匹配正則t，但是e不能匹配o，繼續(xù)直到文本第二個t其中匹配常規(guī)t，然后o匹配o. 當(dāng)n發(fā)現(xiàn)常規(guī)中存在三個可選匹配項時，它開始并行匹配，直到文本中的g使第一個可選條件不匹配為止，繼續(xù)，直到最后一個匹配項.

如您所見，在DFA匹配過程中，文本中的字符僅被比較了一次. 不吐出的操作應(yīng)比NFA快. 另外，無論正則表達(dá)式如何編寫，對于DFA，文本匹配過程都是一致的，并且文本的字符從左到右依次匹配，因此DFA在匹配過程中與正則表達(dá)式無關(guān)，而且NFA對于不同的正則表達(dá)式具有相同的作用，匹配過程完全不同.

在討論引擎之后，讓我們看看什么是回溯. 對于以下表達(dá)，我相信每個人都非常清楚其意圖，

ab {1,3} c

也就是說，中間的b需要匹配1?3次. 因此，對于文本“ abbbc”，根據(jù)第1部分中NFA引擎的匹配規(guī)則，不會發(fā)生回溯. 表達(dá)式中的a匹配后，b恰好完全匹配文本中的3 b，然后c匹配，一次全部匹配. 如果我們將文本更改為“ abc”怎么辦？它只不過是字母b缺失，而是發(fā)生了所謂的回溯. 匹配過程如下所示（橙色是匹配項，是不匹配項），

第1步到第2步應(yīng)該很容易理解，但是為什么要從第3步開始，盡管與b {1,3}匹配的文本中已經(jīng)有ab了，但是字母c和b {1,3會被拖到后面}比較呢？這是我們將在下面提到的常規(guī)貪婪功能，這意味著b {1,3}將盡最大可能匹配最多的字符. 在這個地方，我們首先知道它必須匹配，直到撞到南墻為止. 在這種情況下，步驟3中的不匹配之后，整個匹配過程沒有完成，但是字符c像堆棧一樣被吐出，然后使用正則表達(dá)式中的c來處理文本中的c. 比賽. 這發(fā)生了回溯.

讓我們看看什么是貪婪模式.

我相信每個人都知道如何使用以下特殊字符:

i. ？: 告訴引擎匹配領(lǐng)先字符0次或一次. 實際上，這意味著開頭字符是可選的.

ii. +: 告訴引擎一次或多次匹配前導(dǎo)字符.

iii. *: 告訴引擎匹配開頭字符0次或多次.

iv. {min，max}: 告訴引擎從最小到最大時間匹配前導(dǎo)字符. min和max均為非負(fù)整數(shù). 如果有逗號并且省略了max，則表示max沒有限制. 如果同時省略了逗號和max，則表示重復(fù)了min次.

默認(rèn)情況下，這些特殊字符是貪婪的，也就是說，它們將根據(jù)前導(dǎo)字符匹配盡可能多的內(nèi)容. 這解釋了為什么在第3部分的示例中，步驟3之后發(fā)生了事情.

在上述字符后添加問號（？）以啟用惰性模式. 在這種模式下，常規(guī)引擎將重復(fù)盡可能少的匹配字符. 匹配成功后，它將繼續(xù)匹配其余字符串. 在上面的示例中，如果將正則表達(dá)式更改為

?

ab {1,3}？c

匹配過程如下（橙色匹配，不匹配）

可以看出，在非貪婪模式下，在b {1,3}之后？步驟2中的b與文本b匹配，然后使用c匹配文本中的c而不回溯.

如果在上述四個表達(dá)式之后添加加號（+），則獨占模式將打開. 像貪婪模式一樣java正則表達(dá)式詳解，獨占模式將匹配最長的模式. 但是，在獨占模式下，正則表達(dá)式盡可能匹配字符串. 一旦比賽失敗，它將結(jié)束比賽而不會返回. 讓我們以下面的表達(dá)式為例，

?

ab {1,3} + bc

如果我們使用文本“ abbc”來匹配上述表達(dá)式，則匹配過程如下所示（橙色是匹配項，是不匹配項），

可以發(fā)現(xiàn)，在第2步和第3步中，b {1,3} +與文本中的兩個字母b匹配，而結(jié)果文本中僅保留一個字母c. 然后在第四步中，常規(guī)文本中的b與文本中的c匹配. 如果無法匹配，則不執(zhí)行回溯. 此時，整個文本無法與正則表達(dá)式匹配. 如果刪除了正則表達(dá)式中的加號（+），則整個文本匹配.

列出以下三種模式的表達(dá)式，如下所示:

貪婪

懶惰

獨家

X *

X * +

X +

X ++

X {n}

X {n}？

X {n} +

X {n，}

X {n，}？

X {n，} +

X {n，m}

X {n，m}？

X {n，m} +

現(xiàn)在回顧一下本文開頭的很長的正則表達(dá)式，實際上，經(jīng)過簡化后，它就像一個表格

^[允許字符集]+?

表達(dá)

. 字符集大小約為250，+號表示該字符集至少出現(xiàn)一次. 根據(jù)上述NFA引擎的貪婪模式，當(dāng)用戶輸入一個過長的字符串以進行匹配時，一旦發(fā)生回溯，計算量將很大. 后來，采用了獨占模式，也解決了100％CPU問題.

本文來自本站，轉(zhuǎn)載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-264557-1.html