# Sublinear Time Regular Expression Search

Does there exist a data structure with the following properties. Given a string $$s$$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows searching $$s$$ for arbitrary regular expression patterns in time sublinear in the length of $$s$$, ideally constant or logarithmic. Ideally, the runtime would only depend polynomially on the length of the regex pattern being searched. Is anything known about this? If not, what is the closest one can come?

• I don't see how you could test equality of a string to another fixed string in time sublinear in the size of the fixed string, and your problem seems to reduce to this when the regular expression only contains symbols of the alphabet. Am I missing something? Jun 11 at 16:36
• @xavierm02, yes, I think you are missing something. The poster would be satisfied with an algorithm whose running time is $O(|p|)$ where $|p|$ is the length of the regexp pattern. In your example, $|p|=|s|$, so such an algorithm would not contradict the obvious lower bound you are thinking of.
– D.W.
Jun 11 at 20:03
• Right. I have the vague intuition that this could work: For each substring of $s$, add a new symbol that represents it, and let $f$ be the homomorphism that maps each new symbol to the corresponding substring of $s$, and maps the old symbols to themselves. Let $a$ be the symbol associated with the whole string, i.e. such that $f(a)=s$. The string $s$ is accepted by an automaton $A$ iff the reverse homomorphic image $B$ of $A$ by $f$ accepts $a$. Building $B$ explicitly is of course too long, but it seems plausible that we can build it lazily to solve the problem reasonably fast Jun 13 at 11:14
• Would you be interested by a "PAC" version of this ? i.e. works w.h.p. when $s$ matches $p$ or is far from matching it.
– GBat
Jun 22 at 8:25

Consider the following setup. Let $$s$$ be a string in the pattern <w1><w2>... for words $$w_1, w_2, \dots$$ that don't include <> in their alphabet. Now with the regex .*<w>.* we can check the existence of a word in the 'database' $$s$$. Better yet, we can substitute arbitrary characters of $$w$$ with a wildcard symbol ..

This gives a reduction from Lower bounds for high dimensional nearest neighbor search and related problems by Borodin et. al. where it's shown that constant time queries with polynomial space is impossible.

A stronger conjecture is provided, which would answer your question negatively altogether:

The common “wisdom” among researchers is that simultaneously getting $$poly(nd)$$ storage and $$poly(d)$$ search time is impossible. Moreover, it has been conjectured that either storage or search time must grow exponentially in $$d$$ (at least for certain values of $$n$$). This conjecture is known as the curse of dimensionality[19].

[19] K. Clarkson. An algorithm for approximate closest-point queries. In Proc. of 10th SCG, pp.160–164, 1994.

Here $$n$$ is the number of strings and $$d$$ is the size of each string, thus $$nd \sim |s|$$.

• Should "reduction to" be "reduction from" in this answer?
– a3nm
Jun 17 at 8:32
• @a3nm Yes, I always confuse the two :( The thing that you're reducing from is usually the goal of your argument, so in my mind it's our destination, and I'm likely to use 'to' wrong.
– orlp
Jun 17 at 9:02

It seems to me that your problem is very close to pattern matching in compressed text, which is an active area of research. It consists in searching given patterns in compressed strings, without decompressing them. It is then faster than parsing the strings.

I am not an expert, but the following seems to be a good reference: Practical and flexible pattern matching over Ziv–Lempel compressed text by Gonzalo Navarro and Mathieu Raffinot.

I think this works:

The basic idea is that after reading $$p\overset{u}{\to}q$$ and $$q\overset{v}{\to}r$$ in the automaton, we add a transition $$p\overset{u\cdot v}{\to}r$$. Of course, we need to avoid testing equality of strings because that would already be too slow. This is where the DAG factorization comes in.

I write $$\Sigma$$ for the alphabet, call the input word / string $$s\in \Sigma^*$$, and use a non-deterministic finite automaton $$\mathcal A=(Q, \Sigma, \Delta, I, F)$$ instead of the regular expression.

Precomputation: Computing a DAG factorization of $$s$$

A tree factorization is a finite (binary) tree (with a linear order on the children of each node) whose leaves are labeled by letters of the alphabet. Each node $$n$$ in a tree factorization $$T$$ represents a word $$u_n$$ defined as follows:

• If $$n$$ is a leaf labeled with the letter $$a$$ then $$u_n=a$$;

• If $$n$$ is an internal node with children $$n_1$$ and $$n_2$$ then $$u_n=u_{n_1}\cdot u_{n_2}$$ where $$\cdot$$ denotes concatenation.

While it is slightly easier to reason about tree factorizations, to get a fast algorithm, we instead use a DAG (i.e. directed acyclic graph) factorization where children can be shared by several parents. A DAG factorization is a DAG (with a linear order on the successors of each node) such that has exactly one source (i.e. one node with no incoming edge), and such that each sink (i.e. node with no outgoing edge) is labeled by a letter $$a\in \Sigma$$. Each node $$n$$ in a DAG factorization $$T$$ represents a word $$u_n$$ defined as follows:

• If $$n$$ is a sink labeled with the letter $$a$$ then $$u_n=a$$;

• It $$n$$ is not a sink and has children $$n_1,\dots, n_j$$, then $$u_n=u_{n_1}\cdot \dots \cdot u_{n_j}$$.

A DAG factorization of a string $$s$$ is a DAG factorization $$G$$ such that its source $$n$$ represents the word $$s$$, i.e. $$u_n=s$$.

The precomputation is just computing a DAG factorization of $$s$$, ideally the smallest possible. By this answer, we can build a DAG factorization $$G$$ based on a complete binary tree such that $$|G|=O\left(\frac{|s|}{\sqrt{\log |s|}}\right)$$ (where $$|G|$$ is the number of nodes in $$G$$).

This of course assumes that the alphabet is fixed. If the alphabet is not fixed, we can take an alphabet of size $$|s|$$ to build a word whose letters are all different, and the size of any DAG factorization of this string would have to contain all those letters as leaves, and hence be at least linear in $$|s|$$.

In the best case senario, $$|G|$$ is logarithmic in $$|s|$$. For example, when $$s=a^{2^k}$$, we can take a complete binary tree with nodes of depth $$j$$ labeled by $$a^{2^j}$$.

Running an automaton on a DAG factorization

Given a DAG factorization $$G$$ of $$s\in \Sigma^*$$, and the input automaton $$\mathcal A=(Q, \Sigma, \Delta, I, F)$$, the algorithm runs by associating a transition relation $$\Delta_{n}\subseteq Q\times Q$$ to each node $$n$$ of $$G$$ such that for each $$p$$ and $$n$$, $$(p, u_n, q) \in \Delta^* \iff (p, q) \in \Delta_n$$, i.e. $$\Delta_n$$ relates $$p$$ and $$q$$ if we can get from $$p$$ to $$q$$ by reading $$u_n$$ in the automaton.

• For leaves, $$\Delta_n=\Delta$$;

• For internal nodes $$n$$ with children $$n_1$$ and $$n_2$$, $$\Delta_n= \Delta_{n_1} ; \Delta_{n_2}=\{(p,r):\exists r, (p,q) \in \Delta_{n_1}\text{ and }(q,r) \in \Delta_{n_w}\}$$

We represent those transitions relations by dictionaries. Checking whether $$(p,q)\in \Delta_{n_1}$$ and $$(q,r)\in \Delta_{n_2}$$ costs $$O(\log |Q|^2)=O(\log |Q|)$$, so by iterating over all triplets $$(p,q,r)$$, we can compute $$\Delta_{n_1} ; \Delta_{n_2}$$ in $$O(|Q|^3\log |Q|)$$. Since we visit each node once, the total runtime is therefore $$O(|G|\times |Q|^3\log |Q|)$$

If the automaton is deterministic, we can replace the iteration over $$(p,q,r)$$ by an iteration over $$p$$, so we get $$O(|G|\times |Q|\log |Q|)$$

Conclusion

Given a fixed alphabet $$\Sigma$$, and a word $$s\in \Sigma^*$$, we precompute a DAG factorization $$G$$ of $$s$$ with a number of nodes $$|G|=O\left(\frac{|s|}{\sqrt{\log |s|}}\right)$$ Then, given a non-deterministic finite automaton $$\mathcal A=(Q, \Sigma, \Delta, I, F)$$, we check whether $$s$$ is accepted, i.e. whether there exists $$p\in I$$ and $$q\in F$$ such that $$(p,s,q)\in\Delta^*$$, by first computing $$\Delta_n$$ in time $$O(|G|\times |Q|^3\log |Q|)$$ and then checking whether there exists $$p\in I$$ and $$q\in F$$ such that $$(p,q)\in\Delta_n$$ in time $$O(|I|\times |F|\times \log |Q|)$$. Since $$|G|$$ is sublinear in $$|s|$$, we get a total complexity sublinear in $$|s|$$:$$O\left(\frac{|s|}{\sqrt{\log |s|}}\times |Q|^3\log |Q|\right)$$

• What do you mean the induced tree of a DAG? There might be multiple trees. Do you require that all trees that are induced from the graph are tree factorizations?
– D.W.
Jun 22 at 1:56
• @D.W. To get a unique induced tree, a DAG is indeed not enough, but asking for a unique source should make the induced tree unique. I redefined DAG factorization directly to make things clearer. Jun 22 at 11:16
• That's a pretty fun argument, but sorry I'm just missing something. The answer math.stackexchange.com/a/4179041 shows that there is a DAG factorization of the size that you claim, but I'm not sure of how you would actually construct the factorization -- given that as you say testing equality can be costly. Is it obvious how efficiently the DAG factorization can indeed be built? (That said it's true that the question asked for "polynomial-time precomputation" so I guess it's clear you could do it if you don't care about the polynomial degree.)
– a3nm
Jul 4 at 19:20
• @a3nm What I mean by equality testing being costly is that if you test equality of some strings whose length is of the same order of magnitude as $|s|$, then you can't be sublinear, but the precomputation does not need to be sublinear so we can test string equality during the precomputation. To build the DAG for a word of size $2^k$, you can start by building the tree factorization that always splits the word in two subwords of equal size. Then, initialize a union-find structure on the nodes and mark two leaves as equivalent whenever they have the same letter Jul 5 at 13:10
• Then, build a matrix $A$ such that $A[d][j]$ is the equivalence class of the $j^\text{th}$ node at depth $d$. Then, for each $j$ in decreasing order, sort $A[d]$ according to the lexicographical order pairs of the equivalence class of the left child, and the equivalence class of the right child. (This may require adding an integer label to the roots in the union-find structure in some languages, but in others the physical address would do) Then, for each adjacent nodes in $A[d]$, mark them as equivalent in the union-find structure if they have equivalent left and right children. Jul 5 at 13:32