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