doclist 阅读(36) 评论(0)

简单的探索下正则表达式的相关知识,首先先了解下正则表达式的引擎和匹配过程区别,再试着掌握如何在场景中编写正则表达式,再然后探索下根据上文已知的原理和编写过程怎么去优化正则表达式,最后给出一些js里正则相关的小扩展。

基础及原理简单介绍

了解一下正则表达式的正则引擎(正则表达式使用的理论模型是有穷自动机,具体实现称为正则引擎)。

正则引擎分有DFA(确定型有穷自动机)的和NFA(非确定型有穷自动机)的实现,根据编译相关知识的描述,两者是可以等价转换的。NFA又分传统型和POSIX标准,下面是三者一个简单的对照表:

-/-         回溯     忽略优先量词     捕获型括号       应用算法
DFA          ❌        ❌             ❌          文本主导
传统型NFA     ✔️        ✔️             ✔️         表达式主导   
POSIX NFA    ✔️        ❌             ✔️         表达式主导

回溯指的是:一个类似枚举的搜索尝试过程,在搜索尝试过程中寻找问题的解,当在分歧点选择一条路径,记住另一/多条路径供之后使用,在选择路径后的探索过程中发现不满足求解条件时,就返回到分歧点,尝试其他路径(回溯遵循后进先出原则/LIFO-last in first out)。

忽略优先量词指的是:支持尽可能少的匹配结果。

捕获型括号指的是:匹配并捕获结果,获取组号。

文本主导指的是:匹配搜索过程中的每个字符都对匹配过程进行控制(这样的结果就是:虽然我不能回溯,但我速度快呀 - DFA的傲娇...)。

表达式主导指的是:表达式中的控制权在不同的表达式元素之间转换,然后与文本进行匹配。

三者还有一些其他的差异,如编译阶段的处理及匹配最左最长原则等,由于文章里以js的正则为准,就不做更多区别的介绍,详情可参考书籍《精通正则表达式》,不过值得注意的是本书中的内容不一定完全适合各个语言或平台中的正则表达式...

正则匹配的过程规则总结:

1. 优先选择最左端的匹配结果(匹配是从左到右开始的)

  匹配先从需要查找的字符串的第一个字符尝试匹配;

  如果匹配到结果,则返回结果;

  如果匹配不到结果,则就需要从字符串的第二个字符位置开始重新匹配;

  以此类推,直到尝试过所有的字符串位置作为匹配起始点进行匹配后,返回匹配失败结果。

  如 forever 中匹配是否存在 ever:

  第一轮:从f开始匹配,fore不匹配ever;

  第二轮:从o开始匹配,orev不匹配ever;

  第三轮:从r开始匹配,reve不匹配ever;

  第四轮:从e开始匹配,ever匹配ever,获得ever匹配起始点(此处为3)的索引和匹配结果。

2. 标准量词总是匹配优先的(*、+、?、{m,n})

  匹配优先:尽可能多的匹配;忽略优先:尽可能少的匹配。

  标准量词总是匹配优先的,如:foo 针对表达式取 fo|foo(下面匹配基于JavaScript)

  匹配优先结果:foo,/f[o]{1,2}/

  忽略优先结果:fo,/f[o]{1,2}?/,加?后表示忽略优先量词

更多原理和匹配过程详解可以参考园友@BattleHeart的文章"浅析正则表达式—(原理篇)"

在需求场景中构建正则表达式

要构建正则表达式,得先了解一些正则表达式的一些普通字符和元字符。这些可以参照"百度百科-正则表达式_符号",该表对于正则使用生疏的同学可以作字典参考,这里对于这些字符就不多做赘述。

以几个例子来说明下在有正则需求的场景中该如何来写表达式。

例子一:查询句子中某些单词出现的次数。

首先分析情况得出:先给出个大致形状,/pattern/g ,经测试发现:

"the weather's often cold in the north and windy in the east".match(/the/g).length
// output 4

输出4,明显不对,这时候还需要考虑单词的边界情况,需要在pattern两边加上限制\b,并且注意不需要匹配单词边界,于是得出:

/\bthe\b/g

再测一下:

"the weather's often cold in the north and windy in the east".match(/\bthe\b/g).length
// output 3

正确。

例子二:比如需要给数字加 ",(逗号)" 形成货币格式的场景,如1234567,变成1,234,567。

首先分析情况得出:逗号应该加在"左边存在数字,右边的数字个数是3的倍数"。

这里用到正则的"非获取匹配,反向肯定预查 : (?<=pattern)" 和 "非获取匹配,正向肯定预查 : (?=pattern)",非获取匹配指的是匹配但不获取匹配值,正/反向肯定预查指的是正/反向匹配时在任何匹配条件的字符串开始处匹配查找字符串。

先反向肯定预查"左边存在数字"的组合,给出(?<=\d);再正向肯定预查"右边数字个数是3的倍数的组合",给出(?=(\d{3})+$);结合两者,加上全局的匹配 g,得出:

/(?<=\d)(?=(\d{3})+$)/g

测试一下效果:

'123456789'.replace(/(?<=\d)(?=(\d{3})+$)/g,',')
// output  123,456,789
'23456789'.replace(/(?<=\d)(?=(\d{3})+$)/g,',')
// output  23,456,789
'1234'.replace(/(?<=\d)(?=(\d{3})+$)/g,',')
// output  1,234

例子三:比如想把雷老板的Are you ok 歌词处理一下。

首先不想替换掉"...",其次注意转义字符,最后结合需要取的是引号内包含且非"的字符,于是得出:

 /\"([^\"\.]*)\"/g 

测试一下:

var str = `
Are you ok?
Auther Mr.Lei
1. "Thank you!"
2. "Are you ok?"
3. "Hello"
4. "Thank you"
5. "Thank you every much"
6. "How are you Indian Mi fans?"
7. "Do you like Mi 4i?"
8. "..."
`;

var reg = /\"([^\"\.]*)\"/g; 
var replaceStr = str.replace(reg,'\"???\"');
// output 
// Are you ok?
// Auther Mr.Lei
// 1. "???"
// 2. "???"
// 3. "???"
// 4. "???"
// 5. "???"
// 6. "???"
// 7. "???"
// 8. "..."

如何写正则表达式的总结:先写出明确的匹配条件,再根据需求去组合或添加细节。

正则表达式优化的一些探索

《精通正则表达式》书中和网上查找了不少资料,并且根据对NFA的理解,列出了一些符合理论的优化建议(不排除更多可能):

  1. 减少或者优化判断分支;

  2. 精确匹配条件(字符和量词);

  3. 限制匹配优先的作用范围,如+和*的区别,+减少了多选结构的回溯次数;

  4. 节省引用(使用非获取匹配);

  5. 将复杂的多条件正则拆分成多个简单的单条件正则;

  6. 锚点的优化,^(a|b)而非(^a|^b);

  7. 量词等价转换的效率差异(因语言而异);

  8. 使用固化分组(在支持的情况下,js并不支持);

  9. 使用变量存储正则表达式(减少正则编译过程);

  10. 还有更多细节...

《精通正则表达式》的第五及第六章都有涉及这些优化的介绍,网上google/baidu也是不少资料和案例。

根据其主要做的优化过程大致可总结出以下几点(不排除更多可能):

  1. 减少匹配的回溯次数,减少时间;

  2. 节省引用(使用非获取匹配),减少空间;

  3. 正则表达式自身优化以达到编译最优;

  4. 也许更多吧...

以上是书籍和网上给出的优化建议,给出的案例大多是针对的perl和PHP的,在JavaScript中并不适用,为了验证js里的正则如何优化,下面是我给出的一些测试结果...

基于JavaScript的正则表达式...这一小节给不出完整的测试代码,因为在多个浏览器和nodejs端跑了很多测试代码,给定的情况是不同的...

但单独某个端或者浏览器给出的结果是稳定的,以下是给出Chrome和Firefox浏览器和Nodejs各跑100000次(原先是1W长度字符串跑1000次,后面为了效果更明显最终增加为10W长度字符串跑10W次)测试的结果总结...还有Safari浏览器、360浏览器、QQ浏览器的测试结果也统一不了。

Chrome浏览器下:
    精确查找条件比使用.、*这类元字符或者范围的性能要优;
    非贪婪模式和贪婪模式的效率差别不大,按平均值比较非贪婪模式性能优;
    获取匹配和非获取匹配效率差别不大,按平均值来看非获取匹配性能优;
    优化判断分支(将最可能匹配的结果放前面)性能更差;

Firefox浏览器下:
    精确查找条件和使用.、*这类元字符或者范围的效率差别不大,按平均值比较元字符或者范围的性能优;
    非贪婪模式和贪婪模式的效率差别不大,按平均值比较贪婪模式性能优;
    获取匹配和非获取匹配效率差别不大,按平均值来看获取匹配性能优;
    优化判断分支(将最可能匹配的结果放前面)性能更优;

Nodejs环境下:
    使用.、*这类元字符或范围比精确查找条件的性能要优;
    非贪婪模式和贪婪模式的效率差别不大,按平均值比较非贪婪模式性能优;
    获取匹配和非获取匹配效率差别不大,按平均值来看非获取匹配性能优;
    优化判断分支(将最可能匹配的结果放前面)性能更差;

以上的测试结果并不能给出肯定的答案,所以建议在JavaScript里使用正则的时候先测一下性能以免导致不愉快的意外,至于JavaScript中正则表达式的实现过程更是需要看V8的代码了...

JavaScript RegExp 小扩展

lastIndex 和 test 方法的爱恨情仇

var str = 'abcabc';
var regexp = /a/g;

console.log(regexp.test(str));  // output true 
console.log(regexp.lastIndex);  // output 1 

console.log(regexp.test(str));  // output true 
console.log(regexp.lastIndex);  // output 4

console.log(regexp.test(str));  // output false 
console.log(regexp.lastIndex);  // output 0

test 方法在执行后将 lastIndex 属性值置为匹配到的结果索引值,并返回匹配结果;下一次执行 test 方法时从 lastIndex 位置开始匹配,并返回匹配结果;以此类推;最后一次执行 test 方法,索引重置为0,匹配结果为false。

RegExp vs indexOf 谁才是快男

在固定匹配值和"只匹配一次"的条件下,针对判断字符串是否包含某个"固定的"字符串,indexOf 优于 regexp,性能将近一半。

var str = "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/71.0.3578.98 Safari/537.36";

console.time('reg');
/Mac/.test(str);
console.timeEnd('reg');

console.time('indexOf');
str.indexOf('Mac');
console.timeEnd('indexOf');

经过多次测试  reg 的平均值 是 indexOf 的近2倍(环境:chrome & nodejs);然而在其他匹配条件下,RegExp 更灵活,更方便,更全面。

关于String.prototype.indexOf方法内部代码暂时不知道怎么去探究,根据以下文档有解释,但未明确的理解,参考文档:

[ECMAScript 2015 (6th Edition, ECMA-262)]

[ECMAScript 1st Edition (ECMA-262)](初始定义)

注意:本文只是一次知识探讨,仅供做参考作用,请勿以之为准,如果需要更进一步的学习请以书籍以及自我实践所得为准。