dfa演算法和正則表達式過濾敏感詞

① 正則表達式之原理篇

背景

       最近公司規范出來後，關於字元串不提倡用 「 + 」  進行拼接，於是自己寫了個function，利用正則表達式來進行匹配。對於正則表達式，之前不了解原理，每胡和跡次要用的時候查一下，很浪費時間。

內容

基礎知識；

正則表達式引擎；

貪婪與非貪婪模式；

DFA與NFA引擎；

回溯機制及常見的回溯形式

基礎知識

1. 佔有字元：正則表達式匹配過程中，如果子表達式匹配到東西，而並非是一個位置，並最終保存到匹配的結果當中

2. 零寬度：只匹配一個位置，或者是匹配的內容並不保存到匹配結果中

一個字元，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配

3.控制權：正則表達式由左到右依次進行匹配，通常情況下是由一個表達式取得控制權，從字元串的的某個位置進行匹配，一個子表達式開始嘗試匹配的位置，是從前一子表達匹配成功的結束位置開始的（例如：（表達式一）（表達式二）意思就是表達式一匹配完成後才能匹配表達式二，而匹配表達式二的位置是從表達式一的位置匹配結束後的位置開始）。如果表達式一是零寬度，那表達式一匹配完成後，表達式二匹配的位置還是原來表達式以匹配的位置。也就是說它匹配開始和結束的位置是同一個

4. 元字元 

5. 反義元字元

6. 轉義字元：\  使元字元失去它的意義，僅代表其輸入中字元的意義

需要轉義的字元列表 \ * + ? | { [ ( ) ^ $ . # 和 空白

7. 重復限定符：匹配優先褲並量詞，忽略優先量詞，即：貪婪與非貪婪

{n,}、 {n, m}、 {, m}、 』+』 、『?』、 '*'

8. 字元類：[ ]，區分大小寫

9. 分支條件： |

10. 分組 ：（）指定子表達式，可限制多選項的范圍、將若干字元組合為一個單元、受問號或星號之類的量詞作用，例：(\d{1,3}){3}\d{3}

斷言；(?

11. 括弧及反向引用：（子表達式一）（子表達式二）\1      此時括弧作用為分組，它具有記憶的功能，即棚山在正則表達式內部仍然能回憶上次匹配到的是什麼；\1、\2、\n 是用在正則表達式的匹配環節。在正則表達式的替換環節，則要使用像 $1、$2、$n 這樣的語法

12. 平衡組 參考

正則表達式引擎

有兩個主要特點：

1. 默認貪婪匹配；（ 貪婪匹配與非貪婪匹配 ）

2. 返回最先匹配到的結果

針對簡單的正則匹配進行分析，例：

        當把cat應用到「He captured a catfish for his cat」，引擎先比較c和「H」，結果失敗了。於是引擎再比較c和「e」，也失敗了。直到第四個字元，c匹配了「c」。a匹配了第五個字元。到第六個字元t沒能匹配「p」，也失敗了。引擎再繼續從第五個字元重新檢查匹配性。直到第十五個字元開始，cat匹配上了「catfish」中的「cat」，正則表達式引擎急切的返回第一個匹配的結果，而不會再繼續查找是否有其他更好的匹配

Rubular: 基於 Web 的 Ruby 正則表達式編輯器

貪婪與非貪婪（又稱惰性、懶惰等）模式

兩者影響的是被量詞修飾的子表達式的行為。

貪婪模式在整個表達式匹配成功的前提下，盡可能多的匹配；而非貪婪模式（只被部分NFA引擎支持）在整個表達式匹配成功的前提下，盡可能少的匹配。

匹配優先量詞（屬於貪婪模式的量詞）：

「{m,n}」、「{m,}」、「?」、「*」和「+」。

忽略優先量詞（匹配優先量詞後加上「?」：非貪婪模式的量詞）：

「{m,n}?」、「{m,}?」、「??」、「*?」和「+?」

例：

源字元串：aa

正則表達式一：

正則表達式二：

DFA與NFA引擎（JS的正則引擎是NFA：非確定型有限自動機）

參考： 正則表達式引擎及其分類

DFA引擎：在線性時狀態下執行，不要求回溯（因此永遠不測試相同的字元兩次）；確保匹配最長的可能的字元串；因為只包含有限的狀態（？），所以它不能匹配具有反向引用的模式；並且因為它不構造顯示擴展，所以它不可以捕獲子表達式

傳統的NFA引擎：運行匹配回溯演算法——以指定順序測試正則表達式的所有可能的擴展並接受第一個匹配項。因為傳統的 NFA 構造正則表達式的特定擴展以獲得成功的匹配，所以它可以捕獲子表達式匹配和匹配的反向引用。但傳統 NFA的 回溯使它可以訪問完全相同的狀態多次（如果通過不同的路徑到達該狀態）。因此，在最壞情況下，它的執行速度可能非常慢。因為傳統的 NFA 接受它找到的第一個匹配，所以它還可能會導致其他（可能更長）匹配未被發現

POSIX NFA 引擎：與傳統 NFA 引擎類似，不同點：在可以確保已找到了可能的最長的匹配之前，它們將繼續回溯（更慢）；並且在使用 POSIX NFA 時，您恐怕不會願意在更改回溯搜索的順序的情況下來支持較短的匹配搜索，而非較長的匹配搜索

例：

字元串： this is yansen』s dog

正則表達式： /ya(msen|nsen|nsem)/

NFA工作方式：先在字元串中查找 y， 然後匹配其後是否為 a；  如果是 a 則繼續查找其後是否為 m； 如果不是則匹配其後是否為 n (此時淘汰 msen 支分支)； 然後繼續看其後是否依次為 s,e； 接著測試是否為 n ，是 n 則匹配成功，不是則測試是否為 m 。為什麼是 m ？因為 NFA 工作方式是以正則表達式為標准，反復測試字元串，這樣同樣一個字元串有可能被反復測試了很多次！

DFA：從 this 中 t 開始依次查找 y ，定位到 y ，已知其後為 a ，則查看錶達式是否有 a ，此處正好有 a； 然後字元串 a 後為 n ，DFA依次測試表達式，此時 msen 不符合要求淘汰。 nsen 和 nsem 符合要求，然後DFA依次檢查字元串，檢測到 sen 中的 n 時只有 nsen 分支符合，則匹配成功！

由此兩種引擎是完全不同的工作方式：NFA以表達式為主導，更容易操縱；DFA以文本為主導（搜索更快）

回溯機制

引擎是如何來處理那些模糊的條件匹配？

從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有「狀態」，當一條路走到「盡頭」的時候（不能再前進），再後退一步或若干步，從另一種可能「狀態」出發，繼續搜索，直到所有的「路徑」（狀態）都試探過。這種不斷「前進」、不斷「回溯」尋找解的方法，就稱作「回溯法」

--來自網路

本質上就是深度優先搜索演算法：嘗試匹配失敗時的下一步通常就是回溯

JS中正則表達式會產生回溯的地方都有哪些呢？

常見的回溯形式

1.貪婪量詞

例：正則：/ab{1,3}c/

可視化形式

1. 沒有回溯的匹配：當目標字元串是"abbbc"時

匹配過程

2. 有回溯的匹配：當目標字元串是「abbc」時

匹配過程

上圖第5步有紅顏色（僅表示匹配不成功）：此時b{1,3}已經匹配到了2個字元「b」，准備嘗試第三個時，結果發現接下來的字元是「c」。那麼就認為b{1,3}就已經匹配完畢。然後狀態又回到之前的狀態（即第6步，與第4步一樣），最後再用子表達式c，去匹配字元「c」。當然，此時整個表達式匹配成功了；上圖的第6步，就是「回溯」

即：嘗試可能的順序是「從多往少」的方向去嘗試：首先會嘗試"bbb"，然後再看整個正則是否能匹配。不能匹配時，吐出一個"b"，即在"bb"的基礎上，再繼續嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了

另一個清晰的回溯：

正則：/".*"/

目標字元串："acd"ef

省略了嘗試匹配雙引號失敗的匹配過程

其實「.*」最簡單但也是非常影響效率的

2.惰性量詞

雖然惰性量詞不貪，但也會有回溯的現象（為了整體匹配成）

正則表達式

目標字元串："12345"

匹配過程

3.分支結構

分支也是惰性的，比如/Java|JavaScript/，去匹配字元串"JavaScript"，得到的結果是"Java"，因為分支會一個一個嘗試，如果前面的滿足了，後面就不會再試驗了。

分支結構中可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續嘗試剩下的分支。這種嘗試也可以看成一種回溯：

正則表達式

匹配過程

雖然第五步沒有回到之前的狀態，但仍然回到了分支結構，嘗試下一種可能

總結：有回溯的過程，那麼匹配效率肯定比DFA相對低一些；別看匹配慢，但是編譯快而且還挺有趣

參考： 正則表達式的回溯機制

② 正則表達式原理

首先先講解下裂清正則表達式的基礎知識：

1.字元串的組成

對於字元串」123「而言，包括三個字元四個位置。如下圖所示：

2.佔有字元和零寬度

正則表達式匹配過程中，如果子表達式匹配到東西，而並非是一個位置，並最終保存到匹配的結果當中。這樣的就稱為佔有字元，而只匹配一個位置，或者是匹配的內容並不保存到匹配結果中，這種就稱作零寬度，後續會講到的零寬度斷言等。佔有字元是互斥的，零寬度是非互斥的。也就是一個字元，同一時間只能由一個子表達式匹配，而一個位置，卻可以同時由多個零寬度的子表達式匹配。

3.控制權和傳動

正則表達式由左到右依次進行匹配，通常情況下是由一個表達式取得控制權，從字元串的的某個位置進行匹配，一個子表達式開始嘗試匹配的位置，是從前一子表達匹配成功的結束位置開始的（例如：（表達式一）（表達式二）意思就是表達式一匹配完成後才能匹配表達式二局粗，而匹配表達式二的位置是從表達式一的位置匹配結束後的位置開始）。如果表達式一是零寬度，那表達式一匹配完成後，表達式二匹配的位置還是原來表達式以匹配的位置。也就是說它匹配開始和結束的位置是同一個。

舉一個簡單的例子進行說明：正則表達式：123

源數據：123

講解：首先正則表達式是從最左側開始進行匹配，也就是位置0處進行匹配，首先得到控制權的是正則表達式中的「1」，而不是源數據中的「1」，匹配源數據中的「1」，匹配成功，將源數據的「1」進行保存到匹配的結果當中，這就表明它佔有了一個字元，接下來就將控制權傳給正則表達式中的「2」，匹配的位置變成了位置1，匹配源數據中的「2」，匹配成功，將控制權又傳動給了正則桐源鎮表達式的「3」，這時候匹配的位置變成了位置2，這時候就會將源數據中的「3」進行匹配。又有正則表達式「3」進行傳動控制權，發現已經到了正則表達式的末尾，正則表達式結束。

③ 該正則表達式，用於過濾掉什麼內容呢:"\\([^()]*\\)"; （PHP）

是指提取括弧包裹的內容。
以下是我搜集的正則表達式應用及方法，希望對你有用。
匹配中文字元的正則表達式：[\u4e00-\u9fa5]
匹配雙位元組字元(包括漢字在內)：[^\x00-\xff]
匹配空白行的正則表達式：\n\s*\r
匹配HTML標記的正則表達式：<(\S*?)[^>]*>.*?</\1>|<.*? />
匹配首尾空白字元的正則表達式：^\s*|\s*$
匹配Email地址的正則表達式：\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*
匹配網址URL的正則表達式：[a-zA-z]+://[^\s]*
匹配身份證：\d{15}|\d{18}
匹配ip地址：\d+\.\d+\.\d+\.\d+

匹配特定數字：
^[1-9]\d*$
//匹配正整數

^-[1-9]\d*$ //匹配負整數

^-?[1-9]\d*$ //匹配整數

^[1-9]\d*|0$ //匹配非負整數（正整數 + 0）

^-[1-9]\d*|0$ //匹配非正整數（負整數 + 0）

^[1-9]\d*\.\d*|0\.\d*[1-9]\d*$ //匹配正浮點數

^-([1-9]\d*\.\d*|0\.\d*[1-9]\d*)$
//匹配負浮點數

^-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0)$
//匹配浮點數

^[1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0$
//匹配非負浮點數（正浮點數 + 0）

^(-([1-9]\d*\.\d*|0\.\d*[1-9]\d*))|0?\.0+|0$//匹配非正浮點數（負浮點數 + 0）匹配特定字元串：

^[A-Za-z]+$//匹配由26個英文字母組成的字元串

^[A-Z]+$//匹配由26個英文字母的大寫組成的字元串

^[a-z]+$//匹配由26個英文字母的小寫組成的字元串

^[A-Za-z0-9]+$//匹配由數字和26個英文字母組成的字元串

^\w+$//匹配由數字、26個英文字母或者下劃線組成的字元串

只能輸入數字：「^[0-9]*$」 只能輸入n位的數字：「^d{n}$」
只能輸入至少n位數字：「^d{n,}$」
只能輸入m-n位的數字：「^d{m,n}$」
只能輸入零和非零開頭的數字：「^(0|[1-9][0-9]*)$」
只能輸入有兩位小數的正實數：「^[0-9]+(.[0-9]{2}) $」
只能輸入有1-3位小數的正實數：「^[0-9]+(.[0-9]{1,3}) $」
只能輸入非零的正整數：「^+ [1-9][0-9]*$」
只能輸入非零的負整數：「^-[1-9][0-9]*$」
只能輸入長度為3的字元：「^.{3}$」
驗證用戶密碼:「^[a-zA-Z]w{5,17}$」正確格式為：以字母開頭，長度在6-18之間， 只能包含 字元、數字和下劃線。
驗證是否含有^%&',;= $"等字元：「[^%&',;= $x22]+」 只能輸入漢字：「^[u4e00-u9fa5],{0,}$」

④ 將正則表達式(aa|b)*a(a|bb)轉化成dfa

此正則表達式化簡後為a*b*即空字元串，或者僅由a組成的字元串，或者僅有b組成的字元串，或者由源輪若干a後面接若干b組成的字元串。

(A|B)*表示A或者B出現若干次或者不出現。

(A*B*)* A出現若干次或者不出現，B出現若干次或者不出現，一起出現若干次或者不出現

(A*|B*)* A出現若干次或者不出指裂現或者B出現若干次或者不出現，一起出現若干次或者不出現。

任何一個字元串都匹配這個字元串。

簡介

正則表達式是對字元串和特殊字元（稱為「元字元」））操作的一種邏輯公式，就是用事先定義好的一些特定字元、及這些特定字元的組合，組成一個「規則字元串」，這個「規則字元串」用來表達對字元串的一種過濾邏輯。正則表達式是一種文本唯裂閉模式，該模式描述在搜索文本時要匹配的一個或多個字元串。

⑤ 從正則表達式(RE)到最小確定性有限狀態自動機(DFA)

RE(Regular Expression)到最小DFA(Deterministic Finite Automaton)的轉換是構建正則表達式引擎的基礎,並且也是構建詞法分析器的基礎.

RE描述了一個定義在某個字母表Σ上的字元串集合L,並且空字元串ε也屬於L集合.形式化的定義並不好理解,但是相對其他非形式化的定義來說更加簡潔和准確.這里的正則表達式和平常所用的處理字元串的正則表達式是同一個,但是這里更加簡單.這里的RE只有三個基本的操作:
(1)選擇 取並集.符號:|. 比如兩個字元串集合R和S的選擇操作,記作R|S.
(2)連接 字元串之間的拼接.兩個字元串集合R和S的連接為RS.
(3)閉包 符號:* 字元串集合R的閉包R*是指把R與自身連接零次或者多次形成的所有集合的並集.
  由這幾個簡單的操作可以得到我們平常接觸的正則表達式的所有擴展.

我說的時候喜歡加上狀態兩個字,因為FA的關鍵動作就是狀態間的轉移.FA有一個狀態集S,對於每一個輸入都會讓FA的狀態進行轉移.如果能夠從起始狀態轉移到接受狀態,那麼輸入序列就被識州卜別了.不存在空字元串ε的狀態轉移.
  非確定性有限狀態自動機(Non-deterministic Finite Automaton,NFA).對於同一輸入轉移到多個不同的狀態或者存在空字元串ε的狀態轉移的FA.
  確定性有限狀態自動機(Deterministic Finite Automaton,DFA).對於任何確定的輸入都只有唯一確定的轉移且不存在空扒芹字元串ε的狀態轉移的FA.

上面描述的RE的基本操作的簡單NFA:

NFA到DFA 是對NFA的簡化過程.
  NFA到DFA的子集構造演算法(The Subset Construction):從將初始狀態劃分為一個初始狀態子集開始,構造狀態子集(經過零個或多個空字元串ε轉移到的狀態和已在子集中的狀態都是構造的新的狀態子集),存在c屬於字母表Σ,經過一個c的轉移(必須有c的轉移),能夠使得從狀態子集ni轉移到狀態子集nj,則在DFA中有在c的輸入下從狀態子集ni轉移到狀態子集nj的轉移.最後不再有新的狀態子集出現.根據狀態子集的轉移依次構造DFA.

最小化DFA用到的是等價狀態集合的劃分來構建.一開始只有兩個狀態集,一個接受狀態集合,一個非接受狀態集合.對於每一個狀態集合Sp,如果存在c屬於字母表Σ,使得Sp中的狀態轉移到不同的狀態集合(包括沒有冊此穗轉移的空狀態集合),則拆分Sp,使得拆分後的狀態集合中的每一個狀態不可能轉移到不同的狀態集合.其中狀態集合之間的轉移構成最小化DFA中的轉移.

⑥ 1-7 正則表表達式—查找功能

正則表達式和js配合可以完成3件事。

1. 查找一個固定的敏感詞出現的位置:
以往的方法： str.indexOf()
var i=str.indexOf("敏感詞",starti)；
在str中，從starti位置開始，查找下一個「敏感詞」的位置；
省略第二個參數starti，默認從0位置開始查找；
返回晌前值: 如果找到，返回敏感詞第一個字的位置；
如果找不到，返回-1；

問題: 只能查找一種固定的敏感詞。

2. 模糊查找符合正則表達式要求的敏感詞:
var i=str.search(/正則/);

問題1: 正則默認都是區分大小寫的
解決: 在第二個/後加後綴i, ignore

問題2: 只能返回位置i，無法返回敏感詞的內容。

3. 查詢敏感詞的內容，2種情況:

第一種、只查看第一個敏感詞的內容和位置:

問題: 正則表達式默認只找到第一個就退出；
解決: 在第二個/後加後綴g, global(全部);

第二中空種、 查找所有敏感詞的內容:

問題: 只能獲得內容，無法獲得位置；

4. 查找每個敏感詞的內容和位置: reg.exec()；賣謹瞎