3 ms·

There's a related linear-time algorithm for checking a string against a list of targets for possible substring matches: Aho–Corasick algorithm [0] It's used by

There's a related linear-time algorithm for checking a string against a list of targets for possible substring matches: Aho–Corasick algorithm [0] It's used by standard implementations of grep when matching against fixed strings (e.g. "grep -F" or "fgrep"). 0: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

MattPalmer1086 4y ago
You don't really need the full Aho Corasick algorithm to determine set membership of a string. A simple Trie structure made of the set of strings would suffice.
- pimlottc 4y ago
  No, and it doesn't work for exactly this situation anyway, since you only want complete string matches here (e.g. "paws" shouldn't match), but I thought it was an interesting related problem.
  - recursive 4y ago
    As soon as you encounter the 'p', you fall out of the trie, and it's a miss.
    - pimlottc 4y ago
      Sorry, I was talking about Aho-Corasick
- jeffrallen 4y ago
  There's no way the cache thrashing of walking a trie would cost less than the integer compares the author used.
  - yakubin 4y ago
    Not just cache, but also the branch mispredictions while walking a trie.
  - scotty79 4y ago
    Since the trie is static it could be pregenerated and held in small static array that might fit in a cache line ... I think. I don't really know this stuff. But still probably would be slower especially if there aren't many misses that could be quickly rejected by the trie.
  - MattPalmer1086 4y ago
    Yes, for a small set of strings, which is the problem he is solving, you are almost certainly right.
kazinator 4y ago
I wonder what, if any, is the advantage of this algorithm compared to forming a regex disjunction of the strings and compiling to DFA.
- morelisp 4y ago
  They do totally different things. A regex will tell you if the haystack contained any needle (and if you want, give you one specific one which depends on the engine/compilation). AC tells you all needles the haystack contained.
- burntsushi 4y ago
  The reply you already got is kind of correct, but only in the sense of what is typically exposed at an API level. Most Aho-Corasick implementations have a way to provide all possible matches, even overlapping ones. Yet, most regex engines do not provide any way to return all possible matches. However, FSM-based regex engines can do that, if they want to, using largely the same structure as Aho-Corasick: keep a list of matching patterns for each match state. With that said, this would require treating each literal pattern as a distinct regex instead of doing 'pat0|pat1|..|patN'. But this is mostly just API stuff. Putting that aside, what I suspect to be the most essential difference is the construction algorithm itself. Building an Aho-Corasick NFA (or even DFA) is done in worst case linear time. But building a DFA through powerset construction takes worst case exponential time. Whether I'm actually right about that or not depends on whether the worst case bound for powerset construction remains as such when you know your input is just an alternation of literals. But certainly, if you take a general regex construction implementation and feed it a bunch of literals, the Aho-Corasick implementation is almost certainly going to come out on top. The former is more general and has more infrastructure that costs time and space.

MattPalmer1086 4y ago

You don't really need the full Aho Corasick algorithm to determine set membership of a string. A simple Trie structure made of the set of strings would suffice.

pimlottc 4y ago
No, and it doesn't work for exactly this situation anyway, since you only want complete string matches here (e.g. "paws" shouldn't match), but I thought it was an interesting related problem.
- recursive 4y ago
  As soon as you encounter the 'p', you fall out of the trie, and it's a miss.
  - pimlottc 4y ago
    Sorry, I was talking about Aho-Corasick
jeffrallen 4y ago
There's no way the cache thrashing of walking a trie would cost less than the integer compares the author used.
- yakubin 4y ago
  Not just cache, but also the branch mispredictions while walking a trie.
- scotty79 4y ago
  Since the trie is static it could be pregenerated and held in small static array that might fit in a cache line ... I think. I don't really know this stuff. But still probably would be slower especially if there aren't many misses that could be quickly rejected by the trie.
- MattPalmer1086 4y ago
  Yes, for a small set of strings, which is the problem he is solving, you are almost certainly right.

kazinator 4y ago

I wonder what, if any, is the advantage of this algorithm compared to forming a regex disjunction of the strings and compiling to DFA.

morelisp 4y ago
They do totally different things. A regex will tell you if the haystack contained any needle (and if you want, give you one specific one which depends on the engine/compilation). AC tells you all needles the haystack contained.
burntsushi 4y ago
The reply you already got is kind of correct, but only in the sense of what is typically exposed at an API level. Most Aho-Corasick implementations have a way to provide all possible matches, even overlapping ones. Yet, most regex engines do not provide any way to return all possible matches. However, FSM-based regex engines can do that, if they want to, using largely the same structure as Aho-Corasick: keep a list of matching patterns for each match state. With that said, this would require treating each literal pattern as a distinct regex instead of doing 'pat0|pat1|..|patN'. But this is mostly just API stuff. Putting that aside, what I suspect to be the most essential difference is the construction algorithm itself. Building an Aho-Corasick NFA (or even DFA) is done in worst case linear time. But building a DFA through powerset construction takes worst case exponential time. Whether I'm actually right about that or not depends on whether the worst case bound for powerset construction remains as such when you know your input is just an alternation of literals. But certainly, if you take a general regex construction implementation and feed it a bunch of literals, the Aho-Corasick implementation is almost certainly going to come out on top. The former is more general and has more infrastructure that costs time and space.