817 Advanced

Aho-Corasick Multi-Pattern Search

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Aho-Corasick Multi-Pattern Search" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. When you need to find hundreds of keywords simultaneously in a large text — network intrusion detection scanning for attack signatures, spam filters checking for banned phrases, DNA analysis searching for multiple probes — running each pattern separately costs O(n * k) where k is the number of patterns. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

When you need to find hundreds of keywords simultaneously in a large text — network intrusion detection scanning for attack signatures, spam filters checking for banned phrases, DNA analysis searching for multiple probes — running each pattern separately costs O(n * k) where k is the number of patterns. Aho-Corasick solves this by building a trie of all patterns and adding failure links so that mismatches fall back to the longest suffix that is also a prefix of some pattern. The result is O(n + m + z) where n is text length, m is total pattern length, and z is match count — regardless of how many patterns there are. This is the algorithm powering fgrep -f patterns.txt, network packet inspection, and antivirus scanning.

🎯 Learning Outcomes

• Build a trie (prefix tree) from a set of patterns with nodes tracking pattern completions

• Compute failure links via BFS, connecting mismatch states to the longest proper suffix-prefix

• Understand why BFS is necessary for failure link computation (level-by-level guarantees parent links exist)

• Implement the search phase that follows failure links on mismatch rather than restarting

• Recognize output links that allow reporting multiple overlapping patterns ending at the same position

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Aho-Corasick Multi-Pattern Matching — O(Σ|patterns| + n + matches) *)

let alpha = 256

type node = {
  children : int array;
  mutable fail : int;
  mutable output : int list;  (* pattern indices ending at this node *)
}

let make_node () = { children = Array.make alpha (-1); fail = 0; output = [] }

let build_automaton patterns =
  let nodes = ref [| make_node () |] in  (* root at index 0 *)

  (* Insert all patterns into trie *)
  List.iteri (fun pid pat ->
    let cur = ref 0 in
    String.iter (fun c ->
      let ci = Char.code c in
      if !nodes.(!cur).children.(ci) = -1 then begin
        !nodes.(!cur).children.(ci) <- Array.length !nodes;
        nodes := Array.append !nodes [| make_node () |]
      end;
      cur := !nodes.(!cur).children.(ci)
    ) pat;
    !nodes.(!cur).output <- pid :: !nodes.(!cur).output
  ) patterns;

  (* BFS to compute failure links *)
  let q = Queue.create () in
  for c = 0 to alpha - 1 do
    let ch = !nodes.(0).children.(c) in
    if ch = -1 then !nodes.(0).children.(c) <- 0
    else begin !nodes.(ch).fail <- 0; Queue.push ch q end
  done;
  while not (Queue.is_empty q) do
    let u = Queue.pop q in
    !nodes.(u).output <- !nodes.(u).output @
                         !nodes.(!nodes.(u).fail).output;
    for c = 0 to alpha - 1 do
      let v = !nodes.(u).children.(c) in
      if v = -1 then
        !nodes.(u).children.(c) <- !nodes.(!nodes.(u).fail).children.(c)
      else begin
        !nodes.(v).fail <- !nodes.(!nodes.(u).fail).children.(c);
        Queue.push v q
      end
    done
  done;
  !nodes

let search_ac nodes text patterns =
  let state   = ref 0 in
  let matches = ref [] in
  String.iteri (fun i c ->
    let ci = Char.code c in
    state := nodes.(!state).children.(ci);
    List.iter (fun pid ->
      let pat = List.nth patterns pid in
      matches := (i - String.length pat + 1, pid) :: !matches
    ) nodes.(!state).output
  ) text;
  List.rev !matches

let () =
  let patterns = ["he"; "she"; "his"; "hers"] in
  let text     = "ushers" in
  let nodes    = build_automaton patterns in
  let matches  = search_ac nodes text patterns in
  Printf.printf "Text: %S\n" text;
  Printf.printf "Patterns: [%s]\n" (String.concat "; " patterns);
  List.iter (fun (pos, pid) ->
    Printf.printf "  Found %S at position %d\n" (List.nth patterns pid) pos
  ) matches

Key Differences

Aspect	Rust	OCaml
Goto table	`Vec<HashMap<char, usize>>`	`int array` or `Hashtbl` per node
Failure links	`Vec<usize>` indexed by state	`int array` or `int ref` per node
BFS queue	`std::collections::VecDeque`	`Queue.t` from standard library
Output links	`Vec<Vec<String>>`	`string list ref` per node
Unicode support	HashMap handles any char	Depends on implementation
Memory layout	Cache-friendly Vec storage	GC-managed node heap

OCaml Approach

OCaml represents the Aho-Corasick automaton using arrays of int option for goto transitions or Hashtbl per node. Failure links are mutable int ref values set during BFS using a Queue. The output at each node is a string list ref grown by appending output-linked completions. OCaml's polymorphic variants can express node states cleanly. The Buffer module builds the goto structure, and Array.make creates fixed-size transition arrays for ASCII alphabets. The search function is naturally tail-recursive with the current state threaded through.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Aho-Corasick Multi-Pattern Matching — O(Σ|patterns| + n + matches) *)

let alpha = 256

type node = {
  children : int array;
  mutable fail : int;
  mutable output : int list;  (* pattern indices ending at this node *)
}

let make_node () = { children = Array.make alpha (-1); fail = 0; output = [] }

let build_automaton patterns =
  let nodes = ref [| make_node () |] in  (* root at index 0 *)

  (* Insert all patterns into trie *)
  List.iteri (fun pid pat ->
    let cur = ref 0 in
    String.iter (fun c ->
      let ci = Char.code c in
      if !nodes.(!cur).children.(ci) = -1 then begin
        !nodes.(!cur).children.(ci) <- Array.length !nodes;
        nodes := Array.append !nodes [| make_node () |]
      end;
      cur := !nodes.(!cur).children.(ci)
    ) pat;
    !nodes.(!cur).output <- pid :: !nodes.(!cur).output
  ) patterns;

  (* BFS to compute failure links *)
  let q = Queue.create () in
  for c = 0 to alpha - 1 do
    let ch = !nodes.(0).children.(c) in
    if ch = -1 then !nodes.(0).children.(c) <- 0
    else begin !nodes.(ch).fail <- 0; Queue.push ch q end
  done;
  while not (Queue.is_empty q) do
    let u = Queue.pop q in
    !nodes.(u).output <- !nodes.(u).output @
                         !nodes.(!nodes.(u).fail).output;
    for c = 0 to alpha - 1 do
      let v = !nodes.(u).children.(c) in
      if v = -1 then
        !nodes.(u).children.(c) <- !nodes.(!nodes.(u).fail).children.(c)
      else begin
        !nodes.(v).fail <- !nodes.(!nodes.(u).fail).children.(c);
        Queue.push v q
      end
    done
  done;
  !nodes

let search_ac nodes text patterns =
  let state   = ref 0 in
  let matches = ref [] in
  String.iteri (fun i c ->
    let ci = Char.code c in
    state := nodes.(!state).children.(ci);
    List.iter (fun pid ->
      let pat = List.nth patterns pid in
      matches := (i - String.length pat + 1, pid) :: !matches
    ) nodes.(!state).output
  ) text;
  List.rev !matches

let () =
  let patterns = ["he"; "she"; "his"; "hers"] in
  let text     = "ushers" in
  let nodes    = build_automaton patterns in
  let matches  = search_ac nodes text patterns in
  Printf.printf "Text: %S\n" text;
  Printf.printf "Patterns: [%s]\n" (String.concat "; " patterns);
  List.iter (fun (pos, pid) ->
    Printf.printf "  Found %S at position %d\n" (List.nth patterns pid) pos
  ) matches

Deep Comparison

OCaml vs Rust: Aho Corasick Multi

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Add support for case-insensitive matching by lowercasing during trie construction.

Implement output links to efficiently report all patterns ending at each position, not just direct matches.

Measure the speedup over k separate Boyer-Moore searches for k=10, 100, 1000 patterns.

Serialize the compiled automaton to disk and reload it without rebuilding from patterns.

Extend to report overlapping matches where one pattern is a substring of another.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust