bndm

Crates.io	bndm
lib.rs	bndm
version	1.0.1
source	src
created_at	2024-10-27 15:13:27.657284
updated_at	2024-10-27 18:01:24.339909
description	A Rust library that implements the BNDM algorithm for fast and efficient pattern matching, with support for wildcard searches.
homepage
repository	https://github.com/WilfredC64/bndm
max_upload_size
id	1424695
size	33,620

Wilfred (WilfredC64)

documentation

https://docs.rs/bndm/

README

BNDM

License

A Rust library that implements the BNDM algorithm for fast and efficient pattern matching, with support for wildcard searches.

Overview

BNDM (Backward Nondeterministic Dawg Matching) is an optimized string search algorithm designed for efficiently locating patterns within a text. The BNDM algorithm was invented by Gonzalo Navarro and Mathieu Raffinot.

The BNDM algorithm works by preprocessing the pattern to generate a set of bitmasks. These bitmasks are then used to efficiently scan the text for occurrences of the pattern.

Unlike the traditional BNDM algorithm, this implementation is optimized by scanning the first 2 bytes outside the inner loop. Additionally, it does not have the limitation that the pattern size is limited to the word size of the CPU. It's possible to search for larger patterns than the word size and still benefit from the performance that BNDM offers.

One of the key features of this implementation is its support for wildcard search. This algorithm is ideally suited for this, as it does not impact the performance of the pattern matching itself. The wildcard search only slightly affects the indexing, ensuring that the overall efficiency of the pattern matching remains high.

Usage

Here is an example of how to use the library to search for a pattern in a text:

Without wildcard

use bndm::{BndmConfig, find_pattern};

let source = b"The quick brown fox jumps over the lazy dog";
let pattern = b"jumps";
let config = BndmConfig::new(pattern, None);
let index = find_pattern(source, &config);
assert_eq!(index, Some(20));

With wildcard

use bndm::{BndmConfig, find_pattern};

let source = b"The quick brown fox jumps over the lazy dog";
let pattern = b"ju??s";
let config = BndmConfig::new(pattern, Some(b'?'));
let index = find_pattern(source, &config);
assert_eq!(index, Some(20));