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.