正则表达式匹配N的倍数

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

Regex Golf上有一道题名为 Triples，即要求用正则表达式匹配3的倍数，还有一道匹配7的倍数的练习题。这种问题如果人肉解决的话，相当于做一道包含几十个数的四则运算题，不管你怎么想，反正我小时候遇到五个数以上的四则运算题都是直接略过。小时候不好好学习，现在该怎么办呢？——现在我会写代码了啊。 解决方案其实很简单：写程序构造一个接受3的倍数的DFA，再将其转换成正则式即可。

Finite Automaton

术语听起来都好抽象，其实解决思路就像小学生做除法一样简单。比如我们如何判定4641是3的倍数？ 从左往右一个数一个数地计算，最后余0即可：

46414    % 3 => 116   % 3 => 1 14  % 3 => 2  21 % 3 => 0
一次读一个数字，然后输出一个余数，如果最后余0则表示OK。影响我们判断的有两个因素：上次运算结果的余数，当前读入的字符。自动机就是这样一种机器，开始处于一个状态，每次读入一个字符，然后输出一个新状态。所以上面的运算可以用下面的自动机执行过程表示，起始状态为0，余数即为输出状态：
  40 => 1
  61 => 1
  41 => 2
  12 => 0
用人话来讲就是：上次余数为0时，遇到4则余1；上次余1时遇到6则还余1；……数字只有10个，所以我们可以穷举，除3余数只有0、1、2三种可能，当余数为任意一个时，下一次遇到的数字只有10种可能， 全部情况列举成一张表：
上次余数（From State）
遇到数字（Input Char）
输出余数（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将就画个（这么乱的图真能帮助理解吗）：
接下来其实就可以动手写程序自动生成这张表了：
/**自动构造接受N的倍数的DFA@return { fromState => { Char => toState } }*/function buildDFA(N) {  var map={},i,j,to;  // i 为 From State  for (i=0;i<N;i++) //FromState不会超过N，因为余数肯定小于N嘛    for (j=0;j<10;j++) { // j 为枚举Input Digit Char      //当上次余i这次碰到j时，除N的余数即为输出状态      to=(i*10+j) % N;      (map[i]=map[i]||{})[j]=to;    }  return map;}
这代码也太简单了，用javaScript写的好处就是现在按下F12将代码贴进去运行下就能看到结果了。可生成这张表有什么用呢？再写个执行DFA的函数就大功告成了：
/**运行DFA@param {DFA}    a 就是buildDFA返回的表@param {String} s 输入数字串@return 如果输入匹配则返回true*/function runDFA(a,s) {  for (var i=0,from=0,l=s.length;i<l;i++) {    from=a[from][s[i]];//获取到下一个状态    if (from===undefined) return false;  }  return from===0;//最后余0则OK}//测试是否是3的倍数runDFA(buildDFA(3), ""+4614);
至此已经做到了生成及执行匹配任意整数倍数的DFA，注意是任意位数的N及其倍数哦。接下来的工作就是将自动机转换成正则表达式。有很多种算法，这里只介绍最易于理解的解方程法。
Arden's Lemma
这种方法就是将自动机中的状态变换看成方程组，然后用解方程的方式化简自动机，逐步消减状态，最后合并成一个正则式。该方法基于Arden's Lemma：
L = UL ∪ V ⟺ L = U ∗ V
看上去好抽象，其实只是Minify过了而已。其中的道理很简单，先看下面的DFA如何转换成正则式：
  a0 => 0
  b0 => 1
其中0、1为状态，a、b表示Char，0为起始状态，1为接受状态。这个只包含两条变换的自动机对应于正则式：a*b，这就是Arden's Lemma表达的意思。单这一条引理其实还不够，我们还需要了解正则式其它几个基础性质。我们把这正则式整体当成一个自动机的话，它就是0 => 1这样一个变换。 正则式的串联，比如a*bc*d，对应于自动机的串联：
  a0 => 0
  b0 => 1
  c1 => 1
  d1 => 2
其中2为接受状态。那么两个正则式的串联，则可以看成将整体串联成 0 => 1 => 2得到0 => 2。 依此类推，正则式的并联，如(a|b)c，对应于自动机的并联：
  a0 => 1
  c1 => 2
  b0 => 1
好了，其实正则表达式与自动机相互转换的方法就这些。应用到前面的Triple DFA，比如0 => 0的变换有四条，所以正则式为(0|3|6|9)*，当然更简单的写法是[0369]*，前面buildDFA函数生成的表虽易于执行，但却不便于转换到正则式，所以写一个直接输出如下格式的函数更方便：
{  "0":{    "0":"[0369]",    "1":"[147]",    "2":"[258]",  }}
改写后的buildTable函数（其中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};}
我们的目标是转换成的正则式只匹配除3余0的数，最终生成的正则式只能是一个0 => 0的变换，这样才能保证成功匹配时的结束状态一定是0。所以只需要把所有可能的0 => …… => 0不重复的变换路径进行并联，就能得到最终的正则式。 比如将0 => 1 => 0和0 => 0并联得到正则式：([0369]|[147][258])*，依此类推。应用前面的Arden's Lemma及其它几条方法，将所有的变换都化简成一条0 => 0变换，这个过程就像在解一个方程，将不可接受状态当成未知量化解成用0这个可接受状态表示。例如对于TripleDFA，约去状态2的步骤如下所示：
Origin
应用Arden's Lemma
{  "2": {    "0": "[147]",    "1": "[258]",    "2": "[0369]"  }}
{  "2": {    "0": "[0369]*[147]",    "1": "[0369]*[258]"  }}
然后再将状态1输出中的状态2替换掉，其它依此类推：
Origin
{ "1": {    "0": "[258]",    "1": "[0369]",    "2": "[147]"  }}
1 => 2 => X串联
{  "1": {    "0": "[258]",    "1": "[0369]",    "0": "[147][0369]*[147]",    "1": "[147][0369]*[258]"  }}
1 => X并联
{  "1": {    "0": "[258]|[147][0369]*[147]",    "1": "[0369]|[147][0369]*[258]"  }}
前面buildTable中的reflect表就是用于反查哪些状态可以到达当前要约去的状态，以便将其替换掉。
在化简过程中，无非对正则式进行串联、并联、重复这三种操作，相应的处理函数如下：
// 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=[];  //这一步其实只是为了使生成的正则式更短一些  //按并联的结合性，"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;    }  };}// 将一个正则式标志为重复function repeat(re) {  if (typeof re==='string') return re+'*';  re.repeat=true;  return re;}
除去拼接正则式的代码，最终的函数也不算长：
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])+'$';}
执行buildRegex(3)生成的正则表达式如下，Regex Golf评分 523 Points：
^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$
这个函数生成出的匹配7的倍数的正则式有近16K，虽然说它能生成匹配任意位整数倍数的正则式，但这并不现实，因为它生成的正则式体积呈指数级增涨，生成20以上的正则式内存就不够用了。而这么长的正则式让JS的正则引擎去解析的话，大约15以上就会报错。如果去执行匹配测试的话，大于13就有可能返回 False，这是因为执行时间过长，正则引擎就会放弃执行。优化当然还是可以做的，比如生成的正则式输出时使用非捕获分组如(:?[147])，执行速度则可以提升好几倍。
我知道很多人会说用正则式匹配3的倍数效率太低了，有什么必要呢？我当然知道没人真的会这么用正则式，但这道理还是需要讲明白的。姑且不谈使用atoi的方法即使在64位机上也只能处理长度不超过二十位的数字，试问这个正则表达式真的很慢吗？这可不一定。正则引擎其实还是将正则式转换成DFA或NFA执行的，如果是编译到DFA，虽然编译会花费些时间和内存，但执行速度只慢在额外的内存读取，DFA复杂度和atoi函数一样都是Θ(n)，即使慢也只是常数倍。如果直接执行原始DFA，理论上可以和atoi函数一样快，这道理是明摆着的。 你不信的话，用下面的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);}
如果你仍然觉得正则表达式肯定很慢的话，那看下面的Javascript测试程序：
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);
运行结果显示parseInt方式更慢！为什么？呵呵，因为JS中 Number 是双精度64位浮点数，如果将上面C++程序中atoi改成atof、使用fmod取余的话，运行结果显示取余比正则式只快了不到一倍！
好了，现在至少没人再拿这正则表达式效率低说事了吧。