Lines Matching refs:transitions

16 * Aho-Corasick as an NFA, using dense transitions near the root with sparse
17   transitions elsewhere.
82 Aho-Corasick can be succinctly described as a trie with state transitions
85 transitions are arranged such that each byte of input needs to be inspected
86 only once. These state transitions are typically called "failure transitions,"
136 The meat of the Aho-Corasick algorithm is in how we add failure transitions to
142 As mentioned before, failure transitions connect a proper suffix of the path
176         // to follow multiple failure transitions before we land on a state
181         // transitions. Every transition from the start state either points to
204 Other than the complication around traversing failure transitions, this code
218 typically accomplished by things called _epsilon_ transitions, where one could
221 a particular state transitions to multiple distinct states.) In contrast, a DFA
222 can only ever be in one state at a time. A DFA has no epsilon transitions, and
223 for any given state, a byte transitions to at most one other state.
226 section is an NFA. This is because failure transitions are, effectively,
227 epsilon transitions. That is, whenever the automaton is in state `S`, it is
229 failure transitions from `S`. (This means that, for example, the start state
230 is always active since the start state is reachable via failure transitions
237 failure transitions for every byte of input. While this is a fairly small
239 overlapping patterns with a lot of failure transitions.
251         // failure transitions to be followed. One byte of input advances the
264 It's done by pre-following all failure transitions for all states for all bytes
309     next_state_id = dfa.transitions[current_state_id * 256 + current_byte]
315     next_state_id = dfa.transitions[current_state_id + current_byte]
374   constructed and how failure transitions are found. Namely, only a subset of
375   the failure transitions are added. Specifically, only the failure transitions
403 automaton to use a subset of all failure transitions, which means that