Skip to main content

mnemo_engine/
text.rs

1//! FMT-9d (Phase 2): the keyword side of hybrid recall.
2//!
3//! * [`tokenize`]: UAX #29 words, lowercased, plus **compound tokens**. A
4//!   compound is a whitespace-separated run with its leading and trailing
5//!   punctuation stripped, kept whole when it still has punctuation inside,
6//!   so identifiers like `BP.1`, `v0.9.0` or `PR-10b.2` are searchable as
7//!   themselves (UAX #29 splits them). No stemming in v1.
8//! * Segments: the on-disk unit of the BM25 index. A segment is
9//!   `[u32 dict length][dict][postings]`. The dict is an rmp list of
10//!   `(term, offset, length)`, sorted by term; postings are, per term,
11//!   `(doc delta varint, tf u8)` pairs in ascending doc order.
12//! * [`bm25`]: the per-term score, with k1 1.2 and b 0.75 by default.
13
14use serde::{Deserialize, Serialize};
15use unicode_segmentation::UnicodeSegmentation;
16
17use crate::error::{MnemoError, Result};
18
19/// The tokenizer above. Recorded in the BM25 manifest, so a later
20/// tokenizer (a CJK bigram one, say) can be added without a format change.
21pub(crate) const TOKENIZER_V1: u8 = 1;
22
23/// Longest token indexed, in bytes (longer ones are dropped).
24const MAX_TOKEN_BYTES: usize = 64;
25
26/// The tokens of `text`, in order, with repeats.
27pub(crate) fn tokenize(text: &str) -> Vec<String> {
28    let mut out: Vec<String> = text
29        .unicode_words()
30        .map(|w| w.to_lowercase())
31        .filter(|w| w.len() <= MAX_TOKEN_BYTES)
32        .collect();
33    for run in text.split_whitespace() {
34        let t = run.trim_matches(|c: char| !c.is_alphanumeric());
35        if t.len() < 2 || t.len() > MAX_TOKEN_BYTES {
36            continue;
37        }
38        if t.chars().any(|c| !c.is_alphanumeric()) && t.chars().any(|c| c.is_alphanumeric()) {
39            out.push(t.to_lowercase());
40        }
41    }
42    out
43}
44
45/// Term frequencies of one document: `(term, tf)`, sorted by term, tf
46/// saturating at 255. Also returns the document length (all tokens).
47pub(crate) fn term_freqs(text: &str) -> (Vec<(String, u8)>, u16) {
48    let toks = tokenize(text);
49    let len = toks.len().min(u16::MAX as usize) as u16;
50    let mut map: std::collections::BTreeMap<String, u32> = std::collections::BTreeMap::new();
51    for t in toks {
52        *map.entry(t).or_default() += 1;
53    }
54    (
55        map.into_iter()
56            .map(|(t, n)| (t, n.min(255) as u8))
57            .collect(),
58        len,
59    )
60}
61
62/// BM25 score of one term in one document.
63pub(crate) fn bm25(tf: u8, idf: f32, doc_len: u16, avgdl: f32, k1: f32, b: f32) -> f32 {
64    let tf = tf as f32;
65    let norm = 1.0 - b + b * (doc_len as f32 / avgdl.max(1e-6));
66    idf * tf * (k1 + 1.0) / (tf + k1 * norm)
67}
68
69/// BM25 idf for a term in `df` of `n` live documents.
70pub(crate) fn idf(n: usize, df: usize) -> f32 {
71    let (n, df) = (n as f32, df as f32);
72    (1.0 + (n - df + 0.5) / (df + 0.5)).ln()
73}
74
75/// An in-memory keyword index over a set of texts, with the tokenizer and
76/// BM25 scoring (k1 1.2, b 0.75) of v9's keyword recall, for tools that
77/// search what they've already read, without the file open (`mnemo
78/// inspect`). It needs no embedder and works on texts from any format.
79///
80/// ```
81/// use mnemo_engine::KeywordIndex;
82/// let ix = KeywordIndex::new(["the deploy runs on v0.9.0", "tea, not coffee"]);
83/// assert_eq!(ix.search("v0.9.0", 5)[0].0, 0);
84/// assert!(ix.search("nothing", 5).is_empty());
85/// ```
86#[derive(Clone, Debug, Default)]
87pub struct KeywordIndex {
88    postings: std::collections::BTreeMap<String, Vec<(usize, u8)>>,
89    lens: Vec<u16>,
90    avgdl: f32,
91}
92
93impl KeywordIndex {
94    /// Index `texts`; a hit's index is the text's position here.
95    pub fn new<'a>(texts: impl IntoIterator<Item = &'a str>) -> Self {
96        let mut ix = Self::default();
97        for (doc, text) in texts.into_iter().enumerate() {
98            let (tfs, len) = term_freqs(text);
99            for (term, tf) in tfs {
100                ix.postings.entry(term).or_default().push((doc, tf));
101            }
102            ix.lens.push(len);
103        }
104        let total: u64 = ix.lens.iter().map(|&l| l as u64).sum();
105        ix.avgdl = if ix.lens.is_empty() {
106            0.0
107        } else {
108            total as f32 / ix.lens.len() as f32
109        };
110        ix
111    }
112
113    /// The texts that match any of `query`'s terms, best first, at most
114    /// `top_k`, as `(index, score)`. Ties keep the texts' order.
115    pub fn search(&self, query: &str, top_k: usize) -> Vec<(usize, f32)> {
116        let terms: std::collections::BTreeSet<String> = tokenize(query).into_iter().collect();
117        let n = self.lens.len();
118        let mut scores: std::collections::BTreeMap<usize, f32> = std::collections::BTreeMap::new();
119        for term in &terms {
120            let Some(posts) = self.postings.get(term) else {
121                continue;
122            };
123            let idf = idf(n, posts.len());
124            for &(doc, tf) in posts {
125                *scores.entry(doc).or_default() +=
126                    bm25(tf, idf, self.lens[doc], self.avgdl, 1.2, 0.75);
127            }
128        }
129        let mut hits: Vec<(usize, f32)> = scores.into_iter().collect();
130        hits.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
131        hits.truncate(top_k);
132        hits
133    }
134
135    /// How many texts it holds.
136    pub fn len(&self) -> usize {
137        self.lens.len()
138    }
139
140    /// Whether it holds no text.
141    pub fn is_empty(&self) -> bool {
142        self.lens.is_empty()
143    }
144}
145
146/// One dict entry: a term and its postings' byte range.
147#[derive(Serialize, Deserialize, Clone, Debug)]
148pub(crate) struct DictEntry {
149    pub term: String,
150    pub off: u32,
151    pub len: u32,
152}
153
154fn put_varint(out: &mut Vec<u8>, mut v: u32) {
155    while v >= 0x80 {
156        out.push((v as u8) | 0x80);
157        v >>= 7;
158    }
159    out.push(v as u8);
160}
161
162/// Decode a postings slice into `(doc, tf)` pairs.
163pub(crate) fn decode_postings(b: &[u8]) -> Result<Vec<(u32, u8)>> {
164    let bad = || MnemoError::Invalid("malformed BM25 postings".into());
165    let mut out = Vec::new();
166    let mut i = 0usize;
167    let mut doc = 0u32;
168    while i < b.len() {
169        let mut delta = 0u32;
170        let mut shift = 0u32;
171        loop {
172            let byte = *b.get(i).ok_or_else(bad)?;
173            i += 1;
174            if shift > 28 {
175                return Err(bad());
176            }
177            delta |= ((byte & 0x7f) as u32) << shift;
178            if byte & 0x80 == 0 {
179                break;
180            }
181            shift += 7;
182        }
183        doc = doc.checked_add(delta).ok_or_else(bad)?;
184        let tf = *b.get(i).ok_or_else(bad)?;
185        i += 1;
186        out.push((doc, tf));
187    }
188    Ok(out)
189}
190
191/// Build a segment from documents' term frequencies: `(doc, terms)`.
192pub(crate) fn build_segment(docs: &[(u32, Vec<(String, u8)>)]) -> Result<Vec<u8>> {
193    let mut by_term: std::collections::BTreeMap<&str, Vec<(u32, u8)>> =
194        std::collections::BTreeMap::new();
195    for (doc, terms) in docs {
196        for (t, tf) in terms {
197            by_term.entry(t.as_str()).or_default().push((*doc, *tf));
198        }
199    }
200    let mut dict: Vec<DictEntry> = Vec::with_capacity(by_term.len());
201    let mut postings: Vec<u8> = Vec::new();
202    for (term, mut list) in by_term {
203        list.sort_unstable_by_key(|&(d, _)| d);
204        let off = postings.len() as u32;
205        let mut prev = 0u32;
206        for (d, tf) in list {
207            put_varint(&mut postings, d - prev);
208            postings.push(tf);
209            prev = d;
210        }
211        dict.push(DictEntry {
212            term: term.to_string(),
213            off,
214            len: postings.len() as u32 - off,
215        });
216    }
217    let dict_bytes = rmp_serde::to_vec(&dict).map_err(|e| MnemoError::Serialize(e.to_string()))?;
218    let mut out = Vec::with_capacity(4 + dict_bytes.len() + postings.len());
219    out.extend_from_slice(&(dict_bytes.len() as u32).to_le_bytes());
220    out.extend_from_slice(&dict_bytes);
221    out.extend_from_slice(&postings);
222    Ok(out)
223}
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228
229    #[test]
230    fn tokenizer_keeps_identifiers_whole() {
231        let t = tokenize("Ship BP.1 in v0.9.0 (see PR-10b.2), then flush().");
232        for want in ["ship", "bp", "1", "bp.1", "v0.9.0", "pr-10b.2", "flush"] {
233            assert!(t.contains(&want.to_string()), "{want} missing from {t:?}");
234        }
235        assert!(
236            !t.contains(&"flush()".to_string()),
237            "trailing punctuation stripped"
238        );
239        assert!(tokenize("Ünïcödé Wörds").contains(&"ünïcödé".to_string()));
240    }
241
242    #[test]
243    fn segment_round_trips() {
244        let docs = vec![
245            (3u32, term_freqs("alpha beta beta").0),
246            (7u32, term_freqs("beta gamma").0),
247            (300u32, term_freqs("alpha").0),
248        ];
249        let seg = build_segment(&docs).unwrap();
250        let dlen = u32::from_le_bytes(seg[0..4].try_into().unwrap()) as usize;
251        let dict: Vec<DictEntry> = rmp_serde::from_slice(&seg[4..4 + dlen]).unwrap();
252        let post = &seg[4 + dlen..];
253        let find = |t: &str| {
254            let e = dict.iter().find(|e| e.term == t).unwrap();
255            decode_postings(&post[e.off as usize..(e.off + e.len) as usize]).unwrap()
256        };
257        assert_eq!(find("alpha"), vec![(3, 1), (300, 1)]);
258        assert_eq!(find("beta"), vec![(3, 2), (7, 1)]);
259        assert_eq!(find("gamma"), vec![(7, 1)]);
260    }
261
262    #[test]
263    fn bm25_prefers_rarer_terms_and_shorter_docs() {
264        assert!(idf(100, 1) > idf(100, 50));
265        assert!(bm25(1, 1.0, 5, 10.0, 1.2, 0.75) > bm25(1, 1.0, 20, 10.0, 1.2, 0.75));
266        assert!(bm25(3, 1.0, 10, 10.0, 1.2, 0.75) > bm25(1, 1.0, 10, 10.0, 1.2, 0.75));
267    }
268}