ahocorasick

README

ahocorasick

The fastest Golang implementation of the Aho-Corasick algorithm for string-searching.

Usage

go get github.com/AlexanderZh/ahocorasick@v0.1.8

Documentation

m := CompileByteSlices([][]byte{
  []byte("he"),
  []byte("she"),
  []byte("his"),
  []byte("hers"),
  []byte("she"),
})
m.FindAllByteSlice([]byte("ushers")) // => { "she" 1 }, { "he" 2 }, { "hers" 2 }

m := CompileStrings([]string{
  "he",
  "she",
  "his",
  "hers",
  "she",
)
m.FindAllString("ushers") // => { "she" 1 }, { "he" 2 }, { "hers" 2 }

Benchmarks

macOS Mojave version 10.14.6

MacBook Pro (Retina, 13-inch, Early 2015)

Processor 3.1 GHz Intel Core i7

$ git co d7354e5e7912add9c2c602aae74c508bca3b2f4d; go test -bench=Benchmark

The two basic operations are the compilation of the state machine from an array of patterns (Compile), and the usage of this state machine to find each pattern in text (FindAll). Other implementations call these operations under different names.

Operation	Input Size	rrethy/ahocorasick	BobuSumisu/aho-corasick	anknown/ahocorasick
-	-	Double-Array Trie	LinkedList Trie	Double-Array Trie
-	-	-	-	-
Compile	235886 patterns	133 ms	214 ms	1408 ms
Compile	23589 patterns	20 ms	50 ms	137 ms
Compile	2359 patterns	3320 µs	11026 µs	10506 µs
Compile	236 patterns	229 µs	1377 µs	867s µs
Compile	24 patterns	43 µs	144 µs	82s µs
-	-	-	-	-
FindAll	3227439 bytes	36 ms	38 ms	116 ms
FindAll	318647 bytes	3641 µs	3764 µs	11335 µs
FindAll	31626 bytes	359 µs	370 µs	1103 µs
FindAll	3657 bytes	31 µs	40 µs	131 µs

NOTE: FindAll uses a state machine compiled from 2359 patterns.

NOTE: FindAll time does not include the Compile time for the state machine.

Reference Papers

[1] A. V. Aho, M. J. Corasick, "Efficient String Matching: An Aid to Bibliographic Search," Communications of the ACM, vol. 18, no. 6, pp. 333-340, June 1975.

[2] J.I. Aoe, "An Efficient Digital Search Algorithm by Using a Doble-Array Structure," IEEE Transactions on Software Engineering, vol. 15, no. 9, pp. 1066-1077, September 1989.

[3] J.I. Aoe, K. Morimoto, T. Sato, "An Efficient Implementation of Trie Stuctures," Software - Practice and Experience, vol. 22, no.9, pp. 695-721, September 1992.

License

MIT

Documentation

Overview

Package ahocorasick implements the Aho-Corasick string matching algorithm for efficiently finding all instances of multiple patterns in a text.

Index

• type DeserializeError
  • func (m *DeserializeError) Error() string
• type Match
• type Matcher
  • func CompileByteSlices(words [][]byte) *Matcher
  • func CompileStrings(words []string) *Matcher
  • func Deserialize(data []byte) (m *Matcher, err error)
  • func (m *Matcher) FindAllByteReader(reader io.Reader, matches Matches)
  • func (m *Matcher) FindAllByteSlice(text []byte) (matches []*Match)
  • func (m *Matcher) FindAllString(text string) []*Match
  • func (m *Matcher) Serialize() []byte
  • func (m *Matcher) String() string
• type Matches
• type SWord

Types

type DeserializeError

type DeserializeError struct{}

func (*DeserializeError) Error

func (m *DeserializeError) Error() string

type Match

type Match struct {
	Word  []byte // the matched pattern
	Index int    // the start index of the match
}

Match represents a matched pattern in the text

type Matcher

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

Matcher is the pattern matching state machine.

func CompileByteSlices

func CompileByteSlices(words [][]byte) *Matcher

CompileByteSlices compiles a Matcher from a slice of byte slices. This Matcher can be used to find occurrences of each pattern in a text.

func CompileStrings

func CompileStrings(words []string) *Matcher

CompileStrings compiles a Matcher from a slice of strings. This Matcher can be used to find occurrences of each pattern in a text.

func Deserialize

func Deserialize(data []byte) (m *Matcher, err error)

func (*Matcher) FindAllByteReader

func (m *Matcher) FindAllByteReader(reader io.Reader, matches Matches)

func (*Matcher) FindAllByteSlice

func (m *Matcher) FindAllByteSlice(text []byte) (matches []*Match)

FindAllByteSlice finds all instances of the patterns in the text.

func (*Matcher) FindAllString

func (m *Matcher) FindAllString(text string) []*Match

FindAllString finds all instances of the patterns in the text.

func (*Matcher) Serialize

func (m *Matcher) Serialize() []byte

added function for byte serialization of compiled matcher

func (*Matcher) String

func (m *Matcher) String() string

type Matches

type Matches interface {
	Append(key int, position int)
	Count() int
}

type SWord

type SWord struct {
	Len uint64
	Key uint64
}