利用关键因子过滤的正则表达式匹配算法

来源：计算机科学与探索杂志2016年第3期北京时间：

作者：邱涛，王斌，杨晓春

单位：东北大学 信息科学与工程学院，沈阳 110819

摘要：正则表达式（regular expression，RE）是一种能够提供复杂查询能力的技术，其通过特定的语法结构来描述一类文本的共同特征。正则表达式强大的表达能力和简洁的语法，使得其在各个领域都被广泛地应用。为了提高正则表达式的匹配效率，提出了一种利用关键因子进行过滤的匹配技术，关键因子指的是在文本中具有最小出现频率的有效过滤因子。由于实际文本中字符并不是均匀分布的，子串在文本中出现频率的差异将影响过滤因子的过滤能力。通过考虑有效过滤因子在文本中出现的频率，关键因子能获得更好的过滤能力。提出了利用正则表达式的划分来求取关键因子的算法，进而通过关键因子来过滤候选位置。通过在真实的蛋白序列和英文文本上进行实验，说明了基于关键因子过滤的匹配方法可以有效地提升正则表达式的匹配性能。

关键词：正则表达式,过滤策略,算法性能,关键因子