simstring_rust 0.3.4

A native Rust implementation of the SimString algorithm
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

use crate::FeatureExtractor;
use lasso::{Rodeo, Spur};

#[derive(Clone)]
pub struct CharacterNgrams {
    n: usize,
    endmarker: String,
}

impl CharacterNgrams {
    pub fn new(n: usize, endmarker: &str) -> Self {
        Self {
            n,
            endmarker: endmarker.to_string(),
        }
    }
}

impl Default for CharacterNgrams {
    fn default() -> Self {
        Self::new(2, "$")
    }
}

impl FeatureExtractor for CharacterNgrams {
    fn features(&self, text: &str, interner: &mut Rodeo) -> Vec<Spur> {
        if self.n == 0 {
            return vec![];
        }

        // Pre-calculate capacity to avoid reallocations
        let text_len = text.chars().count();
        let padding_len = self.n.saturating_sub(1);
        let total_len = text_len + 2 * padding_len;

        if total_len < self.n {
            return vec![];
        }

        let expected_ngrams = total_len - self.n + 1;
        let mut ngrams = Vec::with_capacity(expected_ngrams);

        let padding = self.endmarker.repeat(padding_len);

        // collect chars once, then slice
        let mut all_chars = Vec::with_capacity(total_len);
        all_chars.extend(padding.chars());
        all_chars.extend(text.chars());
        all_chars.extend(padding.chars());

        // Generate n-grams using efficient windowing
        for window in all_chars.windows(self.n) {
            // Pre-allocate string with known capacity
            let mut ngram = String::with_capacity(self.n * 4); // Assume max 4 bytes per char
            for &ch in window {
                ngram.push(ch);
            }
            ngrams.push(ngram);
        }

        super::append_feature_counts(interner, ngrams)
    }
}