package aho-corasick

  1. Overview
  2. Docs
On This Page
  1. Searching
Aho-Corasick multi-pattern string matching

Install 

dune-project
 Dependency

ville.dev Readme Changelog Edit opam file Versions (1)

Authors

  1. V
    Ville Vesilehto <ville@vesilehto.fi>

Maintainers

  1. V
    Ville Vesilehto <ville@vesilehto.fi>

Sources

v0.1.1.tar.gz
md5=f1d1c262b14a9ab81e6933c5cb62b545
sha512=369d9b7fe1cd2c4af1eb20739f357ed1259f05590b53c7b3e77da9138bd50155ce966a1a2a521c70c598092c4d7d788c02bc6cce97a65eda69985d2d4a132952

doc/aho-corasick/Aho_corasick/index.html

Module Aho_corasickSource

Aho–Corasick multi-pattern string matching.

Build an automaton from a set of patterns once, then find every occurrence of every pattern in an input with a single left-to-right pass. Search takes O(input length + matches examined); overlapping searches also allocate their reported matches.

Matching is byte-oriented and 8-bit clean: patterns and inputs are arbitrary strings (UTF-8 works as byte matching; ?ignore_case folds ASCII letters only).

Reference: Aho & Corasick, "Efficient string matching: an aid to bibliographic search", CACM 18(6), 1975.

Sourcetype t

A compiled automaton. Immutable and safe to share across threads.

Sourcetype match_ = {
  1. pattern : int;
    (*

    Index of the pattern in the list given to build.

    *)
  2. start : int;
    (*

    Byte offset of the first matched byte.

    *)
  3. stop : int;
    (*

    Byte offset one past the last matched byte.

    *)
}
Sourceval build : ?ignore_case:bool -> string list -> t

build patterns compiles the automaton. Duplicate patterns are allowed (each occurrence reports every duplicate's index). With ~ignore_case:true, ASCII letters match case-insensitively. An empty pattern list yields an automaton that matches nothing.

Raises Invalid_argument if any pattern is the empty string.

Sourceval pattern_count : t -> int

Number of patterns, including duplicates.

Sourceval pattern : t -> int -> string

The original pattern for a match_'s pattern index.

Raises Invalid_argument if the index is out of bounds.

Searching

Sourceval find_all : t -> string -> match_ list

Every match of every pattern, including overlapping ones. Ordered by stop; matches ending at the same position come longest first, then by ascending pattern index for equal lengths.

Sourceval find_iter : t -> string -> match_ Seq.t

Like find_all, but lazily — stop consuming to stop scanning.

Sourceval find_leftmost_longest : t -> string -> match_ list

Non-overlapping matches, chosen greedily: repeatedly take the match with the smallest start (breaking ties by greatest length), then discard everything overlapping it. Equal-length ties use the lowest pattern index. Selection is a single pass and retains at most one candidate per start within the longest-pattern window.

Sourceval mem : t -> string -> bool

Does any pattern occur? Scans only as far as the first match.

Sourceval replace_all : t -> f:(match_ -> string) -> string -> string

Replace each find_leftmost_longest match m with f m.

Sourcemodule Stream : sig ... end