I'm looking for an algorithm that will help me determine substring matches at scale.

I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage is cheap.

On detection side, I have both a very large pool (hundreds of TB) of strings to search for needles in, and also want to be able to stream detection as text comes in. So it's important that the detection be very fast (algorithmically). I can also pre-process this text as part of the detection, obviously.

I can store a copy of all needles, so a probabilistic algorithm would be fine (say, instead of the correct N strings, the algorithm returns some false positives -- I can always do a plain string search afterwards).

There is significant structure to the strings (they happen to be source code -- snippets on the needle side and files in the haystack).

Appreciate any thoughts on where to explore.

  • What algorithms have you looked at so far? What's the range of typical lengths of the needles? – D.W. Feb 21 '17 at 3:17
  • Typical length of needles is less than 500 characters. Thoughts on approaches (not algorithms per se) were: DBMS "LIKE" query, DBMS full text search, pre-processing and then using straight 'grep'. I didn't see a way of getting the performance where I want it, hence I'm exploring here. I suppose LCS would work, but the complexity seems like it wouldn't work for this scale. On the other hand, the streaming case is similar to a search engine, so an inverted index might be the way to go. I also took a look at some of the code-search tools, but performance wasn't very good there either. – Scovetta Feb 21 '17 at 3:35
  • What's the average longest common prefix between the needles? – KWillets Feb 21 '17 at 4:50
  • Not sure about average, but the needles could be tokenized, with each token either coming from a set of size perhaps 300. They aren't at all random, so exploiting the structure would be very reasonable. – Scovetta Feb 21 '17 at 4:56
  • The average LCP between consecutive strings in a sorted list is a measure of how many characters need to be compared to get a unique match -- in your case you need at least log2(100M) = ~27 bits, but I'm guessing it's much more. – KWillets Feb 21 '17 at 6:32
up vote 2 down vote accepted

Rabin-Karp

Rabin-Karp string search would be a good candidate, because it can use a rolling hash function.

You pick a segment length $\ell$. For each "needle", you hash its first $\ell$ characters, and store it in a hashtable keyed on the hash.

Then, as each character of text arrives, you compute the rolling hash of the last $\ell$ characters, look it up in the hash table, and possibly find one or more candidate needles that might match; then you test them directly.

This requires that the segment length be shorter than the shortest needle, but long enough to make hash collisions rare (i.e., so that the first $\ell$ characters of a needle mostly uniquely determines the needle). If you have a wide range of needle lengths, I suppose you could pick two segment lengths $\ell_1,\ell_2$, have two hash tables, and store each needle in appropriate hashtable according to its length.

Aho-Corasick

The Aho-Corasick algorithm would also be a good candidate. It solves exactly this problem, and doesn't require any assumptions on the lengths of the needles.

You might also look at Commentz-Walter.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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