2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What algorithms have you looked at so far? What's the range of typical lengths of the needles? $\endgroup$
    – D.W. ♦
    Commented Feb 21, 2017 at 3:17
  • $\begingroup$ 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. $\endgroup$
    – Scovetta
    Commented Feb 21, 2017 at 3:35
  • $\begingroup$ What's the average longest common prefix between the needles? $\endgroup$
    – KWillets
    Commented Feb 21, 2017 at 4:50
  • $\begingroup$ 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. $\endgroup$
    – Scovetta
    Commented Feb 21, 2017 at 4:56
  • $\begingroup$ 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. $\endgroup$
    – KWillets
    Commented Feb 21, 2017 at 6:32

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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