這篇文章主要是分享最近在開(kāi)發(fā)中正則的學(xué)習(xí)心得體會(huì)。我們開(kāi)發(fā)，一開(kāi)始是采用python的正則庫(kù)，后來(lái)為了適應(yīng)Spring Cloud兼容Java所以正則也相應(yīng)的修改成為了Java版本，經(jīng)過(guò)測(cè)試，Java在匹配速度上相對(duì)慢了好多，平臺(tái)一天需要處理一億多條日志，但按照當(dāng)時(shí)的處理速度，每天差不多就只能處理了2千多萬(wàn)條，這樣的速度，實(shí)在扎心，提單申請(qǐng)擴(kuò)容，那邊的負(fù)責(zé)人說(shuō)資源不足，好咯，將Java所使用的正則庫(kù)替換成C++，C++夠快了吧，不過(guò)，這個(gè)庫(kù)是通過(guò)犧牲功能換取性能來(lái)實(shí)現(xiàn)的。
創(chuàng)新互聯(lián)公司公司2013年成立，先為芒市等服務(wù)建站，芒市等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢(xún)服務(wù)。為芒市企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
理論模型是有窮自動(dòng)機(jī),具體的實(shí)現(xiàn)為正則引擎(Regex Engine)分兩類(lèi)確定型有窮自動(dòng)機(jī)(Definite Finite Automata，DFA,其狀態(tài)都是確定)和非確定型有窮自動(dòng)機(jī)(Non-definite Finite Automate，NFA,其狀態(tài)在某個(gè)時(shí)刻是不確定的)。DFA和NFA是可以證明存在等價(jià)關(guān)系,不過(guò)這是兩種不同的自動(dòng)機(jī)。在這里，我才不會(huì)深入討論它們的原理。簡(jiǎn)單地說(shuō)，DFA 的時(shí)間復(fù)雜度是線性的。它更穩(wěn)定，但功能有限。NFA 的時(shí)間復(fù)雜度相對(duì)不穩(wěn)定。 根據(jù)正則表達(dá)式的不同，時(shí)間有時(shí)長(zhǎng)，有時(shí)短。NFA 的優(yōu)點(diǎn)是它的功能更強(qiáng)大，所以被 Java、.NET、Perl、Python、Ruby 和 PHP 用來(lái)處理正則表達(dá)式。 NFA 是怎樣進(jìn)行匹配的呢？我用下面的字符串和表達(dá)式作為例子。
text="A lovely cat."
regex="cat"
NFA 匹配是基于正則表達(dá)式的。也就是說(shuō)，NFA 將依次讀取正則表達(dá)式的匹配符，并將其與目標(biāo)字符串進(jìn)行匹配。如果匹配成功，它將轉(zhuǎn)到正則表達(dá)式的下一個(gè)匹配符。否則，它將繼續(xù)與目標(biāo)字符串的下一個(gè)字符進(jìn)行比較。 讓我們一步一步地來(lái)看一下上面的例子。
為了應(yīng)對(duì)NFA狀態(tài)不確定，可能會(huì)匹配出錯(cuò)誤的結(jié)果，因此需要“嘗試失敗-重新選擇”的過(guò)程，現(xiàn)在，我已經(jīng)解釋了 NFA 是如何進(jìn)行字符串匹配的——回溯法。我們將使用下面的例子，以便更好的解釋回朔法。
text="xyyyyyyz"
regex="xy{1,10}z"
這是一個(gè)比較簡(jiǎn)單的例子。正則表達(dá)式以 x 開(kāi)始，以 z 結(jié)束。它們之間有以 1-10 個(gè) y 組成的字符串。NFA 的匹配過(guò)程如下：
重慶分公司
重慶分公司
y{1,10}，將它與字符串的第二個(gè)字符 y 進(jìn)行比較。它們又匹配了。y{1,10} 代表 1-10 個(gè) y，基于 NFA 的貪婪特性（即，盡可能地進(jìn)行匹配），此時(shí)它不會(huì)讀取正則表達(dá)式的下一個(gè)匹配符，而是仍然使用y{1,10} 與字符串的第三個(gè)字符 y 進(jìn)行比較。它們匹配了。于是繼續(xù)用 y{1,10} 與字符串的第n個(gè)字符 y 進(jìn)行比較，直到第七個(gè)，它們不匹配。 回溯就出現(xiàn)在這里?標(biāo)志，貪婪模式將變成勉強(qiáng)模式。此時(shí)，它將盡可能少地匹配。然而，勉強(qiáng)模式下回溯仍可能出現(xiàn)。+標(biāo)志，則原來(lái)的貪婪模式將變成獨(dú)占模式。也就是說(shuō)，它將匹配盡可能多的字符，但不會(huì)回溯。text="xyyyyyyz"
regex="xy{1,10}?z"
正則表達(dá)式的第一個(gè)字符 x 與字符串的第一個(gè)字符 x 相匹配。正則表達(dá)式的第二個(gè)運(yùn)算符 y{1,10}? 匹配了字符串的第二個(gè)字符 y 。由于最小匹配的原則，正則表達(dá)式將讀取第三個(gè)運(yùn)算符 z，并與字符串第三個(gè)字符 y 進(jìn)行比較。兩者不匹配。因此，程序進(jìn)行回溯并將正則表達(dá)式的第二個(gè)運(yùn)算符 y{1,10}? 與字符串的第三個(gè)字符 y 進(jìn)行比較。還是匹配成功了。之后繼續(xù)匹配，正則表達(dá)式的第三個(gè)匹配符 c 與字符串的第七個(gè)字符 z 正相匹配。匹配結(jié)束。
這三種模式，在Python，Java這些常見(jiàn)的開(kāi)發(fā)工具中是比較常用的，然而在C++中并不是合適，我們開(kāi)發(fā)團(tuán)隊(duì)經(jīng)過(guò)一次次的修改、優(yōu)化，在性能調(diào)優(yōu)上才有了質(zhì)的飛躍。
下面以一份日志為例，介紹利用前面介紹的三種模式所開(kāi)發(fā)出來(lái)的模型匹配。
[INFO][08:27:34.260][2b0e7244d940]:LOGIN| client_id=007102| ip=8.8.8.8| uin=66666666 | mailname=123456789@139.com| userip=223.3.3.3|
我們想要的就是將日志中的數(shù)據(jù)進(jìn)行提取，獲得我們想要的內(nèi)容，其中包括，clientIP、userID、user、mobileNumber這些，因?yàn)檫€有其他數(shù)據(jù)描述，后續(xù)提高數(shù)據(jù)挖掘的效率，和對(duì)安全風(fēng)險(xiǎn)的分析能力，我們也想對(duì)這些日志進(jìn)行解析。一開(kāi)始我們使用貪婪模式，也就是常見(jiàn)的使用*，看圖中箭頭方向，這個(gè)步長(zhǎng)4635，大概需要11ms，步長(zhǎng)其實(shí)就是回溯的次數(shù)，迭代計(jì)算這么多次，對(duì)于性能來(lái)說(shuō)確實(shí)挺令人失望的，原因已經(jīng)很明顯了，就是由于*導(dǎo)致的，貪婪匹配n次直到和下個(gè)符號(hào)不匹配為止，因此消耗了大量的計(jì)算性能，這個(gè)也是我們需要進(jìn)行優(yōu)化地方。
^[(?P
.)][(?P . )][(?P.)].\=(?P .)|.\=(?P .)|.\=(?P .)|.\=(?P .)|.\=(?P .*)$
接下來(lái)開(kāi)始調(diào)優(yōu)對(duì)原來(lái)的貪婪模式追加勉強(qiáng)匹配（外文名詞翻譯真讓人抓狂），匹配效果卓著，原因在于勉強(qiáng)模式盡大努力地減少了回溯次數(shù)，在原來(lái)的回溯全文之后的基礎(chǔ)上，該模式如果遇匹配上了下個(gè)字符，立即結(jié)束，比如匹配type這個(gè)字段，我們的原先的貪婪模式，沒(méi)遇到一次就會(huì)全文都匹配一遍之后在回到起點(diǎn)，確認(rèn)匹配完成，而勉強(qiáng)模式則是在邊界就停下來(lái)，比如\],\[等字段。
到了這里我們并不滿足，是否還可以更快，對(duì)計(jì)算資源是否可以更友好？畢竟我們的計(jì)算資源很寶貴，于是可以繼續(xù)嘗試使用獨(dú)占模式。見(jiàn)下圖
^[(?P
.?)][(?P . ?)][(?P.?)].?\=(?P .?)|.?\=(?P .?)|.\=(?P .?)|.?\=(?P .?)|.?\=(?P .*?)$
在這個(gè)模式下我們的表達(dá)式性能得到了極大的提升，此時(shí)相較于初始版本，性能已經(jīng)提高了十倍，稱(chēng)之為勉強(qiáng)追加獨(dú)占模式，該匹配已經(jīng)匹配了，基本上可以交差給服務(wù)器日夜不停工作了。
此時(shí)性能看起來(lái)已經(jīng)達(dá)到了最優(yōu)了，但我們要考慮到表達(dá)式的健壯性，畢竟在眾多的日志里，總會(huì)出現(xiàn)有些字段為空（并不是null）的情況，如下圖所示，我特意刪除一些字段，如果是空格還好，當(dāng)不是的時(shí)候又應(yīng)該怎么處理咧？
這里需要使用|這個(gè)符號(hào)，對(duì)這樣的場(chǎng)景經(jīng)行適配,此時(shí)不管是空的還是有數(shù)據(jù)的都沒(méi)啥關(guān)系了，我們已經(jīng)做好了應(yīng)對(duì)準(zhǔn)備。
^[(?P
.+?)][(?P .+?)][(?P .+?)].+?\=(?P .+?)|.+?\=(?P .+?)|.*\=(?P .+?)|.+?\=(?P .+?)|.+?\=(?P .+?)$
[(?P
|.+?)][(?P |.+?)][(?P |.+?)].+?\=(?P |.+?)|.+?\=(?P |.+?)|.*\=(?P |.+?)|.+?\=(?P |.+?)|.+?\=(?P .+|)
這里我特意刪除^和$這兩個(gè)字符，考慮到在這個(gè)場(chǎng)景下，其實(shí)沒(méi)必要規(guī)定起止符，因?yàn)槲覀兪侨钠ヅ涞?，起止符的出現(xiàn)反而需要計(jì)算機(jī)再驗(yàn)證一次是否到了終點(diǎn)，確定一下自己是不是在起點(diǎn)，有點(diǎn)畫(huà)蛇添足。
在生產(chǎn)環(huán)境中學(xué)習(xí)很快，尷尬的就是沒(méi)時(shí)間沉淀，生產(chǎn)的過(guò)程中遇到了好多我覺(jué)得是經(jīng)典的場(chǎng)景，時(shí)間不允許匆匆留在工作筆記中，還沒(méi)探究出所以然。之前以為我學(xué)會(huì)了正則，搞爬蟲(chóng)嘛，對(duì)正則也是要有一定的理解的，在進(jìn)行模型分析的這段時(shí)間越發(fā)看不懂正則，總覺(jué)得這個(gè)是在寫(xiě)啥，官網(wǎng)說(shuō)的是啥，看文檔，現(xiàn)在寫(xiě)正則舒服很多了，處理日志各種不規(guī)范，提供的日志規(guī)范和接收到日志70%以上是不匹配的，還有拼寫(xiě)錯(cuò)誤 ，各種命名法， 形式翻新，永不重復(fù)，這叫一個(gè)皮。。。
在線正則測(cè)試網(wǎng)站
這個(gè)網(wǎng)站可以很明顯的提示我們表達(dá)式中的錯(cuò)誤內(nèi)容，或者說(shuō)不符合語(yǔ)法規(guī)則的地方。跟我們說(shuō)明該表達(dá)式的性能特點(diǎn)，消耗的資源等信息。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。
