1use serde::{Deserialize, Serialize};
19use unicode_segmentation::UnicodeSegmentation;
20
21use crate::error::{MnemoError, Result};
22
23pub(crate) const TOKENIZER_V1: u8 = 1;
30
31pub(crate) const V2_MARK: &str = "\u{0}mnemo.tokenizer.2";
36
37pub(crate) const MIXED_MARK: &str = "\u{0}mnemo.tokenizer.mixed";
41
42#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub(crate) enum Tokenizer {
45 V1,
47 V2,
49}
50
51#[derive(Clone, Copy, Debug, PartialEq, Eq)]
54pub(crate) enum SegmentTokens {
55 V1,
57 V2,
59 Mixed,
61}
62
63impl SegmentTokens {
64 pub(crate) fn from_first_term(first: Option<&str>) -> Self {
66 match first {
67 Some(V2_MARK) => SegmentTokens::V2,
68 Some(MIXED_MARK) => SegmentTokens::Mixed,
69 _ => SegmentTokens::V1,
70 }
71 }
72
73 pub(crate) fn combine(parts: impl IntoIterator<Item = SegmentTokens>) -> Option<Self> {
76 let mut out: Option<SegmentTokens> = None;
77 for p in parts {
78 out = Some(match (out, p) {
79 (None, p) => p,
80 (Some(a), b) if a == b => a,
81 _ => SegmentTokens::Mixed,
82 });
83 }
84 out
85 }
86}
87
88#[derive(Clone, Copy, Debug, PartialEq, Eq)]
91pub enum KeywordTokenizer {
92 V1,
95 V2,
97 Mixed,
102}
103
104impl KeywordTokenizer {
105 pub(crate) fn of(segments: impl IntoIterator<Item = SegmentTokens>) -> Self {
108 match SegmentTokens::combine(segments) {
109 None | Some(SegmentTokens::V2) => KeywordTokenizer::V2,
110 Some(SegmentTokens::V1) => KeywordTokenizer::V1,
111 Some(SegmentTokens::Mixed) => KeywordTokenizer::Mixed,
112 }
113 }
114
115 pub(crate) fn tokenizer(self) -> Tokenizer {
120 match self {
121 KeywordTokenizer::V1 => Tokenizer::V1,
122 KeywordTokenizer::V2 | KeywordTokenizer::Mixed => Tokenizer::V2,
123 }
124 }
125
126 pub fn as_str(self) -> &'static str {
128 match self {
129 KeywordTokenizer::V1 => "1",
130 KeywordTokenizer::V2 => "2",
131 KeywordTokenizer::Mixed => "mixed",
132 }
133 }
134}
135
136const MAX_TOKEN_BYTES: usize = 64;
138
139pub(crate) fn tokenize_with(tok: Tokenizer, text: &str) -> Vec<String> {
147 match tok {
148 Tokenizer::V1 => tokenize(text),
149 Tokenizer::V2 => {
150 let mut out = Vec::new();
151 for run in text.split_whitespace() {
152 let mut terms: Vec<String> = run
153 .unicode_words()
154 .map(|w| w.to_lowercase())
155 .filter(|w| w.len() <= MAX_TOKEN_BYTES)
156 .collect();
157 terms.extend(compound(run));
158 let whole = terms.len();
159 for i in 0..whole {
160 let parts = token_parts(&terms[i]);
161 terms.extend(parts);
162 }
163 let mut seen = std::collections::BTreeSet::new();
164 out.extend(terms.into_iter().filter(|t| seen.insert(t.clone())));
165 }
166 out
167 }
168 }
169}
170
171fn compound(run: &str) -> Option<String> {
174 let t = run.trim_matches(|c: char| !c.is_alphanumeric());
175 if t.len() < 2 || t.len() > MAX_TOKEN_BYTES {
176 return None;
177 }
178 (t.chars().any(|c| !c.is_alphanumeric()) && t.chars().any(|c| c.is_alphanumeric()))
179 .then(|| t.to_lowercase())
180}
181
182fn token_parts(token: &str) -> Vec<String> {
188 let mut out: Vec<String> = Vec::new();
189 let stem = token
190 .strip_suffix("'s")
191 .or_else(|| token.strip_suffix("\u{2019}s"))
192 .filter(|s| !s.is_empty());
193 if let Some(s) = stem {
194 out.push(s.to_string());
195 }
196 let base = stem.unwrap_or(token);
197 let pieces: Vec<&str> = base
198 .split("::")
199 .flat_map(|p| p.split(['.', '/', '_', '-']))
200 .filter(|p| !p.is_empty())
201 .collect();
202 let pieces: Vec<&str> = if pieces.len() > 1 {
203 pieces
204 .into_iter()
205 .filter(|p| !p.chars().all(|c| c.is_ascii_digit()))
206 .collect()
207 } else {
208 Vec::new()
209 };
210 for p in pieces {
211 if p != token && !out.iter().any(|o| o == p) {
212 out.push(p.to_string());
213 }
214 }
215 out
216}
217
218pub(crate) fn tokenize(text: &str) -> Vec<String> {
220 let mut out: Vec<String> = text
221 .unicode_words()
222 .map(|w| w.to_lowercase())
223 .filter(|w| w.len() <= MAX_TOKEN_BYTES)
224 .collect();
225 out.extend(text.split_whitespace().filter_map(compound));
226 out
227}
228
229pub(crate) fn term_freqs(tok: Tokenizer, text: &str) -> (Vec<(String, u8)>, u16) {
232 let toks = tokenize_with(tok, text);
233 let len = toks.len().min(u16::MAX as usize) as u16;
234 let mut map: std::collections::BTreeMap<String, u32> = std::collections::BTreeMap::new();
235 for t in toks {
236 *map.entry(t).or_default() += 1;
237 }
238 (
239 map.into_iter()
240 .map(|(t, n)| (t, n.min(255) as u8))
241 .collect(),
242 len,
243 )
244}
245
246pub(crate) fn bm25(tf: u8, idf: f32, doc_len: u16, avgdl: f32, k1: f32, b: f32) -> f32 {
248 let tf = tf as f32;
249 let norm = 1.0 - b + b * (doc_len as f32 / avgdl.max(1e-6));
250 idf * tf * (k1 + 1.0) / (tf + k1 * norm)
251}
252
253pub(crate) fn idf(n: usize, df: usize) -> f32 {
255 let (n, df) = (n as f32, df as f32);
256 (1.0 + (n - df + 0.5) / (df + 0.5)).ln()
257}
258
259#[derive(Clone, Debug, Default)]
275pub struct KeywordIndex {
276 postings: std::collections::BTreeMap<String, Vec<(usize, u8)>>,
277 lens: Vec<u16>,
278 avgdl: f32,
279}
280
281impl KeywordIndex {
282 pub fn new<'a>(texts: impl IntoIterator<Item = &'a str>) -> Self {
284 let mut ix = Self::default();
285 for (doc, text) in texts.into_iter().enumerate() {
286 let (tfs, len) = term_freqs(Tokenizer::V2, text);
287 for (term, tf) in tfs {
288 ix.postings.entry(term).or_default().push((doc, tf));
289 }
290 ix.lens.push(len);
291 }
292 let total: u64 = ix.lens.iter().map(|&l| l as u64).sum();
293 ix.avgdl = if ix.lens.is_empty() {
294 0.0
295 } else {
296 total as f32 / ix.lens.len() as f32
297 };
298 ix
299 }
300
301 pub fn search(&self, query: &str, top_k: usize) -> Vec<(usize, f32)> {
304 let terms: std::collections::BTreeSet<String> =
305 tokenize_with(Tokenizer::V2, query).into_iter().collect();
306 let n = self.lens.len();
307 let mut scores: std::collections::BTreeMap<usize, f32> = std::collections::BTreeMap::new();
308 for term in &terms {
309 let Some(posts) = self.postings.get(term) else {
310 continue;
311 };
312 let idf = idf(n, posts.len());
313 for &(doc, tf) in posts {
314 *scores.entry(doc).or_default() +=
315 bm25(tf, idf, self.lens[doc], self.avgdl, 1.2, 0.75);
316 }
317 }
318 let mut hits: Vec<(usize, f32)> = scores.into_iter().collect();
319 hits.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
320 hits.truncate(top_k);
321 hits
322 }
323
324 pub fn len(&self) -> usize {
326 self.lens.len()
327 }
328
329 pub fn is_empty(&self) -> bool {
331 self.lens.is_empty()
332 }
333}
334
335#[derive(Serialize, Deserialize, Clone, Debug)]
337pub(crate) struct DictEntry {
338 pub term: String,
339 pub off: u32,
340 pub len: u32,
341}
342
343fn put_varint(out: &mut Vec<u8>, mut v: u32) {
344 while v >= 0x80 {
345 out.push((v as u8) | 0x80);
346 v >>= 7;
347 }
348 out.push(v as u8);
349}
350
351pub(crate) fn decode_postings(b: &[u8]) -> Result<Vec<(u32, u8)>> {
353 let bad = || MnemoError::Invalid("malformed BM25 postings".into());
354 let mut out = Vec::new();
355 let mut i = 0usize;
356 let mut doc = 0u32;
357 while i < b.len() {
358 let mut delta = 0u32;
359 let mut shift = 0u32;
360 loop {
361 let byte = *b.get(i).ok_or_else(bad)?;
362 i += 1;
363 if shift > 28 {
364 return Err(bad());
365 }
366 delta |= ((byte & 0x7f) as u32) << shift;
367 if byte & 0x80 == 0 {
368 break;
369 }
370 shift += 7;
371 }
372 doc = doc.checked_add(delta).ok_or_else(bad)?;
373 let tf = *b.get(i).ok_or_else(bad)?;
374 i += 1;
375 out.push((doc, tf));
376 }
377 Ok(out)
378}
379
380pub(crate) fn build_segment(
384 docs: &[(u32, Vec<(String, u8)>)],
385 tokens: SegmentTokens,
386) -> Result<Vec<u8>> {
387 let mut by_term: std::collections::BTreeMap<&str, Vec<(u32, u8)>> =
388 std::collections::BTreeMap::new();
389 match tokens {
390 SegmentTokens::V1 => {}
391 SegmentTokens::V2 => {
392 by_term.insert(V2_MARK, vec![(0, 1)]);
393 }
394 SegmentTokens::Mixed => {
395 by_term.insert(MIXED_MARK, vec![(0, 1)]);
396 }
397 }
398 for (doc, terms) in docs {
399 for (t, tf) in terms {
400 by_term.entry(t.as_str()).or_default().push((*doc, *tf));
401 }
402 }
403 let mut dict: Vec<DictEntry> = Vec::with_capacity(by_term.len());
404 let mut postings: Vec<u8> = Vec::new();
405 for (term, mut list) in by_term {
406 list.sort_unstable_by_key(|&(d, _)| d);
407 let off = postings.len() as u32;
408 let mut prev = 0u32;
409 for (d, tf) in list {
410 put_varint(&mut postings, d - prev);
411 postings.push(tf);
412 prev = d;
413 }
414 dict.push(DictEntry {
415 term: term.to_string(),
416 off,
417 len: postings.len() as u32 - off,
418 });
419 }
420 let dict_bytes = rmp_serde::to_vec(&dict).map_err(|e| MnemoError::Serialize(e.to_string()))?;
421 let mut out = Vec::with_capacity(4 + dict_bytes.len() + postings.len());
422 out.extend_from_slice(&(dict_bytes.len() as u32).to_le_bytes());
423 out.extend_from_slice(&dict_bytes);
424 out.extend_from_slice(&postings);
425 Ok(out)
426}
427
428#[cfg(test)]
429mod tests {
430 use super::*;
431
432 #[test]
433 fn tokenizer_keeps_identifiers_whole() {
434 let t = tokenize("Ship BP.1 in v0.9.0 (see PR-10b.2), then flush().");
435 for want in ["ship", "bp", "1", "bp.1", "v0.9.0", "pr-10b.2", "flush"] {
436 assert!(t.contains(&want.to_string()), "{want} missing from {t:?}");
437 }
438 assert!(
439 !t.contains(&"flush()".to_string()),
440 "trailing punctuation stripped"
441 );
442 assert!(tokenize("Ünïcödé Wörds").contains(&"ünïcödé".to_string()));
443 }
444
445 #[test]
446 fn segment_round_trips() {
447 let docs = vec![
448 (3u32, term_freqs(Tokenizer::V1, "alpha beta beta").0),
449 (7u32, term_freqs(Tokenizer::V1, "beta gamma").0),
450 (300u32, term_freqs(Tokenizer::V1, "alpha").0),
451 ];
452 let seg = build_segment(&docs, SegmentTokens::V1).unwrap();
453 let dlen = u32::from_le_bytes(seg[0..4].try_into().unwrap()) as usize;
454 let dict: Vec<DictEntry> = rmp_serde::from_slice(&seg[4..4 + dlen]).unwrap();
455 let post = &seg[4 + dlen..];
456 let find = |t: &str| {
457 let e = dict.iter().find(|e| e.term == t).unwrap();
458 decode_postings(&post[e.off as usize..(e.off + e.len) as usize]).unwrap()
459 };
460 assert_eq!(find("alpha"), vec![(3, 1), (300, 1)]);
461 assert_eq!(find("beta"), vec![(3, 2), (7, 1)]);
462 assert_eq!(find("gamma"), vec![(7, 1)]);
463 }
464
465 #[test]
466 fn tokenizer_2_adds_the_parts() {
467 let t = tokenize_with(
468 Tokenizer::V2,
469 "Moved to ~/Documents/GitHub/mnemo.nosync, out of iCloud's reach; \
470 see std::fs::rename, max_bytes and PR-10b.2 in v0.9.0. It\u{2019}s done.",
471 );
472 for want in [
473 "mnemo.nosync",
474 "mnemo",
475 "nosync",
476 "icloud's",
477 "icloud",
478 "std::fs::rename",
479 "std",
480 "fs",
481 "rename",
482 "max_bytes",
483 "max",
484 "bytes",
485 "pr-10b.2",
486 "pr",
487 "10b",
488 "v0",
489 "documents",
490 "github",
491 "it",
492 ] {
493 assert!(t.contains(&want.to_string()), "{want} missing from {t:?}");
494 }
495 let v = tokenize_with(Tokenizer::V2, "v0.9.0");
497 assert!(v.contains(&"v0.9.0".to_string()) && v.contains(&"v0".to_string()));
498 assert!(!v.contains(&"9".to_string()), "{v:?}");
499 let v1 = tokenize_with(Tokenizer::V1, "mnemo.nosync iCloud's");
501 assert!(!v1.contains(&"nosync".to_string()));
502 assert!(!v1.contains(&"icloud".to_string()));
503 assert_eq!(
505 tokenize_with(Tokenizer::V2, "plain words"),
506 tokenize_with(Tokenizer::V1, "plain words")
507 );
508 }
509
510 #[test]
513 fn tokenizer_2_counts_a_term_once_per_run() {
514 let (tfs, len) = term_freqs(
515 Tokenizer::V2,
516 "mnemo.nosync key-file open_shared Mnemo::open iCloud's",
517 );
518 let tf = |t: &str| tfs.iter().find(|(x, _)| x == t).map(|(_, n)| *n);
519 for (term, n) in &tfs {
520 let want = if term == "mnemo" || term == "open" {
521 2
522 } else {
523 1
524 };
525 assert_eq!(*n, want, "{term}: {tfs:?}");
526 }
527 for t in [
528 "mnemo.nosync",
529 "nosync",
530 "key-file",
531 "key",
532 "file",
533 "open_shared",
534 "shared",
535 "mnemo::open",
536 "icloud's",
537 "icloud",
538 ] {
539 assert_eq!(tf(t), Some(1), "{t}: {tfs:?}");
540 }
541 assert_eq!(tf("mnemo"), Some(2));
542 assert_eq!(tf("open"), Some(2));
543 assert_eq!(
545 len as usize,
546 tfs.iter().map(|(_, n)| *n as usize).sum::<usize>()
547 );
548 let (v1, _) = term_freqs(Tokenizer::V1, "mnemo.nosync");
550 assert_eq!(v1, vec![("mnemo.nosync".to_string(), 2)]);
551 }
552
553 #[test]
554 fn a_marked_segment_starts_with_its_mark_and_posts_document_0() {
555 let docs = vec![(5u32, term_freqs(Tokenizer::V2, "mnemo.nosync").0)];
556 for (tokens, mark) in [
557 (SegmentTokens::V2, Some(V2_MARK)),
558 (SegmentTokens::Mixed, Some(MIXED_MARK)),
559 (SegmentTokens::V1, None),
560 ] {
561 let seg = build_segment(&docs, tokens).unwrap();
562 let dlen = u32::from_le_bytes(seg[0..4].try_into().unwrap()) as usize;
563 let dict: Vec<DictEntry> = rmp_serde::from_slice(&seg[4..4 + dlen]).unwrap();
564 let first = dict.first().map(|e| e.term.as_str());
565 assert_eq!(SegmentTokens::from_first_term(first), tokens);
566 if let Some(m) = mark {
567 let e = &dict[0];
568 assert_eq!(e.term, m);
569 let post = &seg[4 + dlen..];
570 let p = decode_postings(&post[e.off as usize..(e.off + e.len) as usize]).unwrap();
571 assert_eq!(p, vec![(0, 1)]);
572 }
573 }
574 }
575
576 #[test]
577 fn a_files_tokenizer_comes_from_its_segments() {
578 use SegmentTokens as S;
579 assert_eq!(KeywordTokenizer::of([]), KeywordTokenizer::V2);
580 assert_eq!(KeywordTokenizer::of([S::V2, S::V2]), KeywordTokenizer::V2);
581 assert_eq!(KeywordTokenizer::of([S::V1, S::V1]), KeywordTokenizer::V1);
582 assert_eq!(
583 KeywordTokenizer::of([S::V2, S::V1]),
584 KeywordTokenizer::Mixed
585 );
586 assert_eq!(KeywordTokenizer::of([S::Mixed]), KeywordTokenizer::Mixed);
587 assert_eq!(KeywordTokenizer::V1.tokenizer(), Tokenizer::V1);
588 assert_eq!(KeywordTokenizer::Mixed.tokenizer(), Tokenizer::V2);
589 }
590
591 #[test]
592 fn bm25_prefers_rarer_terms_and_shorter_docs() {
593 assert!(idf(100, 1) > idf(100, 50));
594 assert!(bm25(1, 1.0, 5, 10.0, 1.2, 0.75) > bm25(1, 1.0, 20, 10.0, 1.2, 0.75));
595 assert!(bm25(3, 1.0, 10, 10.0, 1.2, 0.75) > bm25(1, 1.0, 10, 10.0, 1.2, 0.75));
596 }
597}