daachorse

Daachorse is a fast implementation of the Aho-Corasick algorithm using a compact double-array data structure. It is optimized for time and memory efficiency, representing each state using only 12 bytes. It requires Rust 1.77 or higher.

To use it in your Rust project, add it to your Cargo.toml dependencies. It supports no_std environments provided a global allocator is available via the alloc crate.

# Add to Cargo.toml
daachorse = "5.0.0"

A CharwiseDoubleArrayAhoCorasick is a fast multiple pattern match automaton that uses Unicode code point values instead of raw UTF-8 bytes for transitions.

When to use it

Use this version when matching against multibyte characters (such as CJK characters) to achieve faster matching speeds.

Trade-offs compared to standard DoubleArrayAhoCorasick

• Matching Speed: Generally faster for multibyte characters.
• Construction Time: May be slower.
• Memory Usage:
  • For large scales, memory efficiency is competitive.
  • For small scales, the double array can be sparse and memory-inefficient.

A PrefilterGate acts as a runtime safeguard. It monitors the efficiency of the prefilter during actual scanning. If the prefilter fails to skip enough bytes (i.e., it's not providing a significant speedup), the gate automatically disables prefiltering for the current iterator to fall back to plain automaton scanning.

How it works:

• It tracks performance in windows of GATE_WINDOW_CALLS (64 calls).
• If the total bytes skipped (gain_in_window) in a window is less than GATE_MIN_WINDOW_GAIN (512 bytes), the gate sets enabled to false.
• Once disabled, it stays disabled for the remainder of that iterator's lifecycle.

Serialization in daachorse is designed to be efficient and safe.

1. Primitives: All integer primitives are serialized using little-endian byte order.
2. Options: Option<T> is serialized by writing a u8 flag (0 for None, 1 for Some) followed by the serialized value of T if it exists. Option<NonZeroU32> is optimized to use only 4 bytes (the u32 value itself, where 0 represents None).
3. Vectors: Vec<S> is serialized by writing the length as a u32 followed by the elements. During deserialization, the library validates that the requested number of elements can actually fit within the provided byte slice to prevent malicious memory exhaustion attacks.
4. Empty Types: The Empty type is a zero-cost abstraction that occupies 0 bytes when serialized and consumes no data during deserialization.

To create a Prefilter, use the PrefilterBuilder. This is an incremental builder that allows you to register patterns without keeping the entire pattern set in memory.

Steps:

1. Initialize a new builder with PrefilterBuilder::new().
2. Add patterns using .add(&[u8]).
3. Call .build() to attempt to create the filter.

Note on .build() failure: The builder returns None if:

• No patterns were added.
• Any pattern is shorter than Prefilter::MIN_WINDOW_LEN (2 bytes).
• The resulting filter table is too dense (the estimated candidate rate exceeds MAX_EXPECTED_CANDIDATE_RATE), meaning prefiltering would likely be slower than standard scanning.

let mut builder = PrefilterBuilder::new();
builder.add(b"pattern1");
builder.add(b"pattern2");

if let Some(prefilter) = builder.build() {
    // Use the prefilter
}

The standard DoubleArrayAhoCorasick treats strings as UTF-8 byte sequences. For better performance and efficiency when matching multibyte characters (like Unicode), use CharwiseDoubleArrayAhoCorasick. This version uses Unicode code point values for transitions, which reduces the number of transitions and enables faster matching on non-ASCII text.

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!((m.start(), m.end(), m.value()), (0, 9, 0));

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

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

To search for the earliest registered pattern among those starting from the search position, configure the automaton with MatchKind::LeftmostFirst using the DoubleArrayAhoCorasickBuilder and use leftmost_find_iter(). This is useful when multiple patterns start at the same position and you want the one that was added to the automaton first.

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!((m.start(), m.end(), m.value()), (0, 2, 0));

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

To search for the longest pattern without positional overlap in each iteration, configure the automaton with MatchKind::LeftmostLongest using the DoubleArrayAhoCorasickBuilder and use 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!((m.start(), m.end(), m.value()), (0, 4, 2));

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