ahocorasick

README

ahocorasick

High-performance Aho-Corasick multi-pattern string matching for Go.

Features

• 1+ GB/s throughput — comparable to Rust's aho-corasick
• Dense array transitions — optimized NFA with O(1) state transitions
• Byte class compression — reduces memory by grouping equivalent bytes
• Multiple match semantics — LeftmostFirst (Perl) and LeftmostLongest (POSIX)
• Zero dependencies — pure Go, no cgo
• Zero allocations — IsMatch() hot path allocates nothing

Installation

go get github.com/coregx/ahocorasick

Requires Go 1.21+

Quick Start

package main

import (
    "fmt"
    "github.com/coregx/ahocorasick"
)

func main() {
    // Build automaton from patterns
    ac, _ := ahocorasick.NewBuilder().
        AddStrings([]string{"error", "warning", "fatal"}).
        Build()

    haystack := []byte("[error] something failed")

    // Check if any pattern matches (zero allocation)
    if ac.IsMatch(haystack) {
        fmt.Println("Found a match!")
    }

    // Find first match
    if m := ac.Find(haystack, 0); m != nil {
        fmt.Printf("Found %q at position %d\n",
            haystack[m.Start:m.End], m.Start)
    }

    // Find all non-overlapping matches
    for _, m := range ac.FindAll(haystack, -1) {
        fmt.Printf("Pattern %d: %q\n", m.PatternID, haystack[m.Start:m.End])
    }
}

Performance

Benchmarks on Intel i7-1255U (64KB haystack, 4 patterns):

Method	Throughput	Allocations
IsMatch (with match)	1.6 GB/s	0
Find	1.1 GB/s	1
IsMatch (no match)	780 MB/s	0

Comparable to Rust's aho-corasick crate (~1-2 GB/s).

API

Builder

ahocorasick.NewBuilder().
    AddStrings([]string{"foo", "bar"}).  // Add patterns
    SetMatchKind(ahocorasick.LeftmostLongest).  // Optional: POSIX semantics
    Build()  // Returns (*Automaton, error)

Automaton

// Existence check (zero allocation)
ac.IsMatch(haystack []byte) bool

// Find matches
ac.Find(haystack []byte, start int) *Match      // First match from position
ac.FindAt(haystack []byte, start int) *Match    // Match at exact position
ac.FindAll(haystack []byte, n int) []Match      // All non-overlapping (n=-1 for all)
ac.FindAllOverlapping(haystack []byte) []Match  // All including overlaps

// Utilities
ac.Count(haystack []byte) int   // Count non-overlapping matches
ac.PatternCount() int           // Number of patterns
ac.Pattern(id int) []byte       // Get pattern by ID

Match Semantics

LeftmostFirst   // First pattern in list wins (Perl-compatible, default)
LeftmostLongest // Longest pattern wins (POSIX-compatible)

Use Cases

• Log analysis — scan for error patterns in log files
• Content filtering — detect keywords in text
• Network security — signature-based detection
• DNA sequencing — find multiple motifs simultaneously
• Regex acceleration — as prefilter for foo|bar|baz alternations

How It Works

The Aho-Corasick algorithm builds a finite automaton from patterns:

1. Trie construction — patterns form a prefix tree
2. Failure links — enable backtracking without re-reading input
3. Dense transitions — O(1) state lookup via byte class indexing

This allows matching all patterns simultaneously in O(n) time regardless of pattern count.

Related Projects

• coregex — High-performance regex engine (uses this library)
• BurntSushi/aho-corasick — Rust reference implementation

License

MIT License — see LICENSE for details.

Documentation

Overview

Package ahocorasick implements the Aho-Corasick algorithm for efficient multi-pattern string matching.

The Aho-Corasick algorithm allows searching for multiple patterns simultaneously in O(n + m + z) time, where n is the input length, m is the total pattern length, and z is the number of matches.

This package is under active development. See README for status.

Index

• Constants
• type Automaton
  • func (a *Automaton) Count(haystack []byte) int
  • func (a *Automaton) Find(haystack []byte, start int) *Match
  • func (a *Automaton) FindAll(haystack []byte, n int) []Match
  • func (a *Automaton) FindAllOverlapping(haystack []byte) []Match
  • func (a *Automaton) FindAt(haystack []byte, start int) *Match
  • func (a *Automaton) IsMatch(haystack []byte) bool
  • func (a *Automaton) MatchKind() MatchKind
  • func (a *Automaton) Pattern(id int) []byte
  • func (a *Automaton) PatternCount() int
  • func (a *Automaton) StateCount() int
• type Builder
  • func NewBuilder() *Builder
  • func (b *Builder) AddPattern(pattern []byte) *Builder
  • func (b *Builder) AddPatterns(patterns [][]byte) *Builder
  • func (b *Builder) AddStrings(patterns []string) *Builder
  • func (b *Builder) Build() (*Automaton, error)
  • func (b *Builder) SetASCII(ascii bool) *Builder
  • func (b *Builder) SetByteClasses(enabled bool) *Builder
  • func (b *Builder) SetMatchKind(kind MatchKind) *Builder
  • func (b *Builder) SetPrefilter(prefilter bool) *Builder
• type ByteClasses
  • func NewByteClasses(patterns [][]byte) *ByteClasses
  • func NewSingletonByteClasses() *ByteClasses
  • func (bc *ByteClasses) AlphabetSize() int
  • func (bc *ByteClasses) Get(b byte) int
  • func (bc *ByteClasses) IsSingleton() bool
  • func (bc *ByteClasses) NumClasses() int
• type Match
  • func (m Match) Len() int
• type MatchKind
• type OptimizedNFA
• type PatternID
• type StateID

Constants

const Version = "0.1.0-dev"

Version is the current library version.

Types

type Automaton

type Automaton struct {
	// contains filtered or unexported fields
}

Automaton is the compiled Aho-Corasick multi-pattern matcher. Uses optimized dense array transitions for high performance.

func (*Automaton) Count

func (a *Automaton) Count(haystack []byte) int

Count returns the number of non-overlapping matches in the haystack.

func (*Automaton) Find

func (a *Automaton) Find(haystack []byte, start int) *Match

Find returns the first match in haystack starting at or after position start. Returns nil if no match is found.

func (*Automaton) FindAll

func (a *Automaton) FindAll(haystack []byte, n int) []Match

FindAll returns all non-overlapping matches in the haystack. If n >= 0, at most n matches are returned.

func (*Automaton) FindAllOverlapping

func (a *Automaton) FindAllOverlapping(haystack []byte) []Match

FindAllOverlapping returns all overlapping matches in the haystack. This may return multiple matches at the same position.

func (*Automaton) FindAt

func (a *Automaton) FindAt(haystack []byte, start int) *Match

FindAt returns the first match starting exactly at position start. This is useful for anchored matching. Returns nil if no match starts at the given position.

func (*Automaton) IsMatch

func (a *Automaton) IsMatch(haystack []byte) bool

IsMatch returns true if any pattern matches anywhere in the haystack. Optimized: inlined nextState for maximum performance.

func (*Automaton) MatchKind

func (a *Automaton) MatchKind() MatchKind

MatchKind returns the match semantics used by this automaton.

func (*Automaton) Pattern

func (a *Automaton) Pattern(id int) []byte

Pattern returns the pattern bytes at the given index.

func (*Automaton) PatternCount

func (a *Automaton) PatternCount() int

PatternCount returns the number of patterns in the automaton.

func (*Automaton) StateCount

func (a *Automaton) StateCount() int

StateCount returns the number of states in the underlying automaton. This is useful for debugging and performance analysis.

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder configures and builds an Aho-Corasick automaton.

func NewBuilder

func NewBuilder() *Builder

NewBuilder creates a new Builder with default configuration. Default: LeftmostFirst semantics, byte classes enabled.

func (*Builder) AddPattern

func (b *Builder) AddPattern(pattern []byte) *Builder

AddPattern adds a single pattern to the automaton.

func (*Builder) AddPatterns

func (b *Builder) AddPatterns(patterns [][]byte) *Builder

AddPatterns adds multiple patterns to the automaton.

func (*Builder) AddStrings

func (b *Builder) AddStrings(patterns []string) *Builder

AddStrings adds multiple string patterns to the automaton.

func (*Builder) Build

func (b *Builder) Build() (*Automaton, error)

Build constructs the Aho-Corasick automaton from the configured patterns. Returns an error if no patterns were added or if construction fails. Uses optimized dense array transitions for high performance (1+ GB/s).

func (*Builder) SetASCII

func (b *Builder) SetASCII(ascii bool) *Builder

SetASCII enables ASCII-only optimization. When true, patterns are assumed to contain only ASCII bytes.

func (*Builder) SetByteClasses

func (b *Builder) SetByteClasses(enabled bool) *Builder

SetByteClasses enables or disables byte class compression. When enabled, reduces memory usage by grouping equivalent bytes.

func (*Builder) SetMatchKind

func (b *Builder) SetMatchKind(kind MatchKind) *Builder

SetMatchKind sets the match semantics. Default is LeftmostFirst (Perl-compatible).

func (*Builder) SetPrefilter

func (b *Builder) SetPrefilter(prefilter bool) *Builder

SetPrefilter enables or disables prefilter optimization. When enabled, a prefilter may be used to accelerate search.

type ByteClasses

type ByteClasses struct {
	// contains filtered or unexported fields
}

ByteClasses compresses the 256-byte alphabet into equivalence classes. Bytes that always transition to the same states can share a class. This reduces memory usage and improves cache utilization.

func NewByteClasses

func NewByteClasses(patterns [][]byte) *ByteClasses

NewByteClasses creates ByteClasses from a set of patterns. It computes the minimal set of equivalence classes.

func NewSingletonByteClasses

func NewSingletonByteClasses() *ByteClasses

NewSingletonByteClasses creates ByteClasses where each byte is its own class. This is the identity mapping (no compression).

func (*ByteClasses) AlphabetSize

func (bc *ByteClasses) AlphabetSize() int

AlphabetSize returns the number of equivalence classes. This is the effective alphabet size for the automaton.

func (*ByteClasses) Get

func (bc *ByteClasses) Get(b byte) int

Get returns the equivalence class for the given byte.

func (*ByteClasses) IsSingleton

func (bc *ByteClasses) IsSingleton() bool

IsSingleton returns true if every byte is its own class.

func (*ByteClasses) NumClasses

func (bc *ByteClasses) NumClasses() int

NumClasses returns the number of equivalence classes.

type Match

type Match struct {
	// PatternID is the index of the pattern that matched.
	PatternID int

	// Start is the byte offset of the start of the match.
	Start int

	// End is the byte offset of the end of the match (exclusive).
	End int
}

Match represents a match found in the haystack.

func (Match) Len

func (m Match) Len() int

Len returns the length of the match in bytes.

type MatchKind

type MatchKind int

MatchKind specifies the semantics of matching.

const (
	// LeftmostFirst implements leftmost-first semantics.
	// When multiple patterns can match at the same position,
	// the pattern that appears first in the pattern list wins.
	// This is Perl-compatible behavior and matches Go's regexp package.
	LeftmostFirst MatchKind = iota

	// LeftmostLongest implements leftmost-longest semantics.
	// When multiple patterns can match at the same position,
	// the longest pattern wins. This is POSIX-compatible behavior.
	LeftmostLongest
)

type OptimizedNFA

type OptimizedNFA struct {
	// contains filtered or unexported fields
}

OptimizedNFA represents an optimized Aho-Corasick automaton. Key optimizations: 1. Dense transitions: []StateID instead of map[byte]StateID 2. Precomputed root transitions: no failure link following for root 3. ByteClasses: reduced alphabet size

type PatternID

type PatternID uint32

PatternID is an identifier for a pattern in the automaton.

type StateID

type StateID uint32

StateID is an identifier for a state in the automaton.