Struct NGram 

pub struct NGram(/* private fields */);

A compact n-gram identifier. See the module-level documentation for the bit layout.

Note: we could store n-grams up to length 8 verbatim in a u64. However, that would explode the number of distinct keys in a search dictionary. For that reason we compress n-grams into a u32, which puts a more reasonable upper bound on the number of dictionary keys.

Note: by storing the length explicitly, we ensure that only n-grams of the same length can collide. This is important because there are exponentially more long n-grams than short ones. At the same time, longer n-grams occur less frequently, so colliding long n-grams won’t increase the false-positive rate too much.

Construction

Use NGram::from_bytes for one-off hashing, or the rolling 8-byte window helper inside the extraction loop for amortised O(1) computation per n-gram.

Implementations

impl NGram

pub fn from_bytes(src: &[u8]) -> Self

Build an NGram by hashing the given byte slice from scratch.

Panics

In debug builds, panics if src.len() is not in 2..=MAX_SPARSE_GRAM_SIZE.

pub fn len(&self) -> usize

The byte length of the n-gram.

pub fn is_empty(&self) -> bool

Whether this represents an empty gram. Valid n-grams are always at least 2 bytes long, so this only holds for a default-constructed placeholder.

pub fn as_u32(&self) -> u32

The raw packed u32. This is an opaque, well-distributed identifier suitable as a hash-map or hash-set key.

Trait Implementations

impl Clone for NGram

fn clone(&self) -> NGram

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Copy for NGram

impl Debug for NGram

The encoded u32 representation is not human readable. This formatter improves the situation at least for short ascii grams.

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for NGram

fn default() -> NGram

Returns the “default value” for a type.

impl Eq for NGram

impl Hash for NGram

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 Ord for NGram

fn cmp(&self, other: &NGram) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for NGram

fn eq(&self, other: &NGram) -> bool

Equality operator ==.

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

Inequality operator !=.

impl PartialOrd for NGram

fn partial_cmp(&self, other: &NGram) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl StructuralPartialEq for NGram