正则表达式匹配N的倍数

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

Finite Automaton

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

4641
4    % 3 => 1
16   % 3 => 1
 14  % 3 => 2
  21 % 3 => 0

一次读一个数字,然后输出一个余数,如果最后余0则表示OK。影响我们判断的有两个因素:上次运算结果的余数,当前读入的字符。自动机就是这样一种机器,开始处于一个状态,每次读入一个字符,然后输出一个新状态。所以上面的运算可以用下面的自动机执行过程表示,起始状态为0,余数即为输出状态:

  4
0 => 1
  6
1 => 1
  4
1 => 2
  1
2 => 0

用人话来讲就是:上次余数为0时,遇到4则余1;上次余1时遇到6则还余1;……
数字只有10个,所以我们可以穷举,除3余数只有0、1、2三种可能,当余数为任意一个时,下一次遇到的数字只有10种可能, 全部情况列举成一张表:

上次余数(From State) 遇到数字(Input Char) 输出余数(To State)
00、3、6、90
1、4、71
2、5、82
10、3、6、91
1、4、72
2、5、80
20、3、6、92
1、4、70
2、5、81

教科书都喜欢画DFA流程图,我也用GraphViz将就画个(这么乱的图真能帮助理解吗):

Triple DFA Diagram

接下来其实就可以动手写程序自动生成这张表了:

/**
自动构造接受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如何转换成正则式:

  a
0 => 0
  b
0 => 1

其中0、1为状态,a、b表示Char,0为起始状态,1为接受状态。这个只包含两条变换的自动机对应于正则式:a*b,这就是Arden's Lemma表达的意思。单这一条引理其实还不够,我们还需要了解正则式其它几个基础性质。我们把这正则式整体当成一个自动机的话,它就是0 => 1这样一个变换。 正则式的串联,比如a*bc*d,对应于自动机的串联:

  a
0 => 0
  b
0 => 1
  c
1 => 1
  d
1 => 2

其中2为接受状态。那么两个正则式的串联,则可以看成将整体串联成 0 => 1 => 2得到0 => 2。 依此类推,正则式的并联,如(a|b)c,对应于自动机的并联:

  a
0 => 1
  c
1 => 2
  b
0 => 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 => 00 => 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 10000000
int 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取余的话,运行结果显示取余比正则式只快了不到一倍!

好了,现在至少没人再拿这正则表达式效率低说事了吧。