AhoCorasickAutomaton Class

Definition

Namespace

Bodu.Collections.Generic.Trees

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

AhoCorasickAutomaton.cs

Represents an immutable Aho-Corasick automaton that locates every occurrence of every pattern in a pattern set in a single pass over the searched text.

public sealed class AhoCorasickAutomaton

Inheritance

object

AhoCorasickAutomaton

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Remarks

The automaton is built once from a complete pattern set via Build(IEnumerable<string>) and is immutable thereafter: its failure and output links are global invariants defined relative to the whole pattern set, so a pattern added later would invalidate the links wholesale - rebuild with the new set instead. Matching costs O(n + m) for text length n and m reported matches, independent of the number of patterns.

Character comparison is ordinal. Matches - including overlapping and nested occurrences - are reported in a deterministic order: ascending end index, then ascending pattern length. Because a lazily evaluated sequence cannot capture a ReadOnlySpan<T>, the lazy EnumerateMatches(string) takes a string, while the eager CountMatches(ReadOnlySpan<char>) and HasMatch(ReadOnlySpan<char>) conveniences accept spans. For a value-carrying variant, see AhoCorasickAutomaton<TValue>.

Properties

Patterns

Gets the distinct patterns the automaton searches for, in first-seen order.

public IReadOnlyCollection<string> Patterns { get; }

Property Value

IReadOnlyCollection<string>

A read-only collection of the deduplicated patterns.

Methods

Build(IEnumerable<string>)

Builds an automaton that searches for every pattern in the specified set.

public static AhoCorasickAutomaton Build(IEnumerable<string> patterns)

Parameters

patterns IEnumerable<string>

The patterns to search for. Duplicate patterns are deduplicated.

Returns

AhoCorasickAutomaton

An immutable automaton over the deduplicated pattern set.

Remarks

An empty pattern is rejected because it would match at every text position and carries no information. Repeated patterns are stored once; Patterns reports each distinct pattern a single time.

Exceptions

ArgumentNullException

patterns is null.

ArgumentException

patterns is empty, contains a null pattern, or contains an empty pattern.

ContainsPattern(string)

Determines whether the automaton was built with the specified pattern.

public bool ContainsPattern(string pattern)

Parameters

pattern string

The pattern to locate.

Returns

bool

true if the pattern is in the set; otherwise, false.

Exceptions

ArgumentNullException

pattern is null.

CountMatches(ReadOnlySpan<char>)

Counts every occurrence of every pattern in the specified text.

public int CountMatches(ReadOnlySpan<char> text)

Parameters

text ReadOnlySpan<char>

The text to scan.

Returns

int

The total number of matches, overlapping and nested occurrences included.

Remarks

This is the eager span-friendly companion of EnumerateMatches(string); it reports the same number of matches without materializing them.

EnumerateMatches(string)

Returns every occurrence of every pattern in the specified text.

public IEnumerable<AhoCorasickMatch> EnumerateMatches(string text)

Parameters

text string

The text to scan.

Returns

IEnumerable<AhoCorasickMatch>

A lazily evaluated sequence of matches - overlapping and nested occurrences included - ordered ascending by end index, then ascending by pattern length.

Exceptions

ArgumentNullException

text is null.

HasMatch(ReadOnlySpan<char>)

Determines whether any pattern occurs in the specified text.

public bool HasMatch(ReadOnlySpan<char> text)

Parameters

text ReadOnlySpan<char>

The text to scan.

Returns

bool

true if at least one pattern occurs; otherwise, false.

Remarks

The scan exits at the first hit, so a match near the start of the text returns immediately.

Applies to

Product	Versions
.NET	8, 10