ahocorasick

README

ahocorasick

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

Features

• Up to 7 GB/s throughput — DFA compilation with SIMD-accelerated prefilter
• Flat transition table — fully compiled DFA with premultiplied state IDs
• SIMD prefilter — bytes.IndexByte skip-ahead for non-matching regions
• 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 and Find hot paths allocate nothing

Installation

go get github.com/coregx/ahocorasick

Requires Go 1.25+

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 (zero allocation)
    if m, found := ac.Find(haystack, 0); found {
        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-7 patterns):

Method	Throughput	Allocations
IsMatch (with match)	7.0 GB/s	0
IsMatch (no match)	5.9 GB/s	0
Find	7.0 GB/s	0
FindAll (77B input)	100 MB/s	4

How it achieves this

1. DFA compilation — all failure transitions pre-computed at build time into a flat []uint32 array. Search is a single table lookup per byte: trans[sid + class].
2. SIMD prefilter — before running the DFA, bytes.IndexByte (SSE2/AVX2 on amd64) scans for pattern start bytes. Skips entire regions where no match is possible.
3. Skip-ahead on start state — when the DFA returns to its start state during search, the prefilter re-engages to jump ahead, avoiding byte-by-byte scanning of non-matching text.
4. Match flag embedding — the high bit of each transition entry flags match states, enabling single-instruction match detection with no separate lookup.

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 (Find and FindAt are zero allocation)
ac.Find(haystack []byte, start int) (Match, bool)      // First match from position
ac.FindAt(haystack []byte, start int) (Match, bool)    // 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)

Architecture

Builder.Build()
  -> NFA construction (trie + failure links)
  -> DFA compilation (flat transition table, premultiplied state IDs)
  -> Prefilter setup (start byte collection for SIMD scanning)

Search: IsMatch / Find / FindAll
  -> SIMD prefilter (bytes.IndexByte skip-ahead)
  -> DFA traversal (trans[sid + class], one operation per byte)
  -> Match flag check (raw & matchFlag, one AND per byte)

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

Articles

• Aho-Corasick in Go: Multi-Pattern String Matching at 6 GB/s with Zero Allocations — Deep dive into the DFA compilation, SIMD prefilter, and optimization techniques

Related Projects

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

Star History

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, bool)
  • 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, bool)
  • 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 DFA
  • func (d *DFA) MemoryUsage() int
• type Match
  • func (m Match) Len() int
• type MatchKind
• type OptimizedNFA
• type PatternID
• type StateID

Constants

const Version = "0.3.1"

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 a fully compiled DFA with premultiplied state IDs for maximum throughput.

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, bool)

Find returns the first match in haystack starting at or after position start. Uses the flagged transition table for inline match detection. Prefilter: skips ahead using bytes.IndexByte when no start byte is nearby.

Zero allocations — the Match is returned by value.

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. Uses an inline DFA loop to avoid per-match heap allocations.

func (*Automaton) FindAllOverlapping

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

FindAllOverlapping returns all overlapping matches in the haystack.

func (*Automaton) FindAt

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

FindAt returns the first match starting exactly at position start.

Zero allocations — the Match is returned by value.

func (*Automaton) IsMatch

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

IsMatch returns true if any pattern matches anywhere in the haystack. This is the most optimized search path — zero allocations, minimal branching.

Uses a two-level prefilter strategy:

1. Skip-ahead: use SIMD bytes.IndexByte to jump directly to positions where a match could start, skipping all non-pattern bytes in bulk.
2. DFA scan: run the automaton from the skip position to verify the match.

If the automaton returns to start state during scanning, it re-engages the prefilter to skip ahead again. This is the same strategy as BurntSushi's Rust implementation.

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.

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 DFA

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

DFA represents a fully compiled deterministic finite automaton.

Key properties:

• All failure transitions are pre-computed into the transition table
• Single flat []uint32 array for all transitions (cache-friendly)
• Premultiplied state IDs: sid = stateIndex << stride2
• Match flag embedded in high bit of each transition value
• Match check in IsMatch: bitmap[stateIndex/64] & (1 << (stateIndex%64))
• Lookup: trans[sid + byteClass] — one addition, one load per byte

func (*DFA) MemoryUsage

func (d *DFA) MemoryUsage() int

MemoryUsage returns the approximate heap memory used by this DFA in bytes.

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.