Efficient Matching of Some Fundamental Regular Expressions with Backreferences
Taisei Nogami, Tachio Terauchi · 2025
Read Efficient Matching of Some Fundamental Regular Expressions with Backreferences by Taisei Nogami, Tachio Terauchi (2025) 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-2504-18247.txt.
Introduction
Taisei Nogami and Tachio Terauchi wrote this 2025 arXiv paper on faster pattern matching in text. Regular expressions are the standard tool for finding patterns in strings, and most programming languages extend them with backreferences, which demand that a later chunk repeat an earlier one. That small feature makes matching very hard in theory, and fast methods exist only for narrow cases.
The authors tackle a basic and common shape of such patterns, with one backreference in the middle. Their method mixes ideas from string science and automata theory, checking at once the repeats that could work. It decides a match in time that grows with the square of the string length, a clear gain over the best known cubic time. The result brings a widely used pattern shape closer to practical speed.
Catalog record
| CREATOR | Taisei Nogami, Tachio Terauchi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18247
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Matching of Some Fundamental Regular Expressions with Backreferences Taisei Nogami, Tachio Terauchi Abstract Regular expression matching is of practical importance due to its widespread use in real-world applications. In practical use, regular expressions are often used with real-world extensions. Accordingly, the matching problem of regular expressions with real-world extensions has been actively studied in recent years, yielding steady progress. However, backreference , a popular extension supported by most modern programming languages such as Java, Python, JavaScript and others in their standard libraries for string processing, is an exception to this positive trend. In fact, it is known that the matching problem of regular expressions with backreferences (rewbs) is theoretically hard and the existence of an asymptotically fast matching algorithm for arbitrary rewbs seems unlikely. Even among currently known partial solutions, the balance between efficiency and generality remains unsatisfactory. To bridge this gap, we present an efficient matching algorithm for rewbs of the form e 0 ( e ) 1 e 1 \ 1 e 2 e_{0}(e)_{1}e_{1}\backslash 1e_{2} where e 0 , e , e 1 , e 2 e_{0},e,e_{1},e_{2} are pure regular expressions, which are fundamental and frequently used in practical applications. It runs in quadratic time with respect to the input string length, substantially improving the best-known cubic time complexity for these rewbs. Our algorithm combines ideas from both stringology and automata theory in a novel way. We leverage two techniques from automata theory, injection and summarization , to simultaneously examine matches whose backreferenced substrings are either a fixed right-maximal repeat or its extendable prefixes , which are concepts from stringology. By further utilizing a subtle property of extendable prefixes, our algorithm correctly decides the matching problem while achieving the quadratic-time complexity. Waseda University, Tokyo, [email protected]://orcid.org/0009-0002-2820-8615 Waseda University, Tokyo, Japan and https://www.f.waseda.jp/terauchi/ [email protected]://orcid.org/0000-0001-5305-4916 ccs Theory of computation Regular languages ccs Theory of computation Pattern matching keywords Regular expressions, Backreferences, Regex matching, NFA simulation, Suffix arrays, Right-maximal repeats † † runningtitle: Efficient Matching of Some Fundamental Regular Expressions with Backreferences † † runningauthor: T. Nogami and T. Terauchi † † copyright: Taisei Nogami and Tachio Terauchi † † supplement: Software: https://github.com/nogamita/MFCS2025 † † funding: This work was supported by JSPS KAKENHI Grant Numbers JP25KJ2137, JP23K24826, and JP20K20625. † † editors: Paweł Gawrychowski, Filip Mazowiecki, and Michał Skrzypczak † † event-title: 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) † † event-shorttitle: MFCS 2025 † † event-acronym: MFCS † † year: 2025 † † event-date: August 25–29, 2025 † † event-location: Warsaw, Poland † † series-volume: 345 † † articleno: 91 1 Introduction A regular expression is a convenient way to specify a language (i.e., a set of strings) using concatenation ( \cdot ), disjunction ( \mid ) and iteration ( \ast ). The regular expression matching problem (also known as regular expression membership testing ) asks whether a given string belongs to the language of a given regular expression. This problem is of practical importance due to its widespread use in real-world applications, particularly in format validation and pattern searching. In 1968, Thompson presented a solution to this problem that runs in O({nm}) time where n denotes the length of the input string and m the length of the input regular expression [ 47 ] . We refer to his method, which constructs a nondeterministic finite automaton (NFA) and simulates it, as NFA simulation . The matching problem of real-world regular expressions becomes increasingly complex due to its practical extensions such as lookarounds and backreferences . Unfortunately, reducing the matching of real-world regular expressions to that of pure ones is either inefficient or impossible. In fact, although adding positive lookaheads (a type of lookaround) does not increase the expressive power of regular expressions [ 33 , 8 ] , the corresponding NFAs can inevitably become enormous [ 32 ] . Worse still, adding backreferences makes regular expressions strictly more expressive, meaning that an equivalent NFA may not even exist. 1 1 1 The rewb ((a|b)^{\ast})_{1}\backslash 1 specifies \{ww\mid w\in\{a,b\}^{\ast}\} , which is non-context-free (and therefore non-regular). Nevertheless, most modern programming languages, such as Java, Python, JavaScript and more, support lookarounds and backreferences in their standard libraries for string processing. The most widely used implementation for the real-world regular expression matching is backtracking [ 45 ] , an algorithm that is easy to implement and extend. On the other hand, the backtracking implementation suffers from a major drawback in that it takes exponential time in the worst case with respect to the input string length. This exponential-time behavior poses the risk of ReDoS (regular expression denial of service) , a type of DoS attack that exploits heavy regular expression matching to cause service downtime, making it a critical security issue (refer to Davis et al. [ 15 ] for details on its history and case studies). In response, RE2, a regular expression engine developed by Google, has deferred supporting lookarounds and backreferences, thereby ensuring O({nm}) time complexity using NFA simulation. 2 2 2 The development team declares, “Safety is RE2’s raison d’être.” [ 48 ] Regarding lookarounds, several recent papers have proposed groundbreaking O({nm}) -time solutions to the matching problem of regular expressions with lookarounds [ 31 , 22 , 6 ] , yet regarding backreferences, the outlook is bleak. The matching problem of regular expressions with backreferences (rewbs for short) is well known for its theoretical difficulties. Aho showed that the rewb matching problem is NP-complete [ 2 ] . Moreover, rewbs can be considered a generalization of Angluin’s pattern languages (also known as patterns with variables ) [ 4 ] ; even when restricted to this, its matching problem is NP-complete with respect to the lengths of both a given string and a given pattern [ 4 , 17 , 41 ] , and its NP-hardness [ 19 ] as well as W[1]-hardness [ 20 ] are known for certain fixed parameter settings. The best-known matching algorithm for rewbs with at most k capturing groups runs in O({n^{2k+2}m}) time [ 42 , 43 ] (With a slight modification, the time complexity can be reduced in O({n^{2k+1}m}) time; see Section 4 ). Therefore, the existence of an efficient worst-case time complexity algorithm that works for any rewb seems unlikely, necessitating researchers to explore efficient algorithms that work for some subset of rewbs [ 40 , 43 , 21 ] . Nevertheless, all existing solutions either have high worst-case time complexity or impose non-trivial constraints on the input rewbs, and finding a good balance between efficiency and generality remains an open issue. To bridge this gap, we present an efficient matching algorithm for rewbs of the form e_{0}(e)_{1}e_{1}\backslash 1e_{2} , where e_{0},e,e_{1},e_{2} are pure regular expressions, which are fundamental and frequently encountered in practical applications. While the best-known algorithm for these rewbs is the one stated above and it takes O({n^{4}m}) (or O({n^{3}m}) ) time because k=1 for these rewbs, our algorithm runs in O(n^{2}m^{2}) time, improving the best-known time complexity for these rewbs with respect to the input string length n from cubic to quadratic. The key appeal of this improvement lies in the replacement of the input string length n with the expression length m . Because n is typically much larger