aho-corasick

Aho-Corasick is a multiple substring matching algorithm used to find occurrences of many patterns within a single haystack. Unlike naive searching, which checks every pattern at every position, Aho-Corasick visits each byte in the haystack exactly once, making its performance largely independent of the number of patterns (though larger automata may impact CPU cache efficiency).

At its core, the algorithm uses a trie augmented with failure transitions.

• Trie: A tree structure representing the patterns.
• Failure Transitions: When a byte in the haystack does not match a transition in the current state, the algorithm follows a failure transition to a state representing the longest proper suffix of the current path that is also a prefix of another pattern. This allows the search to continue without restarting from the beginning of the haystack.

This implementation supports several variants, including:

• NFA (Noncontiguous/Contiguous): Different memory layouts for state transitions.
• DFA: A dense transition table using a single allocation.
• Match Semantics: Standard, overlapping, leftmost-first, and leftmost-longest.
• Accelerations: ASCII case insensitivity, SIMD-vectorized search (Teddy algorithm), and fixed-byte/rare-byte acceleration via memchr.

By default, Aho-Corasick may report matches as soon as they are seen, which can lead to unexpected results when patterns overlap (e.g., matching Sam instead of Samwise in the text Samwise).

To achieve regex-like behavior, use AhoCorasick::builder() and set the .match_kind() method:

• MatchKind::LeftmostFirst: Matches the leftmost occurrence, and among those, the one that starts earliest (similar to Perl-like regex engines).
• MatchKind::LeftmostLongest: Matches the leftmost occurrence, and among those, the longest one (similar to POSIX regex behavior).

Example of LeftmostFirst matching:

use aho_corasick::{AhoCorasick, MatchKind};

let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";

let ac = AhoCorasick::builder()
    .match_kind(MatchKind::LeftmostFirst)
    .build(patterns)
    .unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);

Match semantics define how the automaton disambiguates multiple possible matches. You can select these via the MatchKind type.

• standard: Emits matches as soon as they are detected. This is the textbook non-overlapping formulation.
• leftmost-first:
  1. Finds the match starting at the leftmost position.
  2. If multiple matches start at the same position, it reports the one corresponding to the pattern provided first by the caller (allowing for match priority).
• leftmost-longest:
  1. Finds the match starting at the leftmost position.
  2. If multiple matches start at the same position, it reports the longest match (useful for dictionary word matching).

Note on Overlapping Matches: If you require overlapping matches (reporting all possible matches even when they intersect), you must use standard match semantics. Attempting an overlapping search with leftmost-first or leftmost-longest will result in an error or panic because those modes use a subset of failure transitions that prevent overlapping detection.

Teddy achieves high throughput by using bitwise operations and SIMD instructions to perform 'packed' substring matching. The high-level process is:

1. Fingerprinting: For each pattern, a fingerprint is computed (this implementation uses the first $N$ bytes of each substring).
2. Bitset Mapping: A map is created where each fingerprint (or its nybble components) maps to a bitfield representing the patterns that contain it.
3. SIMD Lookup: The haystack is scanned in 16 or 32-byte chunks. The algorithm uses the PSHUFB instruction to perform a parallel lookup. It splits each byte of the haystack into two nybbles (lower 4 bits and upper 4 bits) and uses them to index into two precomputed bitset masks (A0 for lower nybbles, A1 for upper nybbles).
4. Result Combination: The results from the lower and upper nybble lookups are combined using an AND operation to produce a bitset C. If any bit in C is set, it indicates a potential match at that position.
5. Verification: The position of the least significant bit in C identifies the pattern and the offset within the chunk. A verification step is then performed to confirm the actual match.

Teddy is a SIMD-accelerated multiple substring matching algorithm. It optimizes performance by scanning large chunks (16 or 32 bytes) at a time using fingerprints.

Key implementation details include:

• Fingerprint Length (N): The algorithm uses a prefix of length $N \in {1, 2, 3}$ bytes. It automatically selects the largest possible $N$ to minimize the number of verification steps. Larger fingerprints reduce false positives but increase the work required per step.
• Verification: When a fingerprint match is detected via SIMD bitsets, the algorithm performs a verification step. It extracts 64-bit integers from the SIMD vectors, identifies the least significant bit to derive the byte offset and bucket, and then performs an exhaustive search for literals within that bucket.
• SIMD Scaling: The algorithm scales from SSE (128-bit) to AVX (256-bit). While AVX allows for 32-byte chunks, certain alignment operations (like PALIGNR in SSE) require specific shuffling workarounds in AVX because VPALIGNR only operates within 128-bit lanes.