來源：https://jex.im/PRogramming/triple-regex.html

Regex Golf上有一道題名為 Triples，即要求用正則表達(dá)式匹配3的倍數(shù)，還有一道匹配7的倍數(shù)的練習(xí)題。這種問題如果人肉解決的話，相當(dāng)于做一道包含幾十個(gè)數(shù)的四則運(yùn)算題，不管你怎么想，反正我小時(shí)候遇到五個(gè)數(shù)以上的四則運(yùn)算題都是直接略過。小時(shí)候不好好學(xué)習(xí)，現(xiàn)在該怎么辦呢？——現(xiàn)在我會(huì)寫代碼了啊。 解決方案其實(shí)很簡單：寫程序構(gòu)造一個(gè)接受3的倍數(shù)的DFA，再將其轉(zhuǎn)換成正則式即可。

Finite Automaton

術(shù)語聽起來都好抽象，其實(shí)解決思路就像小學(xué)生做除法一樣簡單。比如我們?nèi)绾闻卸?code style="margin:0px 2px; padding:2px; font-family:"DejaVu Sans Mono","WenQuanYi Micro Hei Mono","Ubuntu Mono",Menlo,Monaco,"Courier New",Courier,monospace; white-space:nowrap; word-wrap:break-word; word-break:keep-all; background:rgb(234,234,250); color:black; border:1px solid rgb(170,187,255)">4641是3的倍數(shù)？ 從左往右一個(gè)數(shù)一個(gè)數(shù)地計(jì)算，最后余0即可：

46414    % 3 => 116   % 3 => 1 14  % 3 => 2  21 % 3 => 0
一次讀一個(gè)數(shù)字，然后輸出一個(gè)余數(shù)，如果最后余0則表示OK。影響我們判斷的有兩個(gè)因素：上次運(yùn)算結(jié)果的余數(shù)，當(dāng)前讀入的字符。自動(dòng)機(jī)就是這樣一種機(jī)器，開始處于一個(gè)狀態(tài)，每次讀入一個(gè)字符，然后輸出一個(gè)新狀態(tài)。所以上面的運(yùn)算可以用下面的自動(dòng)機(jī)執(zhí)行過程表示，起始狀態(tài)為0，余數(shù)即為輸出狀態(tài)：
  40 => 1
  61 => 1
  41 => 2
  12 => 0
用人話來講就是：上次余數(shù)為0時(shí)，遇到4則余1；上次余1時(shí)遇到6則還余1；……數(shù)字只有10個(gè)，所以我們可以窮舉，除3余數(shù)只有0、1、2三種可能，當(dāng)余數(shù)為任意一個(gè)時(shí)，下一次遇到的數(shù)字只有10種可能， 全部情況列舉成一張表：
上次余數(shù)（From State）
遇到數(shù)字（Input Char）
輸出余數(shù)（To State）
0
0、3、6、9
0
1、4、7
1
2、5、8
2
1
0、3、6、9
1
1、4、7
2
2、5、8
0
2
0、3、6、9
2
1、4、7
0
2、5、8
1
教科書都喜歡畫DFA流程圖，我也用GraphViz將就畫個(gè)（這么亂的圖真能幫助理解嗎）：
接下來其實(shí)就可以動(dòng)手寫程序自動(dòng)生成這張表了：
/**自動(dòng)構(gòu)造接受N的倍數(shù)的DFA@return { fromState => { Char => toState } }*/function buildDFA(N) {  var map={},i,j,to;  // i 為 From State  for (i=0;i<N;i++) //FromState不會(huì)超過N，因?yàn)橛鄶?shù)肯定小于N嘛    for (j=0;j<10;j++) { // j 為枚舉Input Digit Char      //當(dāng)上次余i這次碰到j(luò)時(shí)，除N的余數(shù)即為輸出狀態(tài)      to=(i*10+j) % N;      (map[i]=map[i]||{})[j]=to;    }  return map;}
這代碼也太簡單了，用javaScript寫的好處就是現(xiàn)在按下F12將代碼貼進(jìn)去運(yùn)行下就能看到結(jié)果了。可生成這張表有什么用呢？再寫個(gè)執(zhí)行DFA的函數(shù)就大功告成了：
/**運(yùn)行DFA@param {DFA}    a 就是buildDFA返回的表@param {String} s 輸入數(shù)字串@return 如果輸入匹配則返回true*/function runDFA(a,s) {  for (var i=0,from=0,l=s.length;i<l;i++) {    from=a[from][s[i]];//獲取到下一個(gè)狀態(tài)    if (from===undefined) return false;  }  return from===0;//最后余0則OK}//測(cè)試是否是3的倍數(shù)runDFA(buildDFA(3), ""+4614);
至此已經(jīng)做到了生成及執(zhí)行匹配任意整數(shù)倍數(shù)的DFA，注意是任意位數(shù)的N及其倍數(shù)哦。接下來的工作就是將自動(dòng)機(jī)轉(zhuǎn)換成正則表達(dá)式。有很多種算法，這里只介紹最易于理解的解方程法。
Arden's Lemma
這種方法就是將自動(dòng)機(jī)中的狀態(tài)變換看成方程組，然后用解方程的方式化簡自動(dòng)機(jī)，逐步消減狀態(tài)，最后合并成一個(gè)正則式。該方法基于Arden's Lemma：
L = UL ∪ V ? L = U ? V
看上去好抽象，其實(shí)只是Minify過了而已。其中的道理很簡單，先看下面的DFA如何轉(zhuǎn)換成正則式：
  a0 => 0
  b0 => 1
其中0、1為狀態(tài)，a、b表示Char，0為起始狀態(tài)，1為接受狀態(tài)。這個(gè)只包含兩條變換的自動(dòng)機(jī)對(duì)應(yīng)于正則式：a*b，這就是Arden's Lemma表達(dá)的意思。單這一條引理其實(shí)還不夠，我們還需要了解正則式其它幾個(gè)基礎(chǔ)性質(zhì)。我們把這正則式整體當(dāng)成一個(gè)自動(dòng)機(jī)的話，它就是0 => 1這樣一個(gè)變換。 正則式的串聯(lián)，比如a*bc*d，對(duì)應(yīng)于自動(dòng)機(jī)的串聯(lián)：
  a0 => 0
  b0 => 1
  c1 => 1
  d1 => 2
其中2為接受狀態(tài)。那么兩個(gè)正則式的串聯(lián)，則可以看成將整體串聯(lián)成 0 => 1 => 2得到0 => 2。 依此類推，正則式的并聯(lián)，如(a|b)c，對(duì)應(yīng)于自動(dòng)機(jī)的并聯(lián)：
  a0 => 1
  c1 => 2
  b0 => 1
好了，其實(shí)正則表達(dá)式與自動(dòng)機(jī)相互轉(zhuǎn)換的方法就這些。應(yīng)用到前面的Triple DFA，比如0 => 0的變換有四條，所以正則式為(0|3|6|9)*，當(dāng)然更簡單的寫法是[0369]*，前面buildDFA函數(shù)生成的表雖易于執(zhí)行，但卻不便于轉(zhuǎn)換到正則式，所以寫一個(gè)直接輸出如下格式的函數(shù)更方便：
{  "0":{    "0":"[0369]",    "1":"[147]",    "2":"[258]",  }}
改寫后的buildTable函數(shù)（其中reflect表后面再解釋）：
function buildTable(n) {  var map={},reflect={},i,j,to,path;  for (i=0;i<n;i++) {    path=map[i]={};    for (j=0;j<10;j++) {      to=(i*10+j) % n;      path[to]=path[to] || '';      path[to]+=j;      if (to>i)        (reflect[to]=reflect[to] || {})[i]=1;    }    for (to in path)      if (path[to].length>1)        path[to]='['+path[to]+']';  }  for (to in reflect)    reflect[to]=Object.keys(reflect[to]);  return {map:map,reflect:reflect};}
我們的目標(biāo)是轉(zhuǎn)換成的正則式只匹配除3余0的數(shù)，最終生成的正則式只能是一個(gè)0 => 0的變換，這樣才能保證成功匹配時(shí)的結(jié)束狀態(tài)一定是0。所以只需要把所有可能的0 => …… => 0不重復(fù)的變換路徑進(jìn)行并聯(lián)，就能得到最終的正則式。 比如將0 => 1 => 0和0 => 0并聯(lián)得到正則式：([0369]|[147][258])*，依此類推。應(yīng)用前面的Arden's Lemma及其它幾條方法，將所有的變換都化簡成一條0 => 0變換，這個(gè)過程就像在解一個(gè)方程，將不可接受狀態(tài)當(dāng)成未知量化解成用0這個(gè)可接受狀態(tài)表示。例如對(duì)于TripleDFA，約去狀態(tài)2的步驟如下所示：
Origin
應(yīng)用Arden's Lemma
{  "2": {    "0": "[147]",    "1": "[258]",    "2": "[0369]"  }}
{  "2": {    "0": "[0369]*[147]",    "1": "[0369]*[258]"  }}
然后再將狀態(tài)1輸出中的狀態(tài)2替換掉，其它依此類推：
Origin
{ "1": {    "0": "[258]",    "1": "[0369]",    "2": "[147]"  }}
1 => 2 => X串聯(lián)
{  "1": {    "0": "[258]",    "1": "[0369]",    "0": "[147][0369]*[147]",    "1": "[147][0369]*[258]"  }}
1 => X并聯(lián)
{  "1": {    "0": "[258]|[147][0369]*[147]",    "1": "[0369]|[147][0369]*[258]"  }}
前面buildTable中的reflect表就是用于反查哪些狀態(tài)可以到達(dá)當(dāng)前要約去的狀態(tài)，以便將其替換掉。
在化簡過程中，無非對(duì)正則式進(jìn)行串聯(lián)、并聯(lián)、重復(fù)這三種操作，相應(yīng)的處理函數(shù)如下：
// seq(["[147]","[258]"]) => "[147][258]"function seq(a) {  return {    type:'seq',    toString:function () {      var re=a.join("");      if (this.repeat)        re=a.length>1?'('+re+')*':re+'*';      return re;    }  };}// choice(["[147]","[258]"]) => "[147]|[258]"function choice(a) {  var items=[];  //這一步其實(shí)只是為了使生成的正則式更短一些  //按并聯(lián)的結(jié)合性，"a|(b|c)" 等同于 "a|b|c"  a.forEach(function (re) {    if (re.type==='choice')      items=items.concat(re.items);    else if (re)      items.push(re);  });  return {    type:'choice', items:items,    toString:function () {      var re=items.join("|");      if (items.length>1 || this.repeat) re='('+re+')';      if (this.repeat) re+='*';      return re;    }  };}// 將一個(gè)正則式標(biāo)志為重復(fù)function repeat(re) {  if (typeof re==='string') return re+'*';  re.repeat=true;  return re;}
除去拼接正則式的代碼，最終的函數(shù)也不算長：
function buildRegex(n) {  var table=buildTable(n),i=n,j,k,to,path;  var map=table.map,reflect=table.reflect;  while (--i) {    var trans=map[i],t={},        prefix=trans[i]?repeat(trans[i]):'';    for (to in trans)      if (to<i) t[to]=trans[to];    trans=t;    if (prefix) for (to in trans)      trans[to]=seq([prefix,trans[to]]);    var entrances=reflect[i];    for (j=entrances.length;j--;) {      var from=entrances[j];      path=map[from];      prefix=path[i];      for (to in trans)        path[to]=choice([path[to] || '',seq([prefix,trans[to]])]);    }  }  return '^'+repeat(map[0][0])+'$';}
執(zhí)行buildRegex(3)生成的正則表達(dá)式如下，Regex Golf評(píng)分 523 Points：
^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$
這個(gè)函數(shù)生成出的匹配7的倍數(shù)的正則式有近16K，雖然說它能生成匹配任意位整數(shù)倍數(shù)的正則式，但這并不現(xiàn)實(shí)，因?yàn)樗傻恼齽t式體積呈指數(shù)級(jí)增漲，生成20以上的正則式內(nèi)存就不夠用了。而這么長的正則式讓JS的正則引擎去解析的話，大約15以上就會(huì)報(bào)錯(cuò)。如果去執(zhí)行匹配測(cè)試的話，大于13就有可能返回 False，這是因?yàn)閳?zhí)行時(shí)間過長，正則引擎就會(huì)放棄執(zhí)行。優(yōu)化當(dāng)然還是可以做的，比如生成的正則式輸出時(shí)使用非捕獲分組如(:?[147])，執(zhí)行速度則可以提升好幾倍。
我知道很多人會(huì)說用正則式匹配3的倍數(shù)效率太低了，有什么必要呢？我當(dāng)然知道沒人真的會(huì)這么用正則式，但這道理還是需要講明白的。姑且不談使用atoi的方法即使在64位機(jī)上也只能處理長度不超過二十位的數(shù)字，試問這個(gè)正則表達(dá)式真的很慢嗎？這可不一定。正則引擎其實(shí)還是將正則式轉(zhuǎn)換成DFA或NFA執(zhí)行的，如果是編譯到DFA，雖然編譯會(huì)花費(fèi)些時(shí)間和內(nèi)存，但執(zhí)行速度只慢在額外的內(nèi)存讀取，DFA復(fù)雜度和atoi函數(shù)一樣都是Θ(n)，即使慢也只是常數(shù)倍。如果直接執(zhí)行原始DFA，理論上可以和atoi函數(shù)一樣快，這道理是明擺著的。 你不信的話，用下面的C++程序測(cè)試看，即使re2也只不過慢了5倍而已：
#include <stdio.h>#include <time.h>#include <stdlib.h>#include <re2/re2.h>#define LOOP_TIMES 10000000int main() {  int dfa[3][10]={    0,1,2,0,1,2,0,1,2,0,    1,2,0,1,2,0,1,2,0,1,    2,0,1,2,0,1,2,0,1,2};  clock_t start;int i;  const char* num="2147483646";  i=LOOP_TIMES;  start=clock();  while (i--) {    const char* str=num;    int from=0;    while( *str ) {      from=dfa[from][(*str++ - '0')];    }    int isTriple=from==0;  }  printf(" DFA:%d/n",clock()-start);  i=LOOP_TIMES;  start=clock();  while (i--) {    unsigned int val = atoi(num);    int isTriple = (val % 3)==0;  }  printf("atoi:%d/n",clock()-start);  RE2::Options opt(RE2::Latin1);  opt.set_never_capture(true);  RE2 re("(?:[0369]|[258][0369]*[147]|"  "(?:[147]|[258][0369]*[258])"  "(?:[0369]|[147][0369]*[258])*"  "(?:[258]|[147][0369]*[147]))*",opt);  i=LOOP_TIMES;  start=clock();  while (i--) {    int isTriple =RE2::FullMatch(num, re);  }  printf(" re2:%d/n",clock()-start);}
如果你仍然覺得正則表達(dá)式肯定很慢的話，那看下面的Javascript測(cè)試程序：
var LOOP_TIMES=10000000;var re=/^(?:[0369]|[258][0369]*[147]|(?:[147]|[258][0369]*[258])(?:[0369]|[147][0369]*[258])*(?:[258]|[147][0369]*[147]))*$/;var s="31457283145728",    i,isTriple,start;start=+new Date;i=LOOP_TIMES;while (i--) isTriple=re.test(s);console.log("  RegExp:",(+new Date)-start);start=+new Date;i=LOOP_TIMES;while (i--) isTriple=parseInt(s)%3 === 0;console.log("parseInt:",(+new Date)-start);
運(yùn)行結(jié)果顯示parseInt方式更慢！為什么？呵呵，因?yàn)镴S中 Number 是雙精度64位浮點(diǎn)數(shù)，如果將上面C++程序中atoi改成atof、使用fmod取余的話，運(yùn)行結(jié)果顯示取余比正則式只快了不到一倍！
好了，現(xiàn)在至少?zèng)]人再拿這正則表達(dá)式效率低說事了吧。