packset_core/
comb.rs

1//! CombSUM / CombMNZ score fusion.
2//!
3//! Each list is min-max normalized. CombSUM sums those values; a
4//! missing list contributes 0. CombMNZ multiplies the sum by the
5//! number of lists that retrieved the id.
6//!
7//! Fox, Shaw, Combination of Multiple Searches, TREC-2, 1993.
8//! doi:10.6028/nist.sp.500-215.vt
9//! Lee, Analyses of multiple evidence combination, SIGIR 1997.
10//! doi:10.1145/258525.258587
11//! Montague, Aslam, Relevance score normalization for metasearch,
12//! CIKM 2001. doi:10.1145/502585.502657
13
14use std::collections::{HashMap, HashSet};
15use std::hash::Hash;
16
17/// One scored list. The f64 is the raw score; order is first-seen only.
18pub type ScoredBallot<T> = Vec<(T, f64)>;
19
20enum Comb {
21    Sum,
22    Mnz,
23}
24
25/// Merge scored lists by CombSUM. Ties break by first-seen id order.
26pub fn combsum_merge<T>(ballots: &[ScoredBallot<T>]) -> Vec<T>
27where
28    T: Clone + Eq + Hash,
29{
30    comb_merge(ballots, Comb::Sum)
31}
32
33/// Merge scored lists by CombMNZ. Ties break by first-seen id order.
34pub fn combmnz_merge<T>(ballots: &[ScoredBallot<T>]) -> Vec<T>
35where
36    T: Clone + Eq + Hash,
37{
38    comb_merge(ballots, Comb::Mnz)
39}
40
41fn comb_merge<T>(ballots: &[ScoredBallot<T>], kind: Comb) -> Vec<T>
42where
43    T: Clone + Eq + Hash,
44{
45    if ballots.is_empty() {
46        return Vec::new();
47    }
48    let mut scores: HashMap<T, f64> = HashMap::new();
49    let mut support: HashMap<T, usize> = HashMap::new();
50    let mut first_seen: Vec<T> = Vec::new();
51    for ballot in ballots {
52        for (id, norm) in normalize_list(ballot) {
53            if !scores.contains_key(&id) {
54                first_seen.push(id.clone());
55            }
56            *scores.entry(id.clone()).or_insert(0.0) += norm;
57            *support.entry(id).or_insert(0) += 1;
58        }
59    }
60    if matches!(kind, Comb::Mnz) {
61        for (id, score) in scores.iter_mut() {
62            *score *= *support.get(id).unwrap_or(&0) as f64;
63        }
64    }
65    let mut ranked = first_seen;
66    ranked.sort_by(|a, b| scores[b].total_cmp(&scores[a]));
67    ranked
68}
69
70fn normalize_list<T>(ballot: &ScoredBallot<T>) -> Vec<(T, f64)>
71where
72    T: Clone + Eq + Hash,
73{
74    let mut seen = HashSet::new();
75    let mut items: Vec<(T, f64)> = Vec::new();
76    for (id, raw) in ballot {
77        if !raw.is_finite() || !seen.insert(id.clone()) {
78            continue;
79        }
80        items.push((id.clone(), *raw));
81    }
82    if items.is_empty() {
83        return Vec::new();
84    }
85    let min = items.iter().map(|(_, s)| *s).fold(f64::INFINITY, f64::min);
86    let max = items
87        .iter()
88        .map(|(_, s)| *s)
89        .fold(f64::NEG_INFINITY, f64::max);
90    let span = max - min;
91    if span == 0.0 {
92        return items.into_iter().map(|(id, _)| (id, 1.0)).collect();
93    }
94    items
95        .into_iter()
96        .map(|(id, s)| (id, (s - min) / span))
97        .collect()
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn combsum_two_lists_tie_after_minmax() {
106        let a = vec![("x", 1.0), ("y", 0.2)];
107        let b = vec![("x", 0.1), ("y", 0.9)];
108        let out = combsum_merge(&[a, b]);
109        // After min-max: x = 1+0, y = 0+1. Tie, first-seen x.
110        assert_eq!(out, vec!["x", "y"]);
111    }
112
113    #[test]
114    fn combmnz_lifts_double_hit_over_single_list_champion() {
115        let a = vec![("c", 1.0), ("d", 0.4), ("low", 0.0)];
116        let b = vec![("hi", 1.0), ("d", 0.25), ("lo", 0.0)];
117        // CombSUM: c = 1.0, d = 0.4+0.25 = 0.65. Champion stays first.
118        let sum = combsum_merge(&[a.clone(), b.clone()]);
119        assert_eq!(sum[0], "c");
120        // CombMNZ: c = 1.0*1, d = 0.65*2 = 1.30. Support lifts d.
121        let mnz = combmnz_merge(&[a, b]);
122        assert_eq!(mnz[0], "d");
123    }
124
125    #[test]
126    fn missing_list_is_zero() {
127        let a = vec![("only", 1.0), ("pad", 0.0)];
128        let b: ScoredBallot<&str> = vec![];
129        let out = combsum_merge(&[a, b]);
130        assert_eq!(out[0], "only");
131    }
132}
packset_core/comb.rs

packset_core/
comb.rs
