Sublinear Time Regular Expression Search

Question

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?

Answer 1

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|$.

Answer 2

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.

Answer 3

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)$$