2
$\begingroup$

What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice?

This has been implemented in 2 libraries I have come across:

But there seem to be very little details of the algorithm available online to understand its working.

$\endgroup$

1 Answer 1

2
$\begingroup$

Reading the source code we can see that it is an extension of Horspool to find a match from a set of needle strings $S$, rather than matching a single needle string.

How it works is by representing the set $S$ as a trie. This allows you to efficiently check character by character whether starting at position $i$ any of the strings on the trie can be found in the haystack. And like in Boyer–Moore–Horspool, if a position $i$ of the haystack fails to match any of the strings in $S$, instead of simply trying $i' = i+1$, a smarter skip lookup table is used: $i' = i + T[\text{haystack}[i + |\text{needle}| - 1]]$.

The second difference is how $T$ is computed. Normally the pseudocode is as follows (from the Wikipedia article):

function preprocess(pattern)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T

But in SetHorspool, the minimum safe skip considering all patterns is computed instead:

function preprocess(S)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← min(length(pattern) : pattern ∈ S)
    for pattern in S
        for i from 0 to length(pattern) - 1 exclusive
            T[pattern[i]] ← min(T[pattern[i]], length(pattern) - 1 - i)
    return T
$\endgroup$
2
  • $\begingroup$ +1. Thanks for the answer. Is it possible to add pseudo-code on how Tire has been generated and the smart skip table if it is not inconvenient? $\endgroup$ Dec 2, 2020 at 16:30
  • $\begingroup$ @SumindaSirinathS.Dharmasena The smart skip table is already in the post, the rest is simply standard tries and Horspool. $\endgroup$
    – orlp
    Dec 2, 2020 at 16:32

Your Answer

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

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