use crate::core::search::collection_statistics::CollectionStatistics;
use crate::core::search::explanation::Explanation;
use crate::core::search::similarities_impl::similarities::{SimScorer, Similarity};
use crate::core::search::term_statistics::TermStatistics;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::number::Number;
use crate::core::util::small_float::SmallFloat;
use std::fmt;
use std::sync::LazyLock;
#[derive(Debug, Clone)]
pub struct BM25Similarity {
k1: f32,
b: f32,
discount_overlaps: bool,
}
impl Default for BM25Similarity {
fn default() -> Self {
Self {
k1: 1.2,
b: 0.75,
discount_overlaps: true,
}
}
}
impl BM25Similarity {
pub fn with_k1_b_discount(k1: f32, b: f32, discount_overlaps: bool) -> Result<Self> {
if !k1.is_finite() || k1 < 0.0 {
return Err(LuceneError::illegal_argument(format!(
"illegal k1 value: {}, must be a non-negative finite value",
k1
)));
}
if b.is_nan() || !(0.0..=1.0).contains(&b) {
return Err(LuceneError::illegal_argument(format!(
"illegal b value: {}, must be between 0 and 1",
b
)));
}
Ok(Self {
k1,
b,
discount_overlaps,
})
}
pub fn with_k1_b(k1: f32, b: f32) -> Result<Self> {
Self::with_k1_b_discount(k1, b, true)
}
pub fn with_discount(discount_overlaps: bool) -> Result<Self> {
Self::with_k1_b_discount(1.2, 0.75, discount_overlaps)
}
pub fn new() -> Result<Self> {
Ok(Self::default())
}
pub fn idf(&self, doc_freq: i64, doc_count: i64) -> f32 {
let numerator = (doc_count - doc_freq) as f64 + 0.5;
let denominator = doc_freq as f64 + 0.5;
(1.0 + numerator / denominator).ln() as f32
}
pub fn avg_field_length(&self, collection_stats: &CollectionStatistics) -> f32 {
(collection_stats.get_sum_total_term_freq() as f64 / collection_stats.get_doc_count() as f64)
as f32
}
pub fn idf_explain(
&self,
collection_stats: &CollectionStatistics,
term_stats: &TermStatistics,
) -> Explanation {
let df = term_stats.get_doc_freq();
let doc_count = collection_stats.get_doc_count();
let idf = self.idf(df, doc_count);
Explanation::match_(
idf,
"idf, computed as log(1 + (N - n + 0.5) / (n + 0.5)) from:",
vec![
Explanation::match_no_details(df, "n, number of documents containing term"),
Explanation::match_no_details(doc_count, "N, total number of documents with field"),
],
)
}
pub fn idf_explain_phrase(
&self,
collection_stats: &CollectionStatistics,
term_stats: &[TermStatistics],
) -> Explanation {
let mut idf_sum: f64 = 0.0; let mut details = Vec::with_capacity(term_stats.len());
for stat in term_stats {
let idf_expl = self.idf_explain(collection_stats, stat);
idf_sum += self.idf(stat.get_doc_freq(), collection_stats.get_doc_count()) as f64;
details.push(idf_expl);
}
Explanation::match_(idf_sum as f32, "idf, sum of:", details)
}
pub fn gen_k1(&self) -> f32 {
self.k1
}
pub fn get_b(&self) -> f32 {
self.b
}
}
impl fmt::Display for BM25Similarity {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "BM25(k1={},b={})", self.k1, self.b)
}
}
impl Similarity for BM25Similarity {
fn get_discount_overlaps(&self) -> bool {
self.discount_overlaps
}
type SimScorer = BM25Scorer;
fn scorer(
&self,
boost: f32,
collection_stats: &CollectionStatistics,
term_stats: &[TermStatistics],
) -> Result<Self::SimScorer> {
let idf = if term_stats.len() == 1 {
self.idf_explain(collection_stats, &term_stats[0])
} else {
self.idf_explain_phrase(collection_stats, term_stats)
};
let avgdl = self.avg_field_length(collection_stats);
let mut cache = [0f32; 256];
let length_table = &*LENGTH_TABLE;
for i in 0..256 {
cache[i] = 1.0 / (self.k1 * ((1.0 - self.b) + self.b * length_table[i] / avgdl));
}
BM25Scorer::new(boost, self.k1, self.b, idf, avgdl, cache)
}
}
pub static LENGTH_TABLE: LazyLock<[f32; 256]> = LazyLock::new(|| {
let mut table = [0.0; 256];
for (i, out) in table.iter_mut().take(256).enumerate() {
*out = expect_invariant!(
SmallFloat::byte4_to_int(i as u8),
"every u8 value is valid for the BM25 length decoding table"
) as f32;
}
table
});
pub struct BM25Scorer {
boost: f32,
k1: f32,
b: f32,
idf: Explanation,
avgdl: f32,
cache: [f32; 256],
weight: f32,
}
impl BM25Scorer {
pub fn new(
boost: f32,
k1: f32,
b: f32,
idf: Explanation,
avgdl: f32,
cache: [f32; 256],
) -> Result<Self> {
let idf_value = idf.get_value().to_f32().ok_or_else(|| {
LuceneError::illegal_argument(format!("cannot convert to f32: {}", idf.get_value()))
})?;
Ok(Self {
boost,
k1,
b,
idf,
avgdl,
cache,
weight: boost * idf_value,
})
}
fn explain_tf(&self, freq: Explanation, norm: i64) -> Result<Explanation> {
let mut subs = Vec::with_capacity(5);
let freq_value = freq.get_value().to_f32().ok_or_else(|| {
LuceneError::illegal_argument(format!("cannot convert to f32: {}", freq.get_value()))
})?;
subs.push(freq);
subs.push(Explanation::match_no_details(
self.k1,
"k1, term saturation parameter",
));
let doclen = LENGTH_TABLE[(norm as u8) as usize];
subs.push(Explanation::match_no_details(
self.b,
"b, length normalization parameter",
));
if (norm & 0xFF) > 39 {
subs.push(Explanation::match_no_details(
doclen,
"dl, length of field (approximate)",
));
} else {
subs.push(Explanation::match_no_details(doclen, "dl, length of field"));
}
subs.push(Explanation::match_no_details(
self.avgdl,
"avgdl, average length of field",
));
let norm_inverse = 1.0 / (self.k1 * ((1.0 - self.b) + self.b * doclen / self.avgdl));
let tf_val = 1.0 - 1.0 / (1.0 + freq_value * norm_inverse);
Ok(Explanation::match_(
tf_val,
"tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl)) from:",
subs,
))
}
fn explain_constant_factors(&self) -> Vec<Explanation> {
let mut subs = Vec::with_capacity(3);
if self.boost != 1.0 {
subs.push(Explanation::match_no_details(
Number::F32(self.boost),
"boost",
));
}
subs.push(self.idf.clone());
subs
}
}
impl SimScorer for BM25Scorer {
fn score(&self, freq: f32, encoded_norm: i64) -> f32 {
let norm_inverse = self.cache[(encoded_norm as u8) as usize];
self.weight - self.weight / (1.0 + freq * norm_inverse)
}
fn explain(&self, freq: Explanation, encoded_norm: i64) -> Result<Explanation> {
let mut subs = self.explain_constant_factors();
let freq_value = freq.get_value().to_f32().ok_or_else(|| {
LuceneError::illegal_argument(format!("cannot convert to f32: {}", freq.get_value()))
})?;
let description = format!(
"score(freq={}), computed as boost * idf * tf from:",
freq.get_value()
);
let tf_expl = self.explain_tf(freq, encoded_norm)?;
subs.push(tf_expl);
let norm_inverse = self.cache[(encoded_norm as u8) as usize];
let score_val = self.weight - self.weight / (1.0 + freq_value * norm_inverse);
Ok(Explanation::match_(score_val, description, subs))
}
}