Efficient submatch extraction for practical regular expressions

Stuart Haber*, William Horne, Pratyusa Manadhata, Miranda Mowbray, Prasad Rao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

4 Citations (Scopus)

Abstract

A capturing group is a syntax used in modern regular expression implementations to specify a subexpression of a regular expression. Given a string that matches the regular expression, submatch extraction is the process of extracting the substrings corresponding to those subexpressions. Greedy and reluctant closures are variants on the standard closure operator that impact how submatches are extracted. The state of the art and practice in submatch extraction are automata based approaches and backtracking algorithms. In theory, the number of states in an automata-based approach can be exponential in n, the size of the regular expression, and the running time of backtracking algorithms can be exponential in ℓ, the length of the string. In this paper, we present an O(ℓc) runtime automata based algorithm for extracting submatches from a string that matches a regular expression, where c > 0 is the number of capturing groups. The previous fastest automata based algorithm was O(nℓc). Both our approach and the previous fastest one require worst-case exponential compile time. But in practice, the worst case behavior rarely occurs, so achieving a practical speed-up against state-of-the-art methods is of significant interest. Our experimental results show that, for a large set of regular expressions used in practice, our algorithm is approximately twice as fast as Java's backtracking based regular expression library and approximately twenty times faster than the RE2 regular expression engine.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 7th International Conference, LATA 2013, Proceedings
Pages323-334
Number of pages12
Volume7810 LNCS
DOIs
Publication statusPublished - 2013
Event7th International Conference on Language and Automata Theory and Applications, LATA 2013 - Bilbao, Spain
Duration: 2 Apr 20135 Apr 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7810 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Language and Automata Theory and Applications, LATA 2013
Country/TerritorySpain
CityBilbao
Period2/04/135/04/13

Fingerprint

Dive into the research topics of 'Efficient submatch extraction for practical regular expressions'. Together they form a unique fingerprint.

Cite this