in reply to Re^5: Regexp for range of numbers
in thread Regexp for range of numbers
The structure you have there is actually more like the DFA equvivelent of an A-C matcher. If you remove the default/back links you get a raw trie. Aho-Corasick matching actually uses an array of fail transitions, so you can think of it as the "unfilled in" version of what you have above. This disadvantage of this is that its slightly slower at run time, but the advantage is its a lot faster to construct the array than it is to fill in the trie, it also makes it easier to simulate NFA leftmost-firstoccuring behaviour instead of "first encountered" or "leftmost longest" as you know when you are doing a fail transition and not a success transition.
I might add more later. There are a number of nodes on PM that discuss Trie's in detail, with implementation examples and the like.
|
|---|