最小倒排索引

pub fn tokenize(text: &str) -> impl Iterator<Item = String> + '_ {
  text
    .split(|c: char| !c.is_alphanumeric())
    .filter(|t| !t.is_empty() && t.len() < 40)
    .map(|t| t.to_lowercase())
}

#[derive(Default)]
pub struct SegmentWriter {
  postings: HashMap<String, Vec<(u32, u32)>>, // term -> [(doc, tf)], doc ids ascending
  doc_lens: Vec<u32>,                          // doc -> number of tokens
}

impl SegmentWriter {
  pub fn add_document(&mut self, text: &str) -> u32 {
    let doc = self.doc_lens.len() as u32;
    let mut len = 0;
    for token in tokenize(text) {
      len += 1;
      let list = self.postings.entry(token).or_default();
      match list.last_mut() {
        Some((d, tf)) if *d == doc => *tf += 1,
        _ => list.push((doc, 1)),
      }
    }
    self.doc_lens.push(len);
    doc
  }
  // ...
}

[term 0 的倒排表][term 1 的倒排表]...[文档长度][词表][footer: 4 个 u64]
倒排表 = vint(n)，再 n 组 (vint(doc 差值), vint(tf))
词表   = 每个词 vint(长度) + 字节 + vint(倒排表偏移) + vint(doc_freq)

    for (term, list) in &terms {
      table.push((term.as_str(), buf.len() as u64, list.len() as u32));
      put_vint(&mut buf, list.len() as u64);
      let mut prev = 0;
      for &(doc, tf) in list {
        put_vint(&mut buf, (doc - prev) as u64);
        put_vint(&mut buf, tf as u64);
        prev = doc;
      }
    }

  fn postings(&self, term: &str) -> Option<(u32, Vec<(u32, u32)>)> {
    let i = self.terms.binary_search_by(|(t, _, _)| t.as_str().cmp(term)).ok()?;
    let (_, mut pos, df) = self.terms[i];
    let n = get_vint(&self.bytes, &mut pos);
    let mut doc = 0;
    let list = (0..n)
      .map(|_| {
        doc += get_vint(&self.bytes, &mut pos) as u32;
        (doc, get_vint(&self.bytes, &mut pos) as u32)
      })
      .collect();
    Some((df, list))
  }

  pub fn search(&self, query: &str, k: usize) -> Vec<(f32, u32)> {
    const K1: f32 = 1.2;
    const B: f32 = 0.75;
    let n = self.doc_lens.len() as f32;
    let mut scores: HashMap<u32, f32> = HashMap::new();
    for term in tokenize(query) {
      let Some((df, list)) = self.postings(&term) else { continue };
      let idf = (1.0 + (n - df as f32 + 0.5) / (df as f32 + 0.5)).ln();
      for (doc, tf) in list {
        let len_norm = K1 * (1.0 - B + B * self.doc_lens[doc as usize] as f32 / self.avg_len);
        *scores.entry(doc).or_default() += idf * (K1 + 1.0) * tf as f32 / (tf as f32 + len_norm);
      }
    }
    let mut heap = BinaryHeap::new(); // min-heap of size k via Reverse
    for (doc, score) in scores {
      heap.push(Reverse((Score(score), Reverse(doc))));
      if heap.len() > k {
        heap.pop();
      }
    }
    // ...
  }

mini: 1000 docs, segment file 461073 bytes, build 20.4 ms, search 0.008 ms
rank  mini(doc score)     tantivy(doc score)   len -> 1-byte fieldnorm
   1   225   8.24297       225   8.30196     870 -> 856
   2   948   7.49725       948   7.56005     1066 -> 1048
   3   427   6.37763       427   6.39058      55 ->  54
   4   796   5.98939       796   6.02377      87 ->  84
   5   517   5.96643       517   5.96643      31 ->  31
   6    54   5.84396        54   5.90903     679 -> 664
   7   959   5.81015       959   5.81015      23 ->  23
   8   319   4.83240       182   4.85172      42 ->  42   <- differs
   9   182   4.81217       319   4.83240     352 -> 344   <- differs
  10   762   4.72020       762   4.74418     155 -> 152