IT技术博客大学习 共学习 共进步

[正则优化] CSS选择符匹配

Miller 2011-09-04 23:37:56 浏览 3,422 次

正则表达式如下

^((^|,)\s*[.\w-][.\w\s\->+~]*)+$

这个正则表达式的作用是用来匹配一些简单的CSS选择符,例如:

/*能匹配成功的*/
.a select,.b input,.b input
.a select,div.test > a,.b input
/*匹配失败的*/
.a select,.b input,.b input[type="submit"]

该表达式在匹配成功时的效率还是比较高的,因为里面使用了字符集进行贪婪匹配,接下来以匹配 ".a select,.b input,.b input " 这个文本来具体分析一下它的效率问题,具体的匹配过程见下图

(使用的工具是RegexBuddy):

2010-11-06_082332

从上图可以看出由于使用了字符集+贪婪匹配([.\w\s\->+~]*),因此在匹配每个","号之间的内容时速度还是非常快的。但是回过头去看一下,文本的长度一共是27个字符,而匹配总共使用了27步,因此效率上还是有提升的余地,具体的问题主要集中在以下几点:

1. 首先,匹配的一开始的4步显示的都是"ok",这里的前两次"ok"实际上都是匹配起始符^的结果。那么为社么这里会匹配两次^,第一次不用多说,第二次是因为表达式最外层的+号实际上是一个循环,即+所限定的表达式会一次一次的循环,每一次循环时表达式要匹配的第一个字符都是起始符^,因此前4步就有一步是多余的。

2.再往后看,会发现匹配中有很多的"backtrack",这就是传说中的"回溯",回溯是浪费正则匹配效率的罪魁祸首,正则优化的最主要手段就是减少回溯。先分析下这些回溯是怎么出现的,知道原因才容易找对策。其实回溯的原因在第1点中已经给出来了,正是(^|,)中的^造成的,因为每次循环尝试匹配的第一个字符就是^,而实际上^在文本中只会出现一次,例如.a select匹配完成后,表达式会进入下一次循环匹配,文本中的下一个字符实际上是",",而正则会拿^来匹配,显然会失败,失败之后便造成回溯。而最后3次回溯的原因是:匹配^失败、匹配","失败以及最后一轮循环整体匹配失败。

通过分析文本的结构实际上是可以避免以上问题的,文本的结构基本上可以看成是逗号+简单选择符的结构,可以概括成start  normal(special normal+)* end 这样的结构(猫头鹰书上有提到),normal指的就是"\s*[.\w-][.\w\s\->+~]*",special指的就是",",根据这个结构将表达式改下如下:

^\s*[.\w-][.\w\s\->+~]*(,\s*[.\w-][.\w\s\->+~]*)*$

由于每次大的循环都是寻找以","开头的字符串,可以有效的解决上面提到的问题,具体的看执行过程:

2010-11-06_085255

从上图可以看出该表达式有效的解决了之前的回溯问题,而实际的性能提升也是比较明显的:IE6下的测试结果,优化后的性能提升在10%-20%左右,Chrome下8%左右,Firefox下30%左右,具体的测试结果可以去 http://jsperf.com/regexp-test-2 围观。

建议继续学习

  1. 字符串匹配那些事(一) (阅读 7,104)
  2. grep 正则表达式选项要记得转义 (阅读 6,445)
  3. 统计最近用过的linux命令 (阅读 6,405)
  4. 正则表达式基础 (阅读 6,162)
  5. 正则表达式的与或非 (阅读 5,744)
  6. 学习Grep,Sed中的正则 (阅读 5,267)
  7. URL正则表达式 (阅读 4,663)
  8. 利用vim(gvim)的正则表达式实现代码自动匹配完成(等号两边数据交换) (阅读 4,525)
  9. 正则表达式简要入门 (阅读 4,364)
  10. 正则转义符汇总 (阅读 4,321)