Struct DoubleArrayAhoCorasick 

pub struct DoubleArrayAhoCorasick<V> { /* private fields */ }

A fast multiple pattern match automaton implemented with the Aho-Corasick algorithm and compact double-array data structure.

DoubleArrayAhoCorasick implements a pattern match automaton based on the Aho-Corasick algorithm, supporting linear-time pattern matching. The internal data structure employs the compact double-array structure, the fastest trie representation technique. It supports constant-time state-to-state traversal, allowing for very fast pattern matching. Moreover, each state is represented in the space of only 12 bytes.

Build instructions

DoubleArrayAhoCorasick supports the following two types of input data:

• DoubleArrayAhoCorasick::new builds an automaton from a set of byte strings while assigning unique identifiers in the input order.

• DoubleArrayAhoCorasick::with_values builds an automaton from a set of pairs of a byte string and a user-defined value.

Limitations

The maximum number of patterns is limited to 2^24-1. If a larger number of patterns is given, DaachorseError will be reported.

Implementations

impl<V> DoubleArrayAhoCorasick<V>

pub fn new<I, P>(patterns: I) -> Result<Self>

where I: IntoIterator<Item = P>, P: AsRef<[u8]>, V: Copy + TryFrom<usize>,

Creates a new DoubleArrayAhoCorasick from input patterns. The value i is automatically associated with patterns[i].

Arguments

• patterns - List of patterns.

Errors

DaachorseError is returned when

• patterns is empty,
• patterns contains entries of length zero,
• patterns contains duplicate entries,
• the conversion from the index i to the specified type V fails,
• the scale of patterns exceeds the expected one, or
• the scale of the resulting automaton exceeds the expected one.

Examples

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());

pub fn with_values<I, P>(patvals: I) -> Result<Self>

where I: IntoIterator<Item = (P, V)>, P: AsRef<[u8]>, V: Copy,

Creates a new DoubleArrayAhoCorasick from input pattern-value pairs.

Arguments

• patvals - List of pattern-value pairs.

Errors

DaachorseError is returned when

• patvals is empty,
• patvals contains patterns of length zero,
• patvals contains duplicate patterns,
• the scale of patvals exceeds the expected one, or
• the scale of the resulting automaton exceeds the expected one.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

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

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()));

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

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

pub fn find_iter<P>( &self, haystack: P, ) -> FindIterator<'_, U8SliceIterator<P>, V>

where P: AsRef<[u8]>,

Returns an iterator of non-overlapping matches in the given haystack.

Arguments

• haystack - String to search for.

Panics

If you do not specify MatchKind::Standard in the construction, the iterator is not supported and the function will panic.

Examples

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());

pub fn find_iter_from_iter<P>(&self, haystack: P) -> FindIterator<'_, P, V>

where P: Iterator<Item = u8>,

Returns an iterator of non-overlapping matches in the given haystack iterator.

Arguments

• haystack - u8 iterator to search for.

Panics

If you do not specify MatchKind::Standard in the construction, the iterator is not supported and the function will panic.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let haystack = "ab".as_bytes().iter().chain("cd".as_bytes()).copied();

let mut it = pma.find_iter_from_iter(haystack);

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());

pub fn find_overlapping_iter<P>( &self, haystack: P, ) -> FindOverlappingIterator<'_, U8SliceIterator<P>, V>

where P: AsRef<[u8]>,

Returns an iterator of overlapping matches in the given haystack.

Arguments

• haystack - String to search for.

Panics

If you do not specify MatchKind::Standard in the construction, the iterator is not supported and the function will panic.

Examples

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());

pub fn find_overlapping_iter_from_iter<P>( &self, haystack: P, ) -> FindOverlappingIterator<'_, P, V>

where P: Iterator<Item = u8>,

Returns an iterator of overlapping matches in the given haystack iterator.

Arguments

• haystack - u8 iterator to search for.

Panics

If you do not specify MatchKind::Standard in the construction, the iterator is not supported and the function will panic.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let haystack = "ab".as_bytes().iter().chain("cd".as_bytes()).copied();

let mut it = pma.find_overlapping_iter_from_iter(haystack);

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());

pub fn find_overlapping_no_suffix_iter<P>( &self, haystack: P, ) -> FindOverlappingNoSuffixIterator<'_, U8SliceIterator<P>, V>

where P: AsRef<[u8]>,

Returns an iterator of overlapping matches without suffixes in the given haystack iterator.

The Aho-Corasick algorithm reads through the haystack from left to right and reports matches when it reaches the end of each pattern. In the overlapping match, more than one pattern can be returned per report.

This iterator returns the first match on each report.

Arguments

• haystack - String to search for.

Panics

If you do not specify MatchKind::Standard in the construction, the iterator is not supported and the function will panic.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

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

let m = it.next().unwrap();
assert_eq!((0, 3, 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());

pub fn find_overlapping_no_suffix_iter_from_iter<P>( &self, haystack: P, ) -> FindOverlappingNoSuffixIterator<'_, P, V>

where P: Iterator<Item = u8>,

Returns an iterator of overlapping matches without suffixes in the given haystack iterator.

The Aho-Corasick algorithm reads through the haystack from left to right and reports matches when it reaches the end of each pattern. In the overlapping match, more than one pattern can be returned per report.

This iterator returns the first match on each report.

Arguments

• haystack - u8 to search for.

Panics

If you do not specify MatchKind::Standard in the construction, the iterator is not supported and the function will panic.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let haystack = "ab".as_bytes().iter().chain("cd".as_bytes()).copied();

let mut it = pma.find_overlapping_no_suffix_iter_from_iter(haystack);

let m = it.next().unwrap();
assert_eq!((0, 3, 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());

pub fn leftmost_find_iter<P>( &self, haystack: P, ) -> LeftmostFindIterator<'_, P, V>

where P: AsRef<[u8]>,

Returns an iterator of leftmost matches in the given haystack.

The leftmost match greedily searches the longest possible match at each iteration, and the match results do not overlap positionally such as DoubleArrayAhoCorasick::find_iter().

According to the MatchKind option you specified in the construction, the behavior is changed for multiple possible matches, as follows.

• If you set MatchKind::LeftmostLongest, it reports the match corresponding to the longest pattern.

• If you set MatchKind::LeftmostFirst, it reports the match corresponding to the pattern earlier registered to the automaton.

Arguments

• haystack - String to search for.

Panics

If you do not specify MatchKind::LeftmostFirst or MatchKind::LeftmostLongest in the construction, the iterator is not supported and the function will panic.

Examples

LeftmostLongest

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());

LeftmostFirst

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());

pub fn find_stepper(&self) -> FindStepper<'_, V>

Returns a stepper of non-overlapping matches that consumes bytes one by one.

Panics

If you do not specify MatchKind::Standard in the construction, the stepper is not supported and the function will panic.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let mut stepper = pma.find_stepper();

let m = stepper.consume(b'a');
let m = m.unwrap();
assert_eq!((0, 1, 2), (m.start(), m.end(), m.value())); // a

let m = stepper.consume(b'b');
assert_eq!(None, m);

let m = stepper.consume(b'c');
assert_eq!(None, m);

let m = stepper.consume(b'd');
let m = m.unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value())); // bcd

pub fn find_overlapping_stepper(&self) -> FindOverlappingStepper<'_, V>

Returns a stepper of overlapping matches that consumes bytes one by one.

Panics

If you do not specify MatchKind::Standard in the construction, the stepper is not supported and the function will panic.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let mut stepper = pma.find_overlapping_stepper();

let mut it = stepper.consume(b'a');
let m = it.next().unwrap();
assert_eq!((0, 1, 2), (m.start(), m.end(), m.value())); // a
assert_eq!(None, it.next());

let mut it = stepper.consume(b'b');
let m = it.next().unwrap();
assert_eq!((0, 2, 1), (m.start(), m.end(), m.value())); // ab
assert_eq!(None, it.next());

let mut it = stepper.consume(b'c');
assert_eq!(None, it.next());

let mut it = stepper.consume(b'd');
let m = it.next().unwrap();
assert_eq!((1, 4, 0), (m.start(), m.end(), m.value())); // bcd
assert_eq!(None, it.next());

pub fn heap_bytes(&self) -> usize

Returns the total amount of heap used by this automaton in bytes.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

assert_eq!(3108, pma.heap_bytes());

pub fn num_states(&self) -> usize

Returns the total number of states this automaton has.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

assert_eq!(pma.num_states(), 6);

pub fn serialize(&self) -> Vec<u8>

where V: Serializable,

Serializes the automaton into a Vec.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

pub fn deserialize(source: &[u8]) -> Result<(Self, &[u8])>

where V: Serializable,

Deserializes the automaton from the given slice.

Warning

This function verifies that the input automaton data will not cause out-of-bounds memory access within this crate; however, it does not verify that the data is a valid Aho-Corasick automaton. Consequently, if malformed data is provided, it may lead to infinite loops or cause Match to return inaccurate ranges. Use this function only if you can tolerate such errors.

Arguments

• source - A source slice.

Returns

A tuple of the automaton and the slice not used for the deserialization.

Errors

DaachorseError is returned when the given data is an invalid automaton.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let (pma, _) = DoubleArrayAhoCorasick::<u32>::deserialize(&bytes).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());

pub unsafe fn deserialize_unchecked(source: &[u8]) -> (Self, &[u8])

where V: Serializable,

Deserializes the automaton from the given slice without performing any validation.

This function does not perform any validation on the input data. If processing speed is not critical, consider using DoubleArrayAhoCorasick::deserialize().

Arguments

• source - A source slice.

Returns

A tuple of the automaton and the slice not used for the deserialization.

Safety

The given data must be a correct automaton exported by DoubleArrayAhoCorasick::serialize() function.

Examples

use daachorse::DoubleArrayAhoCorasick;

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

let (pma, _) = unsafe { DoubleArrayAhoCorasick::<u32>::deserialize_unchecked(&bytes) };

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());

Trait Implementations

impl<V: Clone> Clone for DoubleArrayAhoCorasick<V>

fn clone(&self) -> DoubleArrayAhoCorasick<V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V: Hash> Hash for DoubleArrayAhoCorasick<V>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<V: PartialEq> PartialEq for DoubleArrayAhoCorasick<V>

fn eq(&self, other: &DoubleArrayAhoCorasick<V>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<V: Eq> Eq for DoubleArrayAhoCorasick<V>

impl<V> StructuralPartialEq for DoubleArrayAhoCorasick<V>