1use serde::{Deserialize, Serialize};
15use unicode_segmentation::UnicodeSegmentation;
16
17use crate::error::{MnemoError, Result};
18
19pub(crate) const TOKENIZER_V1: u8 = 1;
22
23const MAX_TOKEN_BYTES: usize = 64;
25
26pub(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
45pub(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
62pub(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
69pub(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#[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 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 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 pub fn len(&self) -> usize {
137 self.lens.len()
138 }
139
140 pub fn is_empty(&self) -> bool {
142 self.lens.is_empty()
143 }
144}
145
146#[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
162pub(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
191pub(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}