Regular Expressions: Matching and Indexing

We survey the classic regular expression matching problem, that is, given a regular expression $R$ and a string $Q$ determine whether or not $Q$ is in the language defined by $R$. We cover the algorithmic techniques and the history of the problem, from Thompson’s classic algorithm from the 60’ties [C. ACM 1968] to the present day.

In this talk I overviewed bit-parallel techniques for complex pattern matching, going from simple strings to regular expressions, via some useful complex patterns of intermediate complexity. I showed how bit-parallelism allows easy and efficient simulation of complex patterns whose deterministic automaton has no simple structure, yet their nondeterministic structure is regular and allows a bit-parallel simulation. This enables not only efficient bit-parallel search of those complex patterns, but also simulating their suffix automata, such as to implement search algorithms that can skip text positions, which without bit-parallelism can only be done for simple strings. Further, I showed how approximate searching can be incorporated into those searches, so that there can be up to k differences between the matched text and some string in the language of the complex pattern. I finished with a nice application to natural language that exploits all the flexibility of this matching both at the intra-word and the inter-word level.

I will give an overview to the use of regular expressions in two areas in databases: information extraction and graph databases. In information extraction, regular expressions play a central role in the document spanner framework. This framework aims at transforming text into a relation of spans, i.e., intervals of start and end positions in the text. Within the spanner framework, the class of regular spanners is particularly interesting, since it is based on regular expressions with capture variables. I will also briefly touch upon frequent sequence mining. In graph databases, regular expressions have been interesting since the beginning, since they form the foundation of regular path queries, which are the quintessential feature of graph database query languages. Recent developments in graph query languages, among which the development of Cypher and the standardization of GQL and SQL/PGQ, motivate new ways of evaluating regular path queries in practice, which raises many new research questions.

In this talk, I will present REmatch, a novel regex engine that always finds all matches. REmatch is based on document spanners, a formal framework for information extraction based on regular expressions and finite automata with capture variables. Given a document (i.e., a string), this framework allows for the definition of extraction tasks by regular expressions with variables in a denotational manner, namely, without depending on the leftmost longest semantics of regex or any evaluation strategy. I will present the main features of REmatch, such as its query language called REQL (RegEx Query Language), the use of variables, and multimatch capturing. Furthermore, I will overview the theory behind REmatch, such as regular expression with capture variables, variable-set automata, and its query evaluation algorithm, based on the theory of constant-delay enumeration algorithms.

Most modern implementations of regular expressions have back-references, which express repetitions of submatches. These allow the definition of non-regular languages, like the copy language $ww$. The price for this gain in expressive power is that matching becomes $\mathrm{𝖭𝖯}$-hard.

In this talk, I present a relational algebra on strings that allows us to adapt techniques from database theory to matching of regular expressions with back-references. It also provides us with a framework to combine these with parsing techniques.

An elegant formalism for describing scenarios where we need to process large amounts of string data arriving online is the streaming model. In this model, the input characters arrive one by one; we cannot go back to any previously seen characters and need to output the answer after receiving the next character. The primary goal is minimizing the amount of working space measured in bits, and the secondary goal is to optimize the time to process a character. It has been shown by Porat and Porat [FOCS 2009] that the classical exact pattern matching problem can be solved in this model using only $O(\log n\log m)$ bits of space with high probability. I will briefly present the properties of the streaming model and an overview of their algorithm.

As pattern matching can be encoded as a regular expression, it is natural to consider, given a general regular expression $R$, checking which prefixes of the text belong to $L(R)$. While it is not difficult to prove that we cannot solve the general case in sublinear space, we can hope to obtain such a bound for restricted classes of regular expressions. In particular, it is natural to limit the number of strings appearing in the regular expression by $d$, and aim at obtaining space complexity that is polynomial in $d$ and $\log n$ (where $n$ is the length of the text). I will sketch some of the ideas used in designing such an algorithm.

In Regular Expression indexing we are given a text T which we seek to index – preprocess a data structure on T – to answer queries q, a regular expression, to find locations in T where a substring begins that belongs to the language of q.

We show (a) conditional lower bounds using fine-grained complexity, (b) the algorithm of Baeza-Yates and (c) the algorithm of Gibney and Thankachan. We then consider restricted cases of regular expressions; (a) text indexing with don’t cares in the pattern queries and (b) gapped indexing, where the pattern queries are of the form (p1,p2,a,b), and we seek all appearance of pairs p1 and p2 with the distance between p1 and p2 being in the range of a and b.

Since the invention of suffix sorting (in particular, of suffix trees) in the 70s, the problem of indexed pattern matching has been heavily studied in the literature. This problem has a natural language-theoretic interpretation: given a string S, build a (linear-space) data structure answering membership queries in the substring closure of S. This interpretation was recently made more interesting by several works showing that suffix sorting can be naturally extended to some nonlinear structures, notably labeled trees and de Bruijn graphs. This line of work culminated in the invention of Wheeler automata, a class of NFAs admitting efficient and elegant solutions to a large number of hard problems on automata (including membership). In this talk, I will first give an introduction to the rich theory of Wheeler automata and Wheeler languages. I will then show how these ideas can be generalized to arbitrary NFAs, comparing this solution to other existing approaches for indexing arbitrary regular languages.

Until recently, regular expression matching has mostly been implemented using backtracking, which led to a denial-of-service vulnerability known as ReDoS. In ReDoS, matching does not complete in linear time and can take an excessive amount of time. In this talk, we will review previous works that detect such problematic regular expressions through ambiguity analysis of nondeterministic automata and growth rate analysis of string-to-tree transducers. For a given regular expression, it is possible to precisely determine the time complexity (order) of its matching with respect to the length of the input string.

Regular expressions can be extended with lookaround assertions, which are subdivided into lookahead and lookbehind assertions. These constructs are used to refine when a match for a pattern occurs in the input text based on the surrounding context. Current implementation techniques for lookaround involve backtracking search, which can give rise to running time that is super-linear in the length of input text. In this talk, we first present a formal mathematical semantics for lookaround, which complements the commonly used operational understanding of lookaround in terms of a backtracking implementation. This formal semantics allows us to establish several equational properties for simplifying lookaround assertions. Additionally, we propose a new algorithm for matching regular expressions with lookaround that has time complexity $O(m\cdot n)$, where $m$ is the size of the regular expression and $n$ is the length of the input text. The algorithm works by evaluating lookaround assertions in a bottom-up manner. It makes use of a notion of nondeterministic finite automata (NFAs), which we call oracle-NFAs. These automata are augmented with epsilon-transitions that are guarded by oracle queries that provide the truth values of lookaround assertions at every position in the text. We provide an implementation of our algorithm that incorporates three performance optimizations for reducing the work performed and memory used. We present an experimental comparison against PCRE and Java’s regex library, which are state-of-the-art regex engines that support lookaround assertions. Our experimental results show that, in contrast to PCRE and Java, our implementation does not suffer from super-linear running time and is several times faster.

A subsequence expression is a regular expression of the form $p=A^{\ast }{x}_1{A}^{\ast }{x}_2{A}^{\ast }\mathrm{\dots }{A}^{\ast }{x}_m{A}^{\ast }$, where $A$ is an alphabet and $x_i\in A$. Matching $p$ to a string $w$ means to search $w$ for the subsequence $x_1{x}_2\mathrm{\dots }{x}_m$. A match can be formalised as an embedding $e:|p|->|w|$, which then, for every , induces an $(i,j)$-gap, i.e., the substring of $w$ that occurs strictly between $w[e(i)]$ and $w[e(j)]$. Gap constraints are constraints for the gaps induced by an embedding, e. g., "the $(i,j)$-gap should be no longer than $7$", "the $(i,j)$-gap should not contain the symbol $c$", etc.

We investigate the problem of matching a subsequence expression to a string under the presence of gap constraints, where the gap constraints are given as regular languages. Our results cover hardness results as well as polynomial upper bounds and conditional lower bounds.

Regular Path Queries (RPQs), which are essentially regular expressions to be matched against the labels of paths in labeled graphs, are at the core of graph database query languages like SPARQL and GQL. A way to solve RPQs is to translate them into a sequence of operations on the adjacency matrices of each label. We design and implement a Boolean algebra on sparse matrix representations and, as an application, use them to handle RPQs. Our baseline representation uses the same space and time as the previously most compact index for RPQs, outper- forming it on the hardest types of queries – those where both RPQ endpoints are unspecified. Our more succinct structure, based on k2 -trees, is 4 times smaller than any existing representation that handles RPQs. While slower, it still solves complex RPQs in a few seconds and slightly outperforms the smallest previous structure on the hardest RPQs. Our new sparse- matrix-based solutions dominate a good portion of the space/time tradeoff map, being outperformed only by representations that use much more space. They also implement an algebra of Boolean matrices that is of independent interest beyond solving RPQs.

We propose techniques to evaluate regular path queries (RPQs) over labeled graphs (e.g., RDF). We apply a bit-parallel simulation of a Glushkov automaton representing the query over a Ring: a compact wavelet-tree-based index of the graph. To the best of our knowledge, our approach is the first to evaluate RPQs over a compact representation of such graphs, where we show the key advantages of using Glushkov automata in this setting. We introduce various optimizations, such as the ability to process several automaton states and graph nodes/labels simultaneously, and to accurately estimate relevant selectivities. Experiments show that our approach uses $3-5\times$ less space, and is over $5\times$ faster, on average, than the next best state-of-the-art system for evaluating RPQs.

Maximal Common Subsequences (MCSs) – the inclusion-maximal sequences of non-contiguous symbols shared by strings – are a natural extension of known methods like Longest Common Subsequences but have only recently gained attention. This talk presents McDag, an efficient graph-based tool to index MCSs on real genomic data, showing it can handle sequence pairs over 10,000 base pairs in minutes with minimal extra storage.

In this talk I will present parameterized linear-time algorithms for SMLG (string matching to labeled graphs) on DAGs. Our algorithms run in time $O(k|G|+|P|)$. We obtain the result separately for a parameter capturing the topology of the DAG $G$, and for a parameter capturing the periodicity of the pattern $P$. Additionally, we present an algorithm running in time proportional to the number of prefix-incomparable matches, which is able to capture both parameters previously mentioned. To obtain the parameterization in the topological structure of $G$, we generalize in-trees, out-trees and funnels to the classes $S_k$, $T_k$ and $S{T}_k$, respectively.

Regular expression denial of service (ReDoS) is an asymmetric cyberattack that has become prominent in recent years. This attack exploits the slow worst-case matching time of regular expression (regex) engines. In this talk, I describe the history of ReDoS, recent developments, and open problems for the future. I trace the history of slow regex performance due to backtracking back to the seminal work of Thompson in 1968, describe how this property can be applied for ReDoS, and indicate how it has been discovered and rediscovered over the years. In the past decade, ReDoS has shifted from a curiosity to a mainstream security concern, thanks to industrial disasters, changes in web software architectures, and the availability of measurement tools. Most mainstream regex engines have now been defended against ReDoS to varying degrees of success. I close by indicating open problems focused on the need to parameterize our worst-case regex analyses to modern algorithms that no longer rely on naïve backtracking.