- 使用正則運算式描述模式
- 非確定有限狀態自動機NFA
- 模擬NFA的運行
- NFA的表示
- 構造與正則運算式相對應的NFA
- NFA的模擬與可達性
除了查找子字串，在很多時候并不知道被查找模式的完整資訊，這時就需要用到正則運算式了，正則運算式在子字串查找、合法性校驗、網路爬蟲等方面有著非常廣泛的應用，
使用正則運算式描述模式
正則運算式對模式的描述，基于幾個基本操作，
- 連接操作，比如AB，表示由A和B連接而成的模式，
- 或操作，或操作可以在模式中指定多種可能的匹配，用"|"表示，
- 閉包操作，閉包操作可以把模式部分重復任意次數，用"*"表示，
- 括號，括號可以改變默認優先級的順序，
- 在編程語言中使用的正則運算式還有很多其它語法，但都是基于這幾種基本操作的，
非確定有限狀態自動機
如何根據正則運算式所描述的模式來匹配文本呢？子字串查找中使用的有序狀態自動機DFA會根據文本中的字符改變自身的狀態，但正則運算式匹配比子字串查找更復雜，因為或操作的存在，自動機無法僅根據一個字符就判斷出模式是否出現；再加上閉包的存在，自動機甚至無法知道需要檢查多少字符才會匹配失敗，為了克服這些困難，需要非確定有限狀態自動機NFA，
根據Kleene定理，任意正則運算式都存在一個與之對應的非確定有限狀態自動機，反之亦然，所以任意正則運算式都可以轉換為一個非確定有限狀態自動機，然后就可以模式NFA的運行軌跡來進行匹配了，
正則運算式((A*B|AC)D)所對應的NFA如下圖：
NFA具有以下特點：
- 長度為M的正則運算式中的每個字符在所對應的NFA中都有且只有一個對應的狀態，NFA的起始狀態為0并含有一個虛擬的接受狀態M；
- 字符表中的字符所對應的狀態都有一條從它指出的邊，這條邊指向模式中的下一個字符所對應的狀態（這種邊為黑色）；
- 元字符"(" ")" "|" "*"所對應的狀態至少含有一條指出的邊（這種邊為紅色），這些邊可能指向其它的任意狀態；
- 有些狀態有多條指出的邊，但一個狀態只能有一條指出的黑色邊，
這里約定將所有的模式都包含在括號中，一次NFA中的第一個狀態和最后一個狀態都對應的是括號，
在檢查文本與模式是否匹配時，NFA需要不斷讀取文本，直到NFA變為接受狀態，或到達文本末尾，由于或操作和閉包操作的存在，NFA從一個狀態轉換到了一個狀態的規則與DFA有所不同，在NFA中有兩種轉換方式：
- 匹配轉換，即文本中的某個字符與模式中的一個字符相對應，此時NFA可以掃過這個字符，并經過黑色的邊轉換到下一狀態；
- ε轉換，是指NFA經由紅色邊轉換到了一個狀態而不掃描文本中的任何字符，
比如在上圖的NFA中，由2->3, 1->6等都是ε轉換，ε轉換說明很多時候，NFA從一個狀態轉換到的下一個狀態是不確定的，比如從狀態3即可以到狀態4，也可以回到狀態2，正是由于這種不確定性的存在，NFA運行時，需要系統地嘗試過所有的可能性后，才能得知是否匹配成功，
模擬NFA的運行
使用NFA進行正則運算式匹配的程序與使用DFA進行子字串查找的整體程序大致相同，也是先根據給定的正則運算式構造NFA，然后模擬NFA在給定文本上的運行軌跡，
NFA的表示
首先考慮的是該如何表示NFA，正則運算式本身已經給出了所有的狀態名，如果正則運算式的長度為M，那么0到M之間的整數就是所有的狀態名，于是用char陣列re保存正則運算式的每個字符，對于匹配轉換，如果re[i]存在于字母表中，那么就存在一個從i到i+1的匹配轉換，
對于ε轉換，用有向圖表示，它們都是連接0到M之間各個頂點的有向邊，
構造與正則運算式相對應的NFA
在表示NFA的時候會使用一個char陣列，一個有向圖，另外還有一個堆疊來記錄所有左括號和或運算子的位置，
-
連接操作
連接操作的實作很容易，狀態的匹配之后和字母表中字符的對應關系就是連接操作的實作， -
括號
遇到正則運算式中的左括號時，將它的索引壓入堆疊中，在遇到右括號時，再從堆疊中彈出， -
閉包操作
閉包運算子'*'如果出現在單個字符之后，就在這個字符和'*'之間添加相互指向的兩條ε轉換；如果出現在右括號之后，就在對應的左括號和'*'之間添加相互指向的兩條ε轉換， -
或操作
遇到或操作也會添加兩條ε轉換，比如(A|B)，一條從左括號所對應的狀態指向或操作后面第一個字符B所對應的狀態，另一條從或運算子的狀態指向右括號對于的狀態，將"|"運算子的索引壓入堆疊中，這樣在到達右括號時從堆疊的頂部就可以拿到這個索引了，
public class Regular {
private char[] re;
private Digraph G;
private int M;
public Regular(String regexp) {
Stack<Integer> ops = new Stack<Integer>();
re = regexp.toCharArray();
M = re.length;
G = new Digraph(M + 1);
for (int i = 0; i < M; i++) {
int lp = i;
if (re[i] == '(' || re[i] == '|')
ops.push(i);
else if (re[i] == ')') {
int or = ops.pop();
if (re[or] == '|') {
lp = ops.pop();
G.addEdge(lp, or + 1);
G.addEdge(or, i);
} else
lp = or;
}
if (i < M - 1 && re[i + 1] == '*') {
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
if (re[i] == '(' || re[i] == '*' || re[i] == ')')
G.addEdge(i, i + 1);
}
}
}
NFA的模擬與可達性
為了模擬NFA的運行，會記錄NFA在檢查當前輸入字符時可能遇到的所有狀態的集合，這里關鍵的計算是有向圖的多點可達性問題，用深度優先搜索實作，
首先利用有向圖查找所有從狀態0通過ε轉換可達的所有狀態，記入一個集合中，這個集合用Bag資料結構來表示，對于集合中的每個狀態，檢查它是否可以與第一個輸入的字符相匹配，如果匹配，在用這些匹配的狀態集合繼續在有向圖中進行查找，就得到了NFA在匹配第一個字符后可達的所有狀態的集合，重復這個程序直到可達的狀態集合中含有接受狀態（匹配成功）或者文本結束（匹配失敗），
public boolean recognize(String txt) {
Bag<Integer> pc = new Bag<Integer>();
DirectedDFS dfs = new DirectedDFS(G, 0);
for (int v = 0; v < G.V(); v++) {
if (dfs.marked(v))
pc.add(v);
}
for (int i = 0; i < txt.length(); i++) {
Bag<Integer> match = new Bag<Integer>();
for (int v : pc)
if (v < M)
if (re[v] == txt.charAt(i) || re[v] == '.')
match.add(v + 1);
pc = new Bag<Integer>();
dfs = new DirectedDFS(G, match);
for (int v = 0; v < G.V(); v++)
if (dfs.marked(v))
pc.add(v);
}
for (int v : pc)
if (v == M)
return true;
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102321.html
標籤：其他