4
$\begingroup$

I have an array of known patterns with optional wildcards. For example this array that has 5 patterns:

ab*e
hkl
abcd*
ab
sdfs?f

now I need to find the elements within the array that match an arbitrary string.

This can be solved with regular expression by converting the patterns to regexp and looping over the array and returning those that match my string. The problem is that this approach is too slow when my patterns array has thousands of patterns.

I'm looking for some sort of hashing to the known patterns array (could be slow as it only happens once), so that the search of matched patterns to a gives string becomes significantly faster. I checked the Rabin Karp and Aho–Corasick algorithms but they don't work for patterns with wildcards.

In the example above if I'm looking for all matched patterns for abcde I would get

ab*d
abcd*

or the values 0,2 which are the indexes in the patterns array matching my string.

$\endgroup$
  • 3
    $\begingroup$ Please add the details on problem size that you gave in comments in your original SO question. $\endgroup$ – j_random_hacker Nov 3 '16 at 17:42
2
$\begingroup$

Rather than build 5 NFAs (one for each pattern), I suggest you build a single NFA or DFA that represents the parallel composition of all five patterns. Then you can run the string through this automaton and check what state it ends at. That state will tell you which of the 5 patterns it matches.

For best performance, build a NFA for each pattern, take the parallel composition using the product construction, and then convert to a DFA. This should be quite fast.

$\endgroup$
2
$\begingroup$

I suggest choosing some small $k$ (e.g., $k=3$) and breaking up each wildcard-free substring within each pattern into all overlapping $k$-mers: e.g. the pattern abcd*ef?ghij would give you the 3-mers abc, bcd, ghi and hij. Any string that matches abcd*ef?ghij must contain all these 3-mers, so we could pick one of them (say, ghi) at preprocessing time; later, when we have a string that we want to test, we know that we only need to do a "full check" for the pattern abcd*ef?ghij if the string contains the 3-mer ghi. So the idea is to build, at preprocessing time, an index $z[]$ that can, for any given $k$-mer $x$, quickly report all the patterns that we need to run a full check on if $x$ is present anywhere in the string. For speed, this $z[]$ can take the form of a large in-memory array whose index is the $k$-mer, encoded as an integer: this means that, for an alphabet of size $A$, it will have $A^k$ entries, each containing a list of pattern IDs. For speed reasons (see below) you may want to round the alphabet size up to the next power of 2 (so, e.g., if the alphabet is lowercase letters, you could round up to an alphabet size of 32, and comfortably get $k=5$).

Preprocessing

  • For each pattern $p_i$:
    • Choose any wildcard-free $k$-mer $x$ in $p$; the "least likely" $k$-mer is the best choice.
    • Add $i$ to the list $z[x]$.

Main algorithm

  • For each $k$-mer $x$ in the given string $s$:
    • For each $i$ in $z[x]$:
      • Check whether $p_i$ matches $s$ "the hard way".
  • If there are any patterns that have no wildcard-free $k$-mer, test each of them against $s$ "the hard way".

Because each pattern appears at most once anywhere in the index $z[]$, this will never test a pattern twice, so the only overhead over the naive algorithm is the cost of breaking the string into $k$-mers. For alphabets with power-of-2 sizes, this can be done in linear time with bit shifts and bitwise OR operations.

Generally, a higher $k$ is better, but requires exponentially more memory -- and also means that patterns have to have longer wildcard-free substrings in order to benefit from the index. You'll need to experiment.

$\endgroup$

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.