2
$\begingroup$

Let's say we have millions of strings (each of them < 100 characters):

alpha
allo
blah
hello world
orlando
...

I know how a binary search tree or a trie can help to do "prefix search" (example: find all strings that match al*, i.e. beginning with al).

Which data structure / algorithm could be used to search patterns inside a word (i.e. not necessarily at the beginning or end), that wouldn't need to do an inefficient O(n) traversal of all the millions of strings?

Example: the pattern orl should match "hello world" as well as "orlando"

Notes:

  • is that called "infix search"?

  • I'm looking for something working on strings even without meaning (the pattern qys should allow to find the string uyiuqysidi among millions of other strings), on DNA (pattern ATTG found in GGATCATTGAAGG), on sequences (subsequence 1, 4, 8 found in sequence 7, 2, 1, 4, 8, 19, 32), etc.

Improve this question
$\endgroup$
2
$\begingroup$

Let $\$$ be a symbol not in the alphabet, and let $\{ w_i \}_{i \in \mathbb{N}}$ be the strings you are searching from. Construct the string $S = w_1 \circ \$ \circ w_2 \circ \$ \circ \dots \circ w_n$ and use Ukkonen's algorithm to construct a suffix tree for $S$. You are now able to retrieve all $m$ occurrences of a pattern $P$ in time $\Theta(m + |P|)$, with $\sum_i|w_i|$ preprocessing time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your helpful answer. To make it even easier to understand, do you think you could add an example of suffix tree for alpha$allo$blah$hello world$orlando to show how it would work to find for orl? $\endgroup$ – Basj Apr 20 '18 at 15:05
  • $\begingroup$ The wikipedia page already has an example, with a different string. $\endgroup$ – quicksort Apr 20 '18 at 15:28
0
$\begingroup$

Depending on the characteristics of the strings, it might be useful to separate the strings to be searched into equivalence classes in some way. For example, generate a bitmap of characters contained somewhere in the string, so each string in the searchable set would get a 26 bit classification. The actual search would only search strings with matching classifications.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Could you add an example? I know what are equivalence classes in math, but how would you define it in this context? Thank you in advance if you can elaborate a bit on the bitmap of characters contained in the string, it looks promosing! I guess alpha would be 10000001000100010000000000? Do you mean you would pre-filter the strings which have the necessary characters first (using bitmap), and then perform a 2nd search (which kind of 2nd search?) $\endgroup$ – Basj Apr 20 '18 at 19:33
  • $\begingroup$ PS: this wouldn't work for DNA sequence, because the bitmap for nearly every string would be 1111 because A, T, G, C will be nearly always present. Also we can't do a bitmap for sequences (x1, x2, x3, ...) with x_i potentially a very large integer (let's say x_i goes up to 2 billions). $\endgroup$ – Basj Apr 20 '18 at 19:36
  • $\begingroup$ as i said; depending on the characteristics of the strings. If the target is DNA sequences, the coding might be based on short sequences that are contained. Some creativity and intelligent experimentation are called for. $\endgroup$ – ddyer Apr 20 '18 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.