Debian Codegraph @

.cargo/vendor/aho-corasick/src/nfa/mod.rs

raw
1 /*!
2 Provides direct access to NFA implementations of Aho-Corasick.
3
4 The principle characteristic of an NFA in this crate is that it may
5 transition through multiple states per byte of haystack. In Aho-Corasick
6 parlance, NFAs follow failure transitions during a search. In contrast,
7 a [`DFA`](crate::dfa::DFA) pre-computes all failure transitions during
8 compilation at the expense of a much bigger memory footprint.
9
10 Currently, there are two NFA implementations provided: noncontiguous and
11 contiguous. The names reflect their internal representation, and consequently,
12 the trade offs associated with them:
13
14 * A [`noncontiguous::NFA`] uses a separate allocation for every NFA state to
15 represent its transitions in a sparse format. This is ideal for building an
16 NFA, since it cheaply permits different states to have a different number of
17 transitions. A noncontiguous NFA is where the main Aho-Corasick construction
18 algorithm is implemented. All other Aho-Corasick implementations are built by
19 first constructing a noncontiguous NFA.
20 * A [`contiguous::NFA`] is uses a single allocation to represent all states,
21 while still encoding most states as sparse states but permitting states near
22 the starting state to have a dense representation. The dense representation
23 uses more memory, but permits computing transitions during a search more
24 quickly. By only making the most active states dense (the states near the
25 starting state), a contiguous NFA better balances memory usage with search
26 speed. The single contiguous allocation also uses less overhead per state and
27 enables compression tricks where most states only use 8 bytes of heap memory.
28
29 When given the choice between these two, you almost always want to pick a
30 contiguous NFA. It takes only a little longer to build, but both its memory
31 usage and search speed are typically much better than a noncontiguous NFA. A
32 noncontiguous NFA is useful when prioritizing build times, or when there are
33 so many patterns that a contiguous NFA could not be built. (Currently, because
34 of both memory and search speed improvements, a contiguous NFA has a smaller
35 internal limit on the total number of NFA states it can represent. But you
36 would likely need to have hundreds of thousands or even millions of patterns
37 before you hit this limit.)
38 */
39 pub mod contiguous;
40 pub mod noncontiguous;