use serde::{Deserialize, Serialize};
use unicode_segmentation::UnicodeSegmentation;
use crate::error::{MnemoError, Result};
pub(crate) const TOKENIZER_V1: u8 = 1;
const MAX_TOKEN_BYTES: usize = 64;
pub(crate) fn tokenize(text: &str) -> Vec<String> {
let mut out: Vec<String> = text
.unicode_words()
.map(|w| w.to_lowercase())
.filter(|w| w.len() <= MAX_TOKEN_BYTES)
.collect();
for run in text.split_whitespace() {
let t = run.trim_matches(|c: char| !c.is_alphanumeric());
if t.len() < 2 || t.len() > MAX_TOKEN_BYTES {
continue;
}
if t.chars().any(|c| !c.is_alphanumeric()) && t.chars().any(|c| c.is_alphanumeric()) {
out.push(t.to_lowercase());
}
}
out
}
pub(crate) fn term_freqs(text: &str) -> (Vec<(String, u8)>, u16) {
let toks = tokenize(text);
let len = toks.len().min(u16::MAX as usize) as u16;
let mut map: std::collections::BTreeMap<String, u32> = std::collections::BTreeMap::new();
for t in toks {
*map.entry(t).or_default() += 1;
}
(
map.into_iter()
.map(|(t, n)| (t, n.min(255) as u8))
.collect(),
len,
)
}
pub(crate) fn bm25(tf: u8, idf: f32, doc_len: u16, avgdl: f32, k1: f32, b: f32) -> f32 {
let tf = tf as f32;
let norm = 1.0 - b + b * (doc_len as f32 / avgdl.max(1e-6));
idf * tf * (k1 + 1.0) / (tf + k1 * norm)
}
pub(crate) fn idf(n: usize, df: usize) -> f32 {
let (n, df) = (n as f32, df as f32);
(1.0 + (n - df + 0.5) / (df + 0.5)).ln()
}
#[derive(Serialize, Deserialize, Clone, Debug)]
pub(crate) struct DictEntry {
pub term: String,
pub off: u32,
pub len: u32,
}
fn put_varint(out: &mut Vec<u8>, mut v: u32) {
while v >= 0x80 {
out.push((v as u8) | 0x80);
v >>= 7;
}
out.push(v as u8);
}
pub(crate) fn decode_postings(b: &[u8]) -> Result<Vec<(u32, u8)>> {
let bad = || MnemoError::Invalid("malformed BM25 postings".into());
let mut out = Vec::new();
let mut i = 0usize;
let mut doc = 0u32;
while i < b.len() {
let mut delta = 0u32;
let mut shift = 0u32;
loop {
let byte = *b.get(i).ok_or_else(bad)?;
i += 1;
if shift > 28 {
return Err(bad());
}
delta |= ((byte & 0x7f) as u32) << shift;
if byte & 0x80 == 0 {
break;
}
shift += 7;
}
doc = doc.checked_add(delta).ok_or_else(bad)?;
let tf = *b.get(i).ok_or_else(bad)?;
i += 1;
out.push((doc, tf));
}
Ok(out)
}
pub(crate) fn build_segment(docs: &[(u32, Vec<(String, u8)>)]) -> Result<Vec<u8>> {
let mut by_term: std::collections::BTreeMap<&str, Vec<(u32, u8)>> =
std::collections::BTreeMap::new();
for (doc, terms) in docs {
for (t, tf) in terms {
by_term.entry(t.as_str()).or_default().push((*doc, *tf));
}
}
let mut dict: Vec<DictEntry> = Vec::with_capacity(by_term.len());
let mut postings: Vec<u8> = Vec::new();
for (term, mut list) in by_term {
list.sort_unstable_by_key(|&(d, _)| d);
let off = postings.len() as u32;
let mut prev = 0u32;
for (d, tf) in list {
put_varint(&mut postings, d - prev);
postings.push(tf);
prev = d;
}
dict.push(DictEntry {
term: term.to_string(),
off,
len: postings.len() as u32 - off,
});
}
let dict_bytes = rmp_serde::to_vec(&dict).map_err(|e| MnemoError::Serialize(e.to_string()))?;
let mut out = Vec::with_capacity(4 + dict_bytes.len() + postings.len());
out.extend_from_slice(&(dict_bytes.len() as u32).to_le_bytes());
out.extend_from_slice(&dict_bytes);
out.extend_from_slice(&postings);
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn tokenizer_keeps_identifiers_whole() {
let t = tokenize("Ship BP.1 in v0.9.0 (see PR-10b.2), then flush().");
for want in ["ship", "bp", "1", "bp.1", "v0.9.0", "pr-10b.2", "flush"] {
assert!(t.contains(&want.to_string()), "{want} missing from {t:?}");
}
assert!(
!t.contains(&"flush()".to_string()),
"trailing punctuation stripped"
);
assert!(tokenize("Ünïcödé Wörds").contains(&"ünïcödé".to_string()));
}
#[test]
fn segment_round_trips() {
let docs = vec![
(3u32, term_freqs("alpha beta beta").0),
(7u32, term_freqs("beta gamma").0),
(300u32, term_freqs("alpha").0),
];
let seg = build_segment(&docs).unwrap();
let dlen = u32::from_le_bytes(seg[0..4].try_into().unwrap()) as usize;
let dict: Vec<DictEntry> = rmp_serde::from_slice(&seg[4..4 + dlen]).unwrap();
let post = &seg[4 + dlen..];
let find = |t: &str| {
let e = dict.iter().find(|e| e.term == t).unwrap();
decode_postings(&post[e.off as usize..(e.off + e.len) as usize]).unwrap()
};
assert_eq!(find("alpha"), vec![(3, 1), (300, 1)]);
assert_eq!(find("beta"), vec![(3, 2), (7, 1)]);
assert_eq!(find("gamma"), vec![(7, 1)]);
}
#[test]
fn bm25_prefers_rarer_terms_and_shorter_docs() {
assert!(idf(100, 1) > idf(100, 50));
assert!(bm25(1, 1.0, 5, 10.0, 1.2, 0.75) > bm25(1, 1.0, 20, 10.0, 1.2, 0.75));
assert!(bm25(3, 1.0, 10, 10.0, 1.2, 0.75) > bm25(1, 1.0, 10, 10.0, 1.2, 0.75));
}
}