Efficient Regex Matching with Sparse Counting-Sets

Martin Berglund, Brink van der Merwe, Sicheol Sung · 2026

Read Efficient Regex Matching with Sparse Counting-Sets by Martin Berglund, Brink van der Merwe, Sicheol Sung (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26679.txt.

Description

Counting regular expressions get a faster matching method from Martin Berglund, Brink van der Merwe, and Sicheol Sung, who make counting regular expressions faster to match. A counting expression states that a pattern repeats at least and at most a set number of times. Matching such expressions naively is slow. A recent data structure, the counting-set, updates many counter values at once. Branching paths, though, force counting-sets to be copied, and the copying dominates the cost.

The authors propose sparse counting-sets. Only essential counter values are stored and carried along. Replication overhead falls sharply as a result. Their matching algorithm keeps the simultaneous-update benefit while shedding the copying bottleneck. The work targets implementations where bounded repetition is common, such as validation of structured text. Efficiency gains come without changing which strings the expressions accept.

Catalog record

CREATORMartin Berglund, Brink van der Merwe, Sicheol Sung
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26679

Browse the full library · About the Tower of Babel