# 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? – xavierm02 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 – xavierm02 Jun 13 at 11:14

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 yesterday
• @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 yesterday

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.