一种正则表达式的高效分组算法

正则表达式（Regular Expression,RE）因其强大的表达能力和简单性正取代精确字符串（explicitstring）成为描述模式（pattern）的首选。在网络应用中,基于DFA（确定有限自动机）的正则表达式匹配技术通常用于网络流量实时处理、病毒检测等系统中。随着正则表达式的数量不断增加,DFA的存储空间急剧膨胀导致Cache的命中率大大降低,最终影响匹配的性能。提出了一种高效的正则表达式分组算法,通过合理地将正则表达式分组来大大降低DFA所需的存储空间。还尝试提出了评价正则表达式分组算法的一些指标。

An Efficient Regular Expression Grouping Algorithm

Regular expressions are replacing explicit string patterns as the choice of describing patterns owing to their expressive power and simplicity. Regular expression matching technology based on DFA(Deterministic Finite Automaton)is commonly used in network real-time processing, virus detection systems etc. With the number of regular expression patterns increasing, the storage space of DFA expands rapidly, which decreases the hit rate of Cache and affect the matching performance ultimately. This paper presents...