Crate daachorse 

🐎 daachorse: Double-Array Aho-Corasick

A fast implementation of the Aho-Corasick algorithm using the compact double-array data structure.

Overview

Daachorse (pronounced “dark horse”) is a crate for fast multiple pattern matching using the Aho-Corasick algorithm, running in linear time over the length of the input text. This crate uses the compact double-array data structure for implementing the pattern match automaton for time and memory efficiency. The data structure not only supports constant-time state-to-state traversal but also represents each state using only 12 bytes of memory.

In addition, a match-candidate prefilter based on 2-grams is enabled by default. It lets the slice-based search methods quickly skip sections of the haystack that contain no occurrence of any pattern, accelerating matching on pattern sets where it is likely to pay off, in exchange for 64KiB of additional heap memory and serialized size. The prefilter never changes match results. You can disable it with DoubleArrayAhoCorasickBuilder::use_prefilter() or CharwiseDoubleArrayAhoCorasickBuilder::use_prefilter().

The main technical ideas behind this library appear in the following paper:

Shunsuke Kanda, Koichi Akabe, and Yusuke Oda. Engineering faster double-array Aho-Corasick automata. Software: Practice and Experience (SPE), 53(6): 1332–1361, 2023 (arXiv)

Example: Finding overlapping occurrences

To search for all occurrences of registered patterns that allow for positional overlap in the input text, use DoubleArrayAhoCorasick::find_overlapping_iter().

When you use DoubleArrayAhoCorasick::new() for construction, the library assigns a unique identifier to each pattern in the input order. The match result has the byte positions of the occurrence and its identifier.

use daachorse::DoubleArrayAhoCorasick;

let patterns = vec!["bcd", "ab", "a"];
let pma = DoubleArrayAhoCorasick::new(patterns).unwrap();

let mut it = pma.find_overlapping_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 1, 2), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((0, 2, 1), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

Example: Finding non-overlapping occurrences with standard matching

To disallow positional overlap, use DoubleArrayAhoCorasick::find_iter() instead.

This function performs the search on the Aho-Corasick automaton and reports the first matching pattern at each search position.

use daachorse::DoubleArrayAhoCorasick;

let patterns = vec!["bcd", "ab", "a"];
let pma = DoubleArrayAhoCorasick::new(patterns).unwrap();

let mut it = pma.find_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 1, 2), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

Example: Finding non-overlapping occurrences with longest matching

To search for the longest pattern without positional overlap in each iteration, specify MatchKind::LeftmostLongest during construction and use DoubleArrayAhoCorasick::leftmost_find_iter().

use daachorse::{DoubleArrayAhoCorasickBuilder, MatchKind};

let patterns = vec!["ab", "a", "abcd"];
let pma = DoubleArrayAhoCorasickBuilder::new()
    .match_kind(MatchKind::LeftmostLongest)
    .build(&patterns)
    .unwrap();

let mut it = pma.leftmost_find_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 4, 2), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

Example: Finding non-overlapping occurrences with leftmost-first matching

To search for the earliest registered pattern among those starting from the search position, specify MatchKind::LeftmostFirst during construction and use DoubleArrayAhoCorasick::leftmost_find_iter().

This semantics is the so-called leftmost first match, a tricky search option supported in the aho-corasick crate. For example, in the following code, ab is reported because it is the earliest registered one.

use daachorse::{DoubleArrayAhoCorasickBuilder, MatchKind};

let patterns = vec!["ab", "a", "abcd"];
let pma = DoubleArrayAhoCorasickBuilder::new()
    .match_kind(MatchKind::LeftmostFirst)
    .build(&patterns)
    .unwrap();

let mut it = pma.leftmost_find_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 2, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

Example: Associating arbitrary values with patterns

To build the automaton from pattern-value pairs, instead of assigning identifiers automatically, use DoubleArrayAhoCorasick::with_values().

use daachorse::DoubleArrayAhoCorasick;

let patvals = vec![("bcd", 0), ("ab", 10), ("a", 20)];
let pma = DoubleArrayAhoCorasick::with_values(patvals).unwrap();

let mut it = pma.find_overlapping_iter("abcd");

let m = it.next().unwrap();
assert_eq!((0, 1, 20), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((0, 2, 10), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

Example: Building faster automaton on multibyte characters

To build a faster automaton on multibyte characters, use CharwiseDoubleArrayAhoCorasick instead.

The standard version DoubleArrayAhoCorasick handles strings as UTF-8 sequences and defines transition labels using byte values. In contrast, CharwiseDoubleArrayAhoCorasick uses Unicode code point values, reducing the number of transitions and enabling faster matching on multibyte characters.

use daachorse::CharwiseDoubleArrayAhoCorasick;

let patterns = vec!["全世界", "世界", "に"];
let pma = CharwiseDoubleArrayAhoCorasick::new(patterns).unwrap();

let mut it = pma.find_iter("全世界中に");

let m = it.next().unwrap();
assert_eq!((0, 9, 0), (m.start(), m.end(), m.value()));

let m = it.next().unwrap();
assert_eq!((12, 15, 2), (m.start(), m.end(), m.value()));

assert_eq!(None, it.next());

Profile-Guided Optimization (PGO)

The double array constructed by daachorse is designed to improve CPU cache efficiency. However, it is not always the optimal layout for every document being scanned.

daachorse addresses this issue by supporting Profile-Guided Optimization (PGO). By providing a corpus when constructing the automaton, the memory layout is optimized, which may improve performance on documents similar to the given corpus.

use daachorse::{DoubleArrayAhoCorasick, DoubleArrayAhoCorasickBuilder};

let patterns = vec!["bcd", "ab", "a"];
let pma: DoubleArrayAhoCorasick<u32> = DoubleArrayAhoCorasickBuilder::new()
    .corpus(["abcd"])
    .build(patterns)
    .unwrap();

Re-exports

pub use crate::bytewise::DoubleArrayAhoCorasick;

pub use crate::bytewise::DoubleArrayAhoCorasickBuilder;

pub use crate::charwise::CharwiseDoubleArrayAhoCorasick;

pub use crate::charwise::CharwiseDoubleArrayAhoCorasickBuilder;

pub use crate::errors::Result;

Modules

bytewise

A byte-wise version of the Double-Array Aho-Corasick.

charwise

A character-wise version for faster matching on multibyte characters.

errors

Definition of errors.

Structs

Empty

Empty value type.

Match

Match result.

Enums

MatchKind

A search option of the Aho-Corasick automaton specified in DoubleArrayAhoCorasickBuilder::match_kind.

Traits

Serializable

Trait indicating serializability.