Efficient Regex Matching with Sparse Counting-Sets
For developers and systems using regular expressions with counting operations, this work provides a more efficient matching method.
The paper addresses the performance bottleneck in regex matching with counting operations caused by replication of counting-sets during branching. The proposed sparse counting-set approach reduces replication overhead, yielding a more efficient matching algorithm.
Regular expressions with counting operations (c-regexes) offer a compact representation of repeating patterns by allowing numerical bounds to be added to subexpressions. Recent work introduced the counting-set data structure, which allows simultaneous updates of multiple counter values for efficient matching. However, this approach suffers from a performance bottleneck when counting-sets must be replicated due to the presence of branching transitions. We propose a sparse counting-set approach, which reduces the replication overhead by maintaining only essential counter values, thereby yielding a more efficient matching algorithm.