ahocorasick

README

Aho-Corasick

A high-performance, generic Aho-Corasick automaton implementation in Go for efficient multi-pattern matching.

Install

$ go get github.com/smotes/ahocorasick

import (
	ac "github.com/smotes/ahocorasick"
)

Overview

The Aho-Corasick algorithm is a string-searching algorithm that locates all instances of a set of keywords (a dictionary) within an input text in a single pass. Unlike searching for each keyword individually, which takes time proportional to the number of keywords, Aho-Corasick builds a finite-state machine (a trie with failure links).

This allows the algorithm to transition between states as it consumes text, effectively searching for all patterns simultaneously with a complexity of $O(n + m + z)$, where $n$ is the length of the text, $m$ is the total length of all patterns, and $z$ is the number of occurrences found.

Features

• Matching Modes:
  • Overlapping: Finds every occurrence of every pattern, including those nested within others.
  • Leftmost-Longest: Finds the longest non-overlapping matches, prioritizing the earliest start position.
• Safe Concurrency: An Automaton instances is compiled once and immutable afterwards, making it safe for concurrent use across multiple goroutines.
• Zero-Alloc Matching: The match search phase is entirely zero-allocation; memory is only allocated on the heap during the initial compilation of the automaton in New.
• Modern Go:
  • Generics:
    • Works with both byte (for ASCII or raw binary) and rune (for UTF-8 text) character types.
    • Identifier constraint works with a variety of types depending on the dictionary size and performance requirements.
  • Iterators: Go 1.23+ range-over-function iterators for clean and efficient processing of matches.
• Options API:
  • Character Normalization: Built-in support for character normalization (eg: case-insensitivity, accent removal, or character interchangeability) via WithNormalizeFunc.
  • Pattern Filtering: Easily exclude dictionary words based on length constraints using WithMinChars and WithMaxChars.
  • Performance Optimization: Use WithFastByteLookup to enable dense transitions for byte-based automata, trading memory for speed.
  • Encoding Safety:
    • Defaults to validating UTF-8 when using rune characters and no validation when using byte characters.
    • Optional ASCII validation for either character type via WithASCIIValidation.

Basic Usage

The following example demonstrates how to build an automaton and find overlapping matches.

package main

import (
	"fmt"

	ac "github.com/smotes/ahocorasick"
)

func main() {
	// 1. Define your dictionary (ID and content)
	patterns := map[int]string{
		0: "he",
		1: "she",
		2: "his",
		3: "hers",
	}

	// 2. Compile the automaton (using rune characters)
	auto, err := ac.New[rune](func(yield func(int, []byte) bool) {
		for id, word := range patterns {
			if !yield(id, []byte(word)) {
				return
			}
		}
	})
	if err != nil {
		panic(err)
	}

	text := []byte("ushers")

	// 3. Find overlapping matches
	for m, err := range auto.Matches(ac.MatchTypeOverlapping, text) {
		if err != nil {
			panic(err)
		}
		fmt.Printf("Found %q (ID: %d) at [%d:%d]\n", 
            text[m.StartIndex:m.EndIndex], m.WordID, m.StartIndex, m.EndIndex)
	}
	// Output:
	// Found "she" (ID: 1) at [1:4]
	// Found "he" (ID: 0) at [2:4]
	// Found "hers" (ID: 3) at [2:6]
}

For more advanced scenarios, including normalization and leftmost-longest matching, please refer to the examples in the package documentation.

Documentation

Overview

Package ahocorasick implements an Aho-Corasick automaton used to scan through bytes of some encoding to find instances of identifiable words (patterns) within a dictionary.

Index

• type Automaton
  • func New[C Character, ID Identifier](dict iter.Seq2[ID, []byte], opts ...Option[C]) (Automaton[C, ID], error)
  • func (a *Automaton[C, ID]) Matches(typ MatchType, text []byte) iter.Seq2[Match[ID], error]
• type Character
• type EncodingError
  • func (err *EncodingError[C]) Error() string
• type Identifier
• type InvalidMatchTypeError
  • func (err InvalidMatchTypeError) Error() string
• type Match
• type MatchType
• type Option
  • func WithASCIIValidation[C Character]() Option[C]
  • func WithFastByteLookup[C Character]() Option[C]
  • func WithMaxChars[C Character](n int) Option[C]
  • func WithMinChars[C Character](n int) Option[C]
  • func WithNormalizeFunc[C Character](fn func(c C) C) Option[C]

Examples

• Automaton.Matches (LeftmostLongest)
• Automaton.Matches (Overlapping)
• New
• WithNormalizeFunc

Types

type Automaton

type Automaton[C Character, ID Identifier] struct {
	// contains filtered or unexported fields
}

Automaton represents a compiled Aho-Corasick automaton for efficient multi-pattern matching. Create an Automaton via New and use Automaton.Matches to find all occurrences of dictionary words in input text.

The C type parameter specifies the character type for dictionary words, either rune for UTF-8 text or byte for ASCII or raw bytes.

The ID type parameter specifies the identifier type for dictionary words. Note that the identifier type chosen must have sufficient cardinality to fit all words within the dictionary.

func New

func New[C Character, ID Identifier](
	dict iter.Seq2[ID, []byte],
	opts ...Option[C],
) (Automaton[C, ID], error)

New compiles a new automaton from the provided dictionary dict and set of options opts. The dictionary should be an iterator that yields pairs of word identifiers and their corresponding content as UTF-8 bytes.

Returns an error if any of the dictionary words contain invalid UTF-8 bytes. Words may also be silently rejected during insertion if they fall outside the configured minimum or maximum character constraints (see WithMinChars and WithMaxChars).

Example

A basic example of compiling an automaton from an iterator-style dictionary of words.

package main

import (
	"github.com/smotes/ahocorasick"
)

func main() {
	auto, err := ahocorasick.New[rune](func(yield func(int, []byte) bool) {
		dict := []string{"Hello", "World"}
		for id, word := range dict {
			if !yield(id, []byte(word)) {
				return
			}
		}
	})
	if err != nil {
		panic(err)
	}
	_ = auto
}

func (*Automaton[C, ID]) Matches

func (a *Automaton[C, ID]) Matches(typ MatchType, text []byte) iter.Seq2[Match[ID], error]

Matches returns an iterator that yields all matches of dictionary words in the input text according to the specified match type. The iterator may yield an error if the specified match type is invalid or the input text contains an invalid sequence of bytes for the encoding.

Matches may be safely called concurrently across multiple goroutines.

Example (LeftmostLongest)

A basic example of leftmost longest matching.

package main

import (
	"fmt"

	"github.com/smotes/ahocorasick"
)

func main() {
	auto, err := ahocorasick.New[rune](func(yield func(int, []byte) bool) {
		dict := []string{
			"Hello", // id=0
			"World", // id=1
			"He",    // id=2
			"She",   // id=3
		}
		for id, word := range dict {
			if !yield(id, []byte(word)) {
				return
			}
		}
	})
	if err != nil {
		panic(err)
	}
	text := []byte("World Hello")
	for m, err := range auto.Matches(ahocorasick.MatchTypeLeftmostLongest, text) {
		if err != nil {
			panic(err)
		}
		fmt.Printf("m=%+v s=%s\n", m, text[m.StartIndex:m.EndIndex])
	}
}

Output:
m={WordID:1 StartIndex:0 EndIndex:5} s=World
m={WordID:0 StartIndex:6 EndIndex:11} s=Hello

Example (Overlapping)

A basic example of overlapping matching.

package main

import (
	"fmt"

	"github.com/smotes/ahocorasick"
)

func main() {
	auto, err := ahocorasick.New[rune](func(yield func(int, []byte) bool) {
		dict := []string{
			"Hello", // id=0
			"World", // id=1
			"He",    // id=2
			"She",   // id=3
		}
		for id, word := range dict {
			if !yield(id, []byte(word)) {
				return
			}
		}
	})
	if err != nil {
		panic(err)
	}
	text := []byte("World Hello")
	for m, err := range auto.Matches(ahocorasick.MatchTypeOverlapping, text) {
		if err != nil {
			panic(err)
		}
		fmt.Printf("m=%+v s=%s\n", m, text[m.StartIndex:m.EndIndex])
	}
}

Output:
m={WordID:1 StartIndex:0 EndIndex:5} s=World
m={WordID:2 StartIndex:6 EndIndex:8} s=He
m={WordID:0 StartIndex:6 EndIndex:11} s=Hello

type Character

type Character interface {
	byte | rune
}

Character is a character unit used for interpreting data, either a single byte for handling ASCII characters and raw bytes or a rune for handling unicode encoded as a sequence of UTF-8 bytes.

type EncodingError

type EncodingError[C Character] struct {
	Character C
	Index     int
}

EncodingError denotes the input data contains an invalid character given the specified encoding; either invalid ASCII or UTF-8 bytes.

func (*EncodingError[C]) Error

func (err *EncodingError[C]) Error() string

type Identifier

type Identifier interface {
	~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uint | ~uintptr |
		~int8 | ~int16 | ~int32 | ~int64 | ~int | ~string
}

Identifier is a constraint that limits dictionary word identifiers to a subset of comparable types. Booleans, floats, pointers, channels, arrays and structs are excluded to ensure that identifiers have sufficient cardinality and are straightforward to compare by value.

type InvalidMatchTypeError

type InvalidMatchTypeError MatchType

InvalidMatchTypeError specifies the match type specified in [Matches] is an invalid value.

func (InvalidMatchTypeError) Error

func (err InvalidMatchTypeError) Error() string

type Match

type Match[ID Identifier] struct {
	// WordID is the identifier of the matched word.
	WordID ID

	// StartIndex is the index of the first byte of the matched word.
	StartIndex int

	// EndIndex is the index of the first byte after the matched word.
	EndIndex int
}

Match represents a single match of a dictionary word in the input text.

type MatchType

type MatchType int

MatchType specifies the type of matches to return when searching the input text.

const (
	// MatchTypeOverlapping specifies that all matches should be returned,
	// including overlapping ones.
	MatchTypeOverlapping MatchType = iota

	// MatchTypeLeftmostLongest specifies that only the leftmost longest
	// match should be returned.
	MatchTypeLeftmostLongest
)

type Option

type Option[C Character] func(*options[C])

Option is custom optional behaviour for the automaton during the building and/or matching phases.

func WithASCIIValidation

func WithASCIIValidation[C Character]() Option[C]

WithASCIIValidation specifies that all dictionary words and all input text should be validated as ASCII bytes (ie: > 127).

func WithFastByteLookup

func WithFastByteLookup[C Character]() Option[C]

WithFastByteLookup optimizes the underlying trie data structure for faster lookup when using byte characters at the expense of more memory usage.

It achieves this by using a dense transition strategy of fixed-size slices rather than a sparse strategy via maps when constructing the edges of the trie that drives the automaton.

func WithMaxChars

func WithMaxChars[C Character](n int) Option[C]

WithMaxChars specifies the maximum number of characters a dictionary word can have to be included in the automaton. Words longer than this length are silently rejected during insertion.

A value n <= 0 means no configured maximum limit.

This option is applied before a word is inserted into the trie, so excluded words never contribute to automaton state or suffix links.

func WithMinChars

func WithMinChars[C Character](n int) Option[C]

WithMinChars specifies the minimum number of characters a dictionary word must have to be included in the automaton. Words shorter than this length are silently rejected during insertion.

A value n <= 0 means no configured minimum limit other than the implicit minimum of 1 character, since empty words are always rejected.

This option is applied before a word is inserted into the trie, so excluded words never contribute to automaton state or suffix links.

func WithNormalizeFunc

func WithNormalizeFunc[C Character](fn func(c C) C) Option[C]

WithNormalizeFunc specifies a normalization function for all characters during both dictionary word insertion and text matching. It can be used to normalize inconsistencies between dictionary words and/or input text data such as casing (eg: "Hello" vs "hello"), accents (eg: "café" vs "cafe"), or interchangeable characters (eg: ` backtick vs ' apostrophe).

If multiple dictionary words normalize to the same sequence only the word with the latest ID will be retained in the automaton.

Normalization functions cannot be chained together if multiple are specified - the latest will always take precedence.

Note that the normalization function is called on every single character transition in the automaton and so is the hottest path in the entire package if specified. For high-performance use cases, input text and dictionary words should both be pre-normalized and this option should be left off.

Example

An example of a normalization function that casts all characters in the dictionary words and input text to lowercase for case insensitivity and replaces all backticks to apostrophes for handling inconsistencies.

package main

import (
	"fmt"
	"unicode"

	"github.com/smotes/ahocorasick"
)

func main() {
	auto, err := ahocorasick.New(func(yield func(int, []byte) bool) {
		dict := []string{
			"Hello",   // id=0
			"WoRLD",   // id=1
			"aren't",  // id=2
			"they`ll", // id=3
		}
		for id, word := range dict {
			if !yield(id, []byte(word)) {
				return
			}
		}
	}, ahocorasick.WithNormalizeFunc(func(r rune) rune {
		if r == '`' {
			return '\''
		}
		return unicode.ToLower(r)
	}))
	if err != nil {
		panic(err)
	}
	text := []byte("Aren`t HELLO world they'll HellO heLLO")
	for m, err := range auto.Matches(ahocorasick.MatchTypeOverlapping, text) {
		if err != nil {
			panic(err)
		}
		fmt.Printf("m=%+v s=%s\n", m, text[m.StartIndex:m.EndIndex])
	}
}

Output:
m={WordID:2 StartIndex:0 EndIndex:6} s=Aren`t
m={WordID:0 StartIndex:7 EndIndex:12} s=HELLO
m={WordID:1 StartIndex:13 EndIndex:18} s=world
m={WordID:3 StartIndex:19 EndIndex:26} s=they'll
m={WordID:0 StartIndex:27 EndIndex:32} s=HellO
m={WordID:0 StartIndex:33 EndIndex:38} s=heLLO