milli_core/update/
words_prefixes_fst.rs

1use std::iter::{repeat_with, FromIterator};
2use std::str;
3
4use fst::{SetBuilder, Streamer};
5use heed::RwTxn;
6
7use crate::{Index, Result, SmallString32};
8
9pub struct WordsPrefixesFst<'t, 'i> {
10    wtxn: &'t mut RwTxn<'i>,
11    index: &'i Index,
12    threshold: usize,
13    max_prefix_length: usize,
14}
15
16impl<'t, 'i> WordsPrefixesFst<'t, 'i> {
17    pub fn new(wtxn: &'t mut RwTxn<'i>, index: &'i Index) -> WordsPrefixesFst<'t, 'i> {
18        WordsPrefixesFst { wtxn, index, threshold: 100, max_prefix_length: 4 }
19    }
20
21    /// Set the number of words required to make a prefix be part of the words prefixes
22    /// database. If a word prefix is supposed to match more than this number of words in the
23    /// dictionary, therefore this prefix is added to the words prefixes datastructures.
24    ///
25    /// Default value is 100. This value must be higher than 50 and will be clamped
26    /// to this bound otherwise.
27    pub fn threshold(&mut self, value: usize) -> &mut Self {
28        self.threshold = value;
29        self
30    }
31
32    /// Set the maximum length of prefixes in bytes.
33    ///
34    /// Default value is `4` bytes. This value must be between 1 and 25 will be clamped
35    /// to these bounds, otherwise.
36    pub fn max_prefix_length(&mut self, value: usize) -> &mut Self {
37        self.max_prefix_length = value;
38        self
39    }
40
41    #[tracing::instrument(
42        level = "trace",
43        skip_all,
44        target = "indexing::prefix",
45        name = "words_prefix_fst"
46    )]
47    pub fn execute(self) -> Result<()> {
48        let words_fst = self.index.words_fst(self.wtxn)?;
49
50        let mut current_prefix = vec![SmallString32::new(); self.max_prefix_length];
51        let mut current_prefix_count = vec![0; self.max_prefix_length];
52        let mut builders =
53            repeat_with(SetBuilder::memory).take(self.max_prefix_length).collect::<Vec<_>>();
54
55        let mut stream = words_fst.stream();
56        while let Some(bytes) = stream.next() {
57            for n in 0..self.max_prefix_length {
58                let current_prefix = &mut current_prefix[n];
59                let current_prefix_count = &mut current_prefix_count[n];
60                let builder = &mut builders[n];
61
62                // We try to get the first n bytes out of this string but we only want
63                // to split at valid characters bounds. If we try to split in the middle of
64                // a character we ignore this word and go to the next one.
65                let word = str::from_utf8(bytes)?;
66                let prefix = match word.get(..=n) {
67                    Some(prefix) => prefix,
68                    None => continue,
69                };
70
71                // This is the first iteration of the loop,
72                // or the current word doesn't starts with the current prefix.
73                if *current_prefix_count == 0 || prefix != current_prefix.as_str() {
74                    *current_prefix = SmallString32::from(prefix);
75                    *current_prefix_count = 0;
76                }
77
78                *current_prefix_count += 1;
79
80                // There is enough words corresponding to this prefix to add it to the cache.
81                if *current_prefix_count >= self.threshold {
82                    builder.insert(prefix)?;
83                }
84            }
85        }
86
87        // We merge all of the previously computed prefixes into on final set.
88        let prefix_fsts: Vec<_> = builders.into_iter().map(|sb| sb.into_set()).collect();
89        let op = fst::set::OpBuilder::from_iter(prefix_fsts.iter());
90        let mut builder = fst::SetBuilder::memory();
91        builder.extend_stream(op.r#union())?;
92        let prefix_fst = builder.into_set();
93
94        // Set the words prefixes FST in the dtabase.
95        self.index.put_words_prefixes_fst(self.wtxn, &prefix_fst)?;
96
97        Ok(())
98    }
99}
milli_core/update/words_prefixes_fst.rs

milli_core/update/
words_prefixes_fst.rs
