AhoCorasickAutomaton<TValue> Class

Definition

Namespace

Bodu.Collections.Generic.Trees

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

AhoCorasickAutomaton{T}.cs

Represents an immutable Aho-Corasick automaton that locates every occurrence of every pattern in a keyed pattern set in a single pass over the searched text, reporting the value associated with each matched pattern.

public sealed class AhoCorasickAutomaton<TValue>

Type Parameters

TValue

The type of the value associated with each pattern.

Inheritance

object

AhoCorasickAutomaton<TValue>

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<KeyValuePair<string, TValue>>) 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 the unkeyed variant, see AhoCorasickAutomaton.

Properties

Patterns

Gets the patterns the automaton searches for, in the order they were supplied.

public IReadOnlyCollection<string> Patterns { get; }

Property Value

IReadOnlyCollection<string>

A read-only collection of the patterns.

Methods

Build(IEnumerable<KeyValuePair<string, TValue>>)

Builds an automaton that searches for every pattern key in the specified set, associating each with its value.

public static AhoCorasickAutomaton<TValue> Build(IEnumerable<KeyValuePair<string, TValue>> patterns)

Parameters

patterns IEnumerable<KeyValuePair<string, TValue>>

The pattern/value pairs to search for.

Returns

AhoCorasickAutomaton<TValue>

An immutable automaton over the pattern set.

Remarks

Unlike the unkeyed Build(IEnumerable<string>), a duplicate pattern key throws rather than deduplicating, because two entries would compete for the key's value - mirroring the Trie<TValue> versus Trie add contracts.

Exceptions

ArgumentNullException

patterns is null.

ArgumentException

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

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, carrying each pattern's associated value.

public IEnumerable<AhoCorasickMatch<TValue>> EnumerateMatches(string text)

Parameters

text string

The text to scan.

Returns

IEnumerable<AhoCorasickMatch<TValue>>

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