5 ms·
You can't do Aho-Corasick or any form of tree/trie structure (practically) without using pointers, and any form of pointer-chasing algorithm is going to have a
by trentnelson 8y ago
You can't do Aho-Corasick or any form of tree/trie structure (practically) without using pointers, and any form of pointer-chasing algorithm is going to have a tough time competing with the lower bounds of this algorithm, when we're dealing with 6 to 13 CPU cycles.
This data structure is specifically optimized for small sets of short strings. If we were dealing with larger data sets we wanted to match against, then a comparison against other contemporary techniques would be warranted.
- voidmain 8y agoYes, I agree, the article's approach will definitely win for small tables. But readers of this article may want to solve the same problem on big tables, so should be aware that there's an asymptotically faster solution. (Actually, I think you could probably use the article's approach in combination with DFA techniques to build something that's both fast and scalable. Something like a finite state automaton doing something like what's in the article at each node. But I don't need this and am not going to invest in trying to figure it out or learn whether there is prior art.)