天天看點
傳回

用正規表達式比對3的任意倍數

正規表達式能比對3的任意倍數?(注意是任意倍數) ，我曾經也很震驚，但确實可以。我5年多前練習正規表達式，在 Regex Golf 這個正規表達式測試網站上發現了這個題，當時完全沒有任何頭緒，于是我在知乎提問 正規表達式如何比對 3 的倍數 ，但是得到了好多知乎大佬的關注，也上了當天的熱榜。 排名第一的答主已經給出了答案和思路，但這麼多年來我一直都沒看懂，最近學習編譯原理，看到正規表達式和DFA，于是仔細研究了一下這個問題，并将問題擴充至比對N的倍數，最後給出通用解法和代碼。 

^(([0369]|[147][0369]*[258])|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$

先給出答案，上面這個正規表達式确實能夠比對任意3的着倍數，再次強調是任意，它确實能比對任意長度的3的倍數(嚴謹一點應該是正整數倍，這裡不再細究)。 這個正規表達式是這麼來的？實際上它是由下面這個DFA(确定性有窮狀态機)生成的。

用正規表達式比對3的任意倍數

構造DFA

那這個DFA又是如何來的？首先我們來解釋下何為DFA(Deterministic finite automata)，首先DFA是一種狀态機(automata)，狀态機是用來描述狀态在不同條件下互相轉換的關系，DFA就是在指定條件下，這個狀态轉換路徑是确定且唯一的，這也是它和NFA(Nondeterministic finite automata)的差別。 在正規表達式中，DFA就是在給定某個字元的情況狀态如何轉移，一般情況下有個初始狀态和終止狀态，如上圖所示狀态A就是終止狀态，一般用雙層環表示，上圖并為辨別初始狀态，其實這裡初始狀态也是A。在正規表達式對應的DFA中如果目前狀态是終止狀态，說明正規表達式比對成功。

如果我們要生成一個比對N的倍數的DFA，我們的思路是這樣的，如果一個數X是N的倍數，那麼一定是

X % N == 0

，這也是我們用來判斷X是不是N的倍數方法，我們是把X看成是一個數字一個整體。其實我們這裡也是通過取mod是否為零來做的，但我們需要對取mod的過程稍微改造下，舉例如下：

0128%3 == (((((0 % 3)*10 + 1) % 3)*10 + 2)*10 + 8) % 3

左右兩邊的表達式計算結果是等價的，隻是我們右邊是把每位拆開來單獨計算。仔細看看右邊的表達式，我們從高位到低位挨個計算mod 3的結果，然後把計算結果乘以10再加到下一位上繼續計算，直到後面沒有其他數字為止。這種從前到後按位去mod的方式就和正規表達式從前到後按字元去比對的方式一緻了，我們可以按目前狀态和新到的數字去計算下一個狀态是啥了。

了解了這點，我們就可以開始構造我們的DFA了，我們可以以mod N之後餘幾做作為狀态，比如N為3時，總共有0 1 2 三種狀态。每增加一個數字，一個狀态都可以轉移到了一個狀态，例如：狀态$S_k$新增數字m的情況下可以轉移到狀态$S_{(k*10 + m) \% 3}$，接下來我們隻需要建立每個狀态在每種不同輸入下狀态轉移的關系就行了，僞代碼如下。

for i = 0 to N:
    for j = 0 to N:
        if i*10 + k) % n == :
            建立一條狀态Si到Sj的邊

将上面建立好的關系繪制成圖就得到了如下DFA。

用正規表達式比對3的任意倍數

DFA推導出正規表達式

對于上文中比對3的倍數的DFA，因為狀态還算比較少，我們可以人肉推導出來。從上圖我們可以看出ABC三個狀态是互相依存的關系，我們可以把這種關系列成三個方程式。

A = A[0369] | B[258] | C[147] 
B = A[147] | B[0369] | C[258]
C = A[258] | B[147] | C[0369]

根據

Arden定理

若$X = XA | B$則$X = BA*$ ，我們可以再做如下轉化。

A = (| B[258] | C[147])[0369]* (1)
B = (A[147] | C[258])[0369]* (2)
C = (A[258] | B[147])[0369]* (3)

為了讓你了解如何計算出A這裡我做一個不恰當但很合理的轉化，你可以把連接配接和 | 分别看出四則運算裡的乘和加，把ABC分别看成三個未知數，然後我們就得到了一個三元一次方程組，而我們隻需要求解出A，求解過程如下：

把(3)帶入(1)(2)分别得到：

A = (| B[258] | (A[258] | B[147])[0369]*[147])[0369]* (4)
B = (A[147] | (A[258] | B[147])[0369]*[258])[0369]* (5)

用配置設定律展開 (5) 中的豎線得到

B = A[147][0369]* | A[258][0369]*[258][0369]* | B[147][0369]*[258][0369]*

這裡再用一次

得到

B = A[147][0369]*([147][0369]*[258][0369]*)* 
  | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)* (6)

把(6)帶入到(4)中，并繼續用

消去右側的A

A = (| B[258] | (A[258] | B[147])[0369]*[147])[0369]*
  =   [0369]* 
    | B[258][0369]*
    | A[258][0369]*[147][0369]*
    | B[147][0369]*[147][0369]* 
  =   [0369]* 
    | A[147][0369]*([147][0369]*[258][0369]*)*[258][0369]*
    | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]*
    | A[258][0369]*[147][0369]*
    | A[147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* 
    | A[258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* 
  = [0369]* (
                  [147][0369]*([147][0369]*[258][0369]*)*[258][0369]*
    | [258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[258][0369]*
    |             [147][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]* 
    | [258][0369]*[258][0369]*([147][0369]*[258][0369]*)*[147][0369]*[147][0369]*
    | [258][0369]*[147][0369]* )*
  = [0369]* (
      (
        [147][0369]*
      | [258][0369]*[258][0369]*
      ) ([147][0369]*[258][0369]*)* (
        [258][0369]*
 
      | [147][0369]*[147][0369]*
      )
    | [258][0369]*[147][0369]* )*

加上^ 和 $ 就得到了能夠比對3的倍數的正規表達式，推導過程很艱辛，有沒有什麼方法可以自動把DFA轉為正規表達式？

你可能注意到這個正規表達式和我在文章開頭給出的不一樣，但這個正規表達式也是正确的。這個正規表達式我自己實在是沒推導出來，是以推導過程引用了

知乎的内容

，但我找到了能夠将任意DFA轉成正規表達式的方法，文章開頭的正規表達式就是我用代碼自動生成的，接下來就教你DFA如何自動轉正規表達式。

任意DFA轉正規表達式的方法

DFA轉Regex的核心思想也很簡單，逐個删除中間狀态(非初始狀态和終止狀态)，删除過程中把經過這個狀态的路徑合并到其他路徑上，舉例如下：

用正規表達式比對3的任意倍數

我們删除q時，需要對經過狀态q的路徑做合并。（__·__ 表示連接配接符，star()表示

Kleene star

，其實就是正規表達式中的星号，表示出現0次或任意多次）

L[p->r] = L[p-q] · star[L[q->q]] · L[q-r]
L[r->p] = L[r-q] · star[L[q->q]] · L[q-p]

經裝換後得到了如下DFA。

用正規表達式比對3的任意倍數

如果p為初始狀态，r為終止狀态，我們可以直接把這個DFA通過如下公式轉為正規表達式。

star(L[s,s]) · L[s,f] · star(L[f,s] · star(L[s,s]) · L[s,f] + L[f,f])

為了加深了解，我們再舉個例子。

用正規表達式比對3的任意倍數

在删除完狀态2之後，1->3的路徑需要并上經過狀态2的路徑，也就是1->2->3。 同理 3->1的路徑需要并上3->2->1，最後DFA變成如下。

用正規表達式比對3的任意倍數

用同樣的方式删除完狀态3之後，我們隻剩下狀态1，因為狀态1即是初始狀态，又是終止狀态，是以我們要的正規表達式就是0->0的路徑。在隻剩下初始狀态$State_s$和終止狀态$State_e$的DFA，$State_s$->$State_e$的路徑就可以代表整個原始DFA，這個路徑也可以當成正規表達式直接使用。

用正規表達式比對3的任意倍數

最後得到了

(??+(?+??)(??)*(?+??))*

，把

+

替換為

|

，并把ab分别替換成狀态轉移條件就變成一個可用的正規表達式。

在給出完整代碼前，我先給出DFA轉Regex的僞代碼：

# 首先需要把兩個狀态間的多條邊合并成1條
for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a 
remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]

# 逐個删除中間狀态  
for i = 1 to n:  
  if not(final(i)) and not(initial(i)):  
    remove(i)

我用Java實作了N任意倍數的DFA生成，并實作了DFA轉Regex的功能，完整代碼如下。調用getDFA(3)傳回的就是繪制成圖就是上文中出現多次的DFA，這裡我用了HashMap存儲各個狀态之間的關系。

代碼 

public class DFA2regex {
    private final static int INITSTATE = 0;
    private final static int FINALSTATE = 0;
    private final static Set<Integer> set = new HashSet<>();
 
    // 生成DFA時我直接将多條邊合并成了一條 
    private static Map<String, String> getDFA(int n) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 10; k++) {
                    String key = key(i, j);
                    if (!map.containsKey(key)) {
                        map.put(key, new LinkedList<>());
                    }
                    if ((i*10 + k) % n == j) {
                        List<String> list = map.get(key);
                        list.add(String.valueOf(k));
                    }
                }
            }
        }
        Map<String, String> finalRes = new HashMap<>();
        for (HashMap.Entry<String, List<String>> entry : map.entrySet()) {
            String key = entry.getKey();
            String val =  entry.getValue().stream().reduce("", String::concat);
            if (val.length() > 1) {
                val = "[" + val + "]";
            }
            finalRes.put(key, val);
        }
        return finalRes;
    }
   
    private static void remove(int k, int n, Map<String, String> dfa) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (set.contains(i) || set.contains(j)) {
                    continue;
                }
                dfa.put(key(i, j), concat(dfa.get(key(i, j)), dfa.get(key(i, k)), star(dfa.get(key(k, k))), dfa.get(key(k, j))));
            }
        }
    }

    private static String concat(String s1, String s2, String s3, String s4) {
        String str1 = s1;
        String str2 = s2 + s3 + s4;
        if (str1.length() > 0 && str2.length() > 0) {
            str1 += "|";
        }
        String res = str1 + str2;
        if (res.contains("|") || res.contains("*")) {
            return "(" + res + ")";
        }
        return res;
    }


    private static String star(String s) {
        if (s.equals("") || s.equals("|")) {
            return "";
        }
        return s + "*";
    }

    private static String key(int s, int e) {
        return s + "_" + e;
    }

    public static void main(String[] args) {
        int n = 4;
        Map<String, String> dfa = getDFA(n);
        for (int i = 0; i < n; i++) {
            if (INITSTATE != i && FINALSTATE != i) {
                set.add(i);
                remove(i, n, dfa);
            }
        }
        System.out.println("^" + star(dfa.get("0_0")) + "$");
    }
}

寫上面代碼的過程中我踩到幾個坑，正規表達式各運算符是有優先級的，是以需要再狀态消除過程中對中間表達式左右添加 () ，為了讓生成的正規表達式簡潔，我在concat()中做了一些特殊的處理，讓最終結果沒有多餘的_小括号_ 和 | 符号。

彩蛋

這裡分别列一下能比對1-6的任意倍數的正規表達式。為什麼不列更多，因為後面生成的正規表達式已經越來越長了，列不下了，7的就已經幾千個字元了，有興趣大家可以自己跑下上面代碼生成下。事實上因為正規表達式越來越長，數字越大越耗資源，我自己電腦跑16就跑不出結果了。

1 

^[0123456789]*$

2 

^([02468]|[13579][13579]*[02468])*$

3 

^(([0369]|[147][0369]*[258])|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$

4 

^((([048]|[159][37]*[26])|([26]|[159][37]*[048])([26]|[159][37]*[048])*([048]|[159][37]*[26]))|(([37]|[159][37]*[159])|([26]|[159][37]*[048])([26]|[159][37]*[048])*([37]|[159][37]*[159]))(([159]|[37][37]*[159])|([048]|[37][37]*[048])([26]|[159][37]*[048])*([37]|[159][37]*[159]))*(([26]|[37][37]*[26])|([048]|[37][37]*[048])([26]|[159][37]*[048])*([048]|[159][37]*[26])))*$

5 

^(((([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05])))|((([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49])))((([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([49]|[16][16]*[49])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([49]|[16][16]*[49])))*((([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))|(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))(([38]|[16][16]*[38])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([38]|[16][16]*[38]))*(([05]|[16][16]*[05])|([27]|[16][16]*[27])([27]|[16][16]*[27])*([05]|[16][16]*[05]))))*$

6 

^((((([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))))|((((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))(((([39]|5[39]*[17])|([06]|5[39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))*((((4|5[39]*[28])|([06]|5[39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))))*$

參考資料

  1. 知乎：正規表達式如何比對 3 的倍數？
  2. How to convert finite automata to regular expressions?
存儲 java 網絡安全 perl 安全存儲java java資料存儲 java網絡 java求職面試 java經典面試求職面試
上一篇: 一文告訴你CPU分支預測對性能影響有多大
下一篇: 布隆過濾器(BloomFilter)原理 實作和性能測試

繼續閱讀