RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement and Lookarounds
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917901298040832 |
|---|---|
| author | Varatalu, Ian Erik Veanes, Margus Ernits, Juhan-Peep |
| author_facet | Varatalu, Ian Erik Veanes, Margus Ernits, Juhan-Peep |
| contents | We present a tool and theory RE# for regular expression matching that is built on symbolic derivatives, does not use backtracking, and, in addition to the classical operators, also supports complement, intersection and lookarounds. We develop the theory formally and show that the main matching algorithm has input-linear complexity both in theory as well as experimentally. We apply thorough evaluation on popular benchmarks that show that RE# is over 71% faster than the next fastest regex engine in Rust on the baseline, and outperforms all state-of-the-art engines on extensions of the benchmarks often by several orders of magnitude. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_20479 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement and Lookarounds Varatalu, Ian Erik Veanes, Margus Ernits, Juhan-Peep Formal Languages and Automata Theory F.4.3; I.1.3 We present a tool and theory RE# for regular expression matching that is built on symbolic derivatives, does not use backtracking, and, in addition to the classical operators, also supports complement, intersection and lookarounds. We develop the theory formally and show that the main matching algorithm has input-linear complexity both in theory as well as experimentally. We apply thorough evaluation on popular benchmarks that show that RE# is over 71% faster than the next fastest regex engine in Rust on the baseline, and outperforms all state-of-the-art engines on extensions of the benchmarks often by several orders of magnitude. |
| title | RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement and Lookarounds |
| topic | Formal Languages and Automata Theory F.4.3; I.1.3 |
| url | https://arxiv.org/abs/2407.20479 |