一句话：提出位向量自动机（NBVA）模型与算法，使含界重复的正则表达式匹配时间与重复次数上限无关，并实现 BVA-Scan 引擎。
正则表达式广泛用于现代软件。回溯式匹配引擎虽支持界重复等高级构造，但在某些模式上匹配时间可随输入文本指数增长；基于自动机的引擎效率更有保证，然而实际正则中的界重复构造仍会导致严重性能退化。本文提出针对含界重复正则表达式的高效匹配算法，其基础是一种新的自动机模型——非确定性位向量自动机（NBVA），其表达能力等价于计数器有界的非确定性计数器自动机。作者证明存在一类含界重复的正则表达式，其匹配时间与重复次数上限无关，覆盖实践中绝大多数困难的界重复情形；并在正则引擎 BVA-Scan 中实现该方法，在多个真实数据集上与最先进的正则引擎进行了比较。
Regular expressions (regexes) are ubiquitous in modern software. There is a variety of implementation techniques for regex matching, which can be roughly categorized as (1) relying on backtracking search, or (2) being based on finite-state automata. The implementations that use backtracking are often chosen due to their ability to support advanced pattern-matching constructs. Unfortunately, they are known to suffer from severe performance problems. For some regular expressions, the running time for matching can be exponential in the size of the input text. In order to provide stronger guarantees of matching efficiency, automata-based regex matching is the preferred choice. However, even these regex engines may exhibit severe performance degradation for some patterns. The main reason for this is that regexes used in practice are not exclusively built from the classical regular constructs, i.e., concatenation, nondeterministic choice and Kleene's star. They involve additional constructs that provide succinctness and convenience of expression. The most common such construct is bounded repetition (also called counting), which describes the repetition of the pattern a fixed number of times. In this paper, we propose a new algorithm for the efficient matching of regular expressions that involve bounded repetition. Our algorithms are based on a new model of automata, which we call nondeterministic bit vector automata (NBVA). This model is chosen to be expressively equivalent to nondeterministic counter automata with bounded counters, a very natural model for expressing patterns with bounded repetition. We show that there is a class of regular expressions with bounded repetition that can be matched in time that is independent from the repetition bounds. Our algorithms are general enough to cover the vast majority of challenging bounded repetitions that arise in practice. We provide an implementation of our approach in a regex engine, which we call BVA-Scan. We compare BVA-Scan against state-of-the-art regex engines on several real datasets.
@article{paperbot2023,
title = {Regular Expression Matching using Bit Vector Automata},
author = {Alexis Le Glaunec and Lingkun Kong and Konstantinos Mamouras},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA1},
year = {2023},
doi = {10.1145/3586044}
}