packset_core/
rrf.rs

1//! Reciprocal Rank Fusion: score(i) = sum_b 1 / (k0 + rank_b(i)).
2//!
3//! Rank is 1-based. Missing ranks do not contribute. No score
4//! calibration. k0 is typically 60.
5//!
6//! Cormack, Clarke, Buettcher, Reciprocal Rank Fusion outperforms
7//! Condorcet and individual Rank Learning Methods, SIGIR 2009.
8//! doi:10.1145/1571941.1572114
9
10use std::collections::HashMap;
11use std::hash::Hash;
12
13use crate::borda::Ballot;
14
15/// Merge ballots by Reciprocal Rank Fusion. Ties break by first-seen id order.
16pub fn rrf_merge<T>(ballots: &[Ballot<T>], k0: usize) -> Vec<T>
17where
18    T: Clone + Eq + Hash,
19{
20    if ballots.is_empty() {
21        return Vec::new();
22    }
23    let k0 = k0 as f64;
24    let mut scores: HashMap<T, f64> = HashMap::new();
25    let mut first_seen: Vec<T> = Vec::new();
26    for ballot in ballots {
27        for (pos, id) in ballot.iter().enumerate() {
28            if !scores.contains_key(id) {
29                first_seen.push(id.clone());
30            }
31            let rank = (pos + 1) as f64;
32            *scores.entry(id.clone()).or_insert(0.0) += 1.0 / (k0 + rank);
33        }
34    }
35    let mut ranked = first_seen;
36    ranked.sort_by(|a, b| scores[b].total_cmp(&scores[a]));
37    ranked
38}
39
40#[cfg(test)]
41mod tests {
42    use super::*;
43    use crate::borda::borda_merge;
44
45    #[test]
46    fn two_lists_of_three() {
47        let a = vec!["x", "y", "z"];
48        let b = vec!["y", "x", "z"];
49        let out = rrf_merge(&[a, b], 60);
50        // x: 1/61 + 1/62, y: 1/62 + 1/61, z: 2/63. Tie x/y: first-seen x.
51        assert_eq!(out, vec!["x", "y", "z"]);
52    }
53
54    #[test]
55    fn omitted_rank_lifts_z_above_borda_last() {
56        let a = vec!["x", "y", "z"];
57        let b = vec!["y", "x", "z"];
58        let c = vec!["z"];
59        let borda = borda_merge(&[a.clone(), b.clone(), c.clone()], 3);
60        // Borda last-place dump: z stays last on the three-way tie.
61        assert_eq!(borda, vec!["x", "y", "z"]);
62        let out = rrf_merge(&[a, b, c], 60);
63        assert_eq!(out[0], "z");
64    }
65}
packset_core/rrf.rs

packset_core/
rrf.rs
