AhoCorasick

AhoCorasick module: multi-pattern string search (pure March implementation).

Finds every occurrence of ANY of a set of fixed string patterns inside a haystack in a single pass, in O(haystack_len + total_pattern_len) time — independent of how many patterns there are. The naive alternative, N calls to String.index_of-style scanning (one per pattern), costs O(N * haystack_len). This is the classic Aho-Corasick automaton: a trie over the patterns, BFS-computed failure links (the "what state do I fall back to on a mismatch" edges), and output sets merged along the failure chain so a match of a shorter suffix pattern is reported even when the trie path actually walked belongs to a longer pattern (e.g. patterns "he" and "she" both match inside "ushers" — "she" is the trie path walked, but "he" is a suffix of it and must also be reported).

Two-phase use, matching the "compile once, scan many times" shape that makes the automaton worth building in the first place:

let ac = AhoCorasick.build(["he", "she", "his", "hers"])
AhoCorasick.find_all(ac, "ushers")
-- [{start: 1, stop: 4, pattern_index: 1, pattern: "she"},
--  {start: 2, stop: 4, pattern_index: 0, pattern: "he"}]

Matches are returned in the order their END position is reached scanning left to right; matches sharing an end position are ordered longest-pattern- first (the pattern whose trie path was actually walked, then its suffixes via the failure chain, shortest last).

Byte-oriented throughout (like Regex and Json): string_byte_at / string_byte_length, no per-byte allocation. Since string_chars and friends operate on raw bytes rather than decoded Unicode codepoints, this is safe for UTF-8 input too — multibyte continuation bytes are always >= 0x80 and match only themselves.

An empty pattern (zero bytes) is skipped during build: it would match at every position with zero width, which is not useful for a "find these literal substrings" search and would need special-casing throughout. It is simply excluded from the automaton — no error, no match ever produced for it.

Types

ptypeAcNodeAcNode = AcNode(List((Int, Int)), Int, List(Int))#

ptypeAutomatonAutomaton = Automaton(Array(AcNode), Array(String))#

typeMatchMatch = { start : Int, stop : Int, pattern_index : Int, pattern : String }#

Functions

fnbuildbuild(patterns : List(String)) : Automaton#

Build an automaton matching any of patterns in a single linear pass over a haystack. Building costs O(total pattern length); scanning with the result costs O(haystack length), independent of the number of patterns — build once, scan as many haystacks as you like with find_all / matches / find_first.

Patterns are referenced by their position in `patterns` (`pattern_index`
on a `Match`). An empty pattern string is skipped (see module doc).

    let ac = AhoCorasick.build(["he", "she", "his", "hers"])
    AhoCorasick.matches(ac, "ushers")  -- true

fnfind_allfind_all(automaton : Automaton, haystack : String) : List(Match)#

Find every match of any pattern in haystack, in one linear pass. Matches can overlap, and a shorter pattern that is a suffix of a longer matched pattern is reported separately (see module doc's "he"/"she" example).

    let ac = AhoCorasick.build(["he", "she"])
    AhoCorasick.find_all(ac, "ushers")
    -- [{start: 1, stop: 4, pattern_index: 1, pattern: "she"},
    --  {start: 2, stop: 4, pattern_index: 0, pattern: "he"}]

fnfind_firstfind_first(automaton : Automaton, haystack : String) : Option(Match)#

Find the first match (by end position, longest pattern first) of any pattern in haystack, without building the full match list.

    let ac = AhoCorasick.build(["he", "she"])
    AhoCorasick.find_first(ac, "ushers")  -- Some({start: 1, stop: 4, ...})
    AhoCorasick.find_first(ac, "xyz")     -- None

fnmatchesmatches(automaton : Automaton, haystack : String) : Bool#

Whether any pattern matches anywhere in haystack.

    let ac = AhoCorasick.build(["needle"])
    AhoCorasick.matches(ac, "a needle in a haystack")  -- true
    AhoCorasick.matches(ac, "nothing here")             -- false

fnpattern_atpattern_at(automaton : Automaton, index : Int) : Option(String)#

The pattern text at index (its position in the list passed to build), or None if out of range.

    let ac = AhoCorasick.build(["he", "she"])
    AhoCorasick.pattern_at(ac, 1)   -- Some("she")
    AhoCorasick.pattern_at(ac, 99)  -- None

fnpattern_countpattern_count(automaton : Automaton) : Int#

The number of patterns automaton was built from (including any empty ones, which are stored but never match — see module doc).

    AhoCorasick.pattern_count(AhoCorasick.build(["a", "b", "c"]))  -- 3