18442569236

Committed 12 Oct 2025 10:14AM UTC coverage: 20.383%. First build

Build # 18442569236

Build Type

Pull #1

github

Committed by

tamada

Commit Message

Update README and Cargo.toml files for clarity and consistency in descriptions.

Pull Request Pull Request #1: Develop

Run Details

181 of 888 new or added lines in 8 files covered. (20.38%)

181 of 888 relevant lines covered (20.38%)

0.32 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/lib/src/comparators.rs

use std::collections::{HashMap, HashSet};
use std::fmt::Display;
use std::iter::zip;
use clap::{Parser, ValueEnum};
use serde::{Serialize, Deserialize};

use crate::birthmarks::{Birthmark, BirthmarkType, Element, Info};
use crate::Result;

#[derive(Serialize, Deserialize, Parser, Debug, Clone, PartialEq, Eq, Hash, ValueEnum)]
pub enum Type {
    /// Simpson's coefficient
    Simpson,
    /// Jaccard index
    Jaccard,
    /// Dice's coefficient
    Dice,
    /// Cosine similarity
    Cosine,
    /// Longest common subsequence
    LCS,
    /// Levenshtein distance (Edit distance)
    Levenshtein,
}

impl Display for Type {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self)
    }
}

pub fn comparator(t: &Type) -> Box<dyn Comparator> {
    match t {
        Type::Simpson => Box::new(Simpson{}),
        Type::Jaccard => Box::new(Jaccard{}),
        Type::Dice => Box::new(Dice{}),
        Type::Cosine => Box::new(Cosine{}),
        Type::LCS => Box::new(LCS{}),
        Type::Levenshtein => Box::new(Levenshtein{}),
    }
}

#[derive(Serialize, Deserialize, Debug)]
pub struct Similarity {
    pub btype: BirthmarkType,
    pub a_info: Info,
    pub b_info: Info,
    pub ctype: Type,
    pub score: f64,
    pub elapsed_ms: Option<f64>,
}

pub trait Comparator {
    fn name(&self) -> String {
        self.ctype().to_string()
    }

    fn ctype(&self) -> Type;

    fn compare(&self, a: &Birthmark, b: &Birthmark) -> Result<Similarity> {
        let start = std::time::Instant::now();
        let s = match (a.len(), b.len()) {
            (0, 0) => Ok(1.0),
            (0, _) | (_, 0) => Ok(0.0),
            _ => self.compare_impl(a, b),
        };
        let elapsed = start.elapsed();
        s.map(|score| Similarity {
            btype: a.info.btype.clone(),
            a_info: a.info.clone(),
            b_info: b.info.clone(),
            ctype: self.ctype(),
            score,
            elapsed_ms: Some(elapsed.as_secs_f64() * 1000.0),
        })
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64>;
}

struct Simpson {
}

struct Jaccard {
}

struct Dice {
}

struct Cosine {
}

struct LCS {
}

struct Levenshtein {
}

impl Comparator for Simpson {
    fn ctype(&self) -> Type {
        Type::Simpson
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {
        Ok(zip(a.iter(), b.iter())
                .filter(|(a, b)| a.is_same(b))
                .count() as f64
                / a.len().min(b.len()) as f64)
    }
}

impl Comparator for Jaccard {
    fn ctype(&self) -> Type {
        Type::Jaccard
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {
        Ok(zip(a.iter(), b.iter())
                .filter(|(a, b)| a.is_same(b))
                .count() as f64
                / (a.len() + b.len() - zip(a.iter(), b.iter())
                    .filter(|(a, b)| a.is_same(b))
                    .count()) as f64)
    }
}

impl Comparator for Dice{
    fn ctype(&self) -> Type {
        Type::Dice
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {
        Ok(2.0 * zip(a.iter(), b.iter())
                .filter(|(a, b)| a.is_same(b))
                .count() as f64
                / (a.len() + b.len()) as f64)
    }
}

impl Comparator for Cosine {
    fn ctype(&self) -> Type {
        Type::Cosine
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {
        let m1 = a.freq();
        let m2 = b.freq();
        let keys = merge_keys(&m1, &m2);

        let dot_product = keys.iter()
            .map(|k| m1.get(k).unwrap_or(&0) * m2.get(k).unwrap_or(&0))
            .sum::<usize>() as f64;
        let magnitude_a = (m1.values().map(|v| v * v).sum::<usize>() as f64).sqrt();
        let magnitude_b = (m2.values().map(|v| v * v).sum::<usize>() as f64).sqrt();
        Ok(dot_product / (magnitude_a * magnitude_b))
    }
}

fn merge_keys<'a>(m1: &'a HashMap<&'a Element, usize>, m2: &'a HashMap<&'a Element, usize>) -> HashSet<&'a Element> {
    let mut keys = HashSet::new();
    for k in m1.keys() {
        keys.insert(*k);
    }
    for k in m2.keys() {
        keys.insert(*k);
    }
    keys
}

impl Comparator for LCS {
    fn ctype(&self) -> Type {
        Type::LCS
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {
        let len_a = a.len();
        let len_b = b.len();
        let lcs_len = {
            let mut dp = vec![vec![0; len_b + 1]; len_a + 1];
            for i in 1..=len_a {
                for j in 1..=len_b {
                    if a.iter().nth(i - 1).unwrap().is_same(b.iter().nth(j - 1).unwrap()) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
                    }
                }
            }
            dp[len_a][len_b]
        };
        Ok(lcs_len as f64 / len_a.max(len_b) as f64)
    }
}

impl Comparator for Levenshtein {
    fn ctype(&self) -> Type {
        Type::Levenshtein
    }

    fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {
        let len_a = a.len();
        let len_b = b.len();
        let dist = edit_distance(a, b);
        Ok(1.0 - dist as f64 / len_a.max(len_b) as f64)
    }
}

fn edit_distance(a: &Birthmark, b: &Birthmark) -> usize {
    let len_a = a.len();
    let len_b = b.len();
    let mut dp = vec![vec![0; len_b + 1]; len_a + 1];

    for i in 0..=len_a {
        dp[i][0] = i;
    }
    for j in 0..=len_b {
        dp[0][j] = j;
    }

    for i in 1..=len_a {
        for j in 1..=len_b {
            let cost = if a.iter().nth(i - 1).unwrap().is_same(b.iter().nth(j - 1).unwrap()) {
                0
            } else {
                1
            };
            dp[i][j] = *[
                dp[i - 1][j] + 1,     // Deletion
                dp[i][j - 1] + 1,     // Insertion
                dp[i - 1][j - 1] + cost, // Substitution
            ]
            .iter()
            .min()
            .unwrap();
        }
    }

    dp[len_a][len_b]
}

1	use std::collections::{HashMap, HashSet};
2	use std::fmt::Display;
3	use std::iter::zip;
4	use clap::{Parser, ValueEnum};
5	use serde::{Serialize, Deserialize};
6
7	use crate::birthmarks::{Birthmark, BirthmarkType, Element, Info};
8	use crate::Result;
9
10	#[derive(Serialize, Deserialize, Parser, Debug, Clone, PartialEq, Eq, Hash, ValueEnum)]
11	pub enum Type {
12	/// Simpson's coefficient
13	Simpson,
14	/// Jaccard index
15	Jaccard,
16	/// Dice's coefficient
17	Dice,
18	/// Cosine similarity
19	Cosine,
20	/// Longest common subsequence
21	LCS,
22	/// Levenshtein distance (Edit distance)
23	Levenshtein,
24	}
25
26	impl Display for Type {
NEW 27	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {	×
NEW 28	write!(f, "{:?}", self)	×
NEW 29	}	×
30	}
31
NEW 32	pub fn comparator(t: &Type) -> Box<dyn Comparator> {	×
NEW 33	match t {	×
NEW 34	Type::Simpson => Box::new(Simpson{}),	×
NEW 35	Type::Jaccard => Box::new(Jaccard{}),	×
NEW 36	Type::Dice => Box::new(Dice{}),	×
NEW 37	Type::Cosine => Box::new(Cosine{}),	×
NEW 38	Type::LCS => Box::new(LCS{}),	×
NEW 39	Type::Levenshtein => Box::new(Levenshtein{}),	×
40	}
NEW 41	}	×
42
43	#[derive(Serialize, Deserialize, Debug)]
44	pub struct Similarity {
45	pub btype: BirthmarkType,
46	pub a_info: Info,
47	pub b_info: Info,
48	pub ctype: Type,
49	pub score: f64,
50	pub elapsed_ms: Option<f64>,
51	}
52
53	pub trait Comparator {
NEW 54	fn name(&self) -> String {	×
NEW 55	self.ctype().to_string()	×
NEW 56	}	×
57
58	fn ctype(&self) -> Type;
59
NEW 60	fn compare(&self, a: &Birthmark, b: &Birthmark) -> Result<Similarity> {	×
NEW 61	let start = std::time::Instant::now();	×
NEW 62	let s = match (a.len(), b.len()) {	×
NEW 63	(0, 0) => Ok(1.0),	×
NEW 64	(0, _) \| (_, 0) => Ok(0.0),	×
NEW 65	_ => self.compare_impl(a, b),	×
66	};
NEW 67	let elapsed = start.elapsed();	×
NEW 68	s.map(\|score\| Similarity {	×
NEW 69	btype: a.info.btype.clone(),	×
NEW 70	a_info: a.info.clone(),	×
NEW 71	b_info: b.info.clone(),	×
NEW 72	ctype: self.ctype(),	×
NEW 73	score,	×
NEW 74	elapsed_ms: Some(elapsed.as_secs_f64() * 1000.0),	×
NEW 75	})	×
NEW 76	}	×
77
78	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64>;
79	}
80
81	struct Simpson {
82	}
83
84	struct Jaccard {
85	}
86
87	struct Dice {
88	}
89
90	struct Cosine {
91	}
92
93	struct LCS {
94	}
95
96	struct Levenshtein {
97	}
98
99	impl Comparator for Simpson {
NEW 100	fn ctype(&self) -> Type {	×
NEW 101	Type::Simpson	×
NEW 102	}	×
103
NEW 104	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {	×
NEW 105	Ok(zip(a.iter(), b.iter())	×
NEW 106	.filter(\|(a, b)\| a.is_same(b))	×
NEW 107	.count() as f64	×
NEW 108	/ a.len().min(b.len()) as f64)	×
NEW 109	}	×
110	}
111
112	impl Comparator for Jaccard {
NEW 113	fn ctype(&self) -> Type {	×
NEW 114	Type::Jaccard	×
NEW 115	}	×
116
NEW 117	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {	×
NEW 118	Ok(zip(a.iter(), b.iter())	×
NEW 119	.filter(\|(a, b)\| a.is_same(b))	×
NEW 120	.count() as f64	×
NEW 121	/ (a.len() + b.len() - zip(a.iter(), b.iter())	×
NEW 122	.filter(\|(a, b)\| a.is_same(b))	×
NEW 123	.count()) as f64)	×
NEW 124	}	×
125	}
126
127	impl Comparator for Dice{
NEW 128	fn ctype(&self) -> Type {	×
NEW 129	Type::Dice	×
NEW 130	}	×
131
NEW 132	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {	×
NEW 133	Ok(2.0 * zip(a.iter(), b.iter())	×
NEW 134	.filter(\|(a, b)\| a.is_same(b))	×
NEW 135	.count() as f64	×
NEW 136	/ (a.len() + b.len()) as f64)	×
NEW 137	}	×
138	}
139
140	impl Comparator for Cosine {
NEW 141	fn ctype(&self) -> Type {	×
NEW 142	Type::Cosine	×
NEW 143	}	×
144
NEW 145	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {	×
NEW 146	let m1 = a.freq();	×
NEW 147	let m2 = b.freq();	×
NEW 148	let keys = merge_keys(&m1, &m2);	×
149
NEW 150	let dot_product = keys.iter()	×
NEW 151	.map(\|k\| m1.get(k).unwrap_or(&0) * m2.get(k).unwrap_or(&0))	×
NEW 152	.sum::<usize>() as f64;	×
NEW 153	let magnitude_a = (m1.values().map(\|v\| v * v).sum::<usize>() as f64).sqrt();	×
NEW 154	let magnitude_b = (m2.values().map(\|v\| v * v).sum::<usize>() as f64).sqrt();	×
NEW 155	Ok(dot_product / (magnitude_a * magnitude_b))	×
NEW 156	}	×
157	}
158
NEW 159	fn merge_keys<'a>(m1: &'a HashMap<&'a Element, usize>, m2: &'a HashMap<&'a Element, usize>) -> HashSet<&'a Element> {	×
NEW 160	let mut keys = HashSet::new();	×
NEW 161	for k in m1.keys() {	×
NEW 162	keys.insert(*k);	×
NEW 163	}	×
NEW 164	for k in m2.keys() {	×
NEW 165	keys.insert(*k);	×
NEW 166	}	×
NEW 167	keys	×
NEW 168	}	×
169
170	impl Comparator for LCS {
NEW 171	fn ctype(&self) -> Type {	×
NEW 172	Type::LCS	×
NEW 173	}	×
174
NEW 175	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {	×
NEW 176	let len_a = a.len();	×
NEW 177	let len_b = b.len();	×
NEW 178	let lcs_len = {	×
NEW 179	let mut dp = vec![vec![0; len_b + 1]; len_a + 1];	×
NEW 180	for i in 1..=len_a {	×
NEW 181	for j in 1..=len_b {	×
NEW 182	if a.iter().nth(i - 1).unwrap().is_same(b.iter().nth(j - 1).unwrap()) {	×
NEW 183	dp[i][j] = dp[i - 1][j - 1] + 1;	×
NEW 184	} else {	×
NEW 185	dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);	×
NEW 186	}	×
187	}
188	}
NEW 189	dp[len_a][len_b]	×
190	};
NEW 191	Ok(lcs_len as f64 / len_a.max(len_b) as f64)	×
NEW 192	}	×
193	}
194
195	impl Comparator for Levenshtein {
NEW 196	fn ctype(&self) -> Type {	×
NEW 197	Type::Levenshtein	×
NEW 198	}	×
199
NEW 200	fn compare_impl(&self, a: &Birthmark, b: &Birthmark) -> Result<f64> {	×
NEW 201	let len_a = a.len();	×
NEW 202	let len_b = b.len();	×
NEW 203	let dist = edit_distance(a, b);	×
NEW 204	Ok(1.0 - dist as f64 / len_a.max(len_b) as f64)	×
NEW 205	}	×
206	}
207
NEW 208	fn edit_distance(a: &Birthmark, b: &Birthmark) -> usize {	×
NEW 209	let len_a = a.len();	×
NEW 210	let len_b = b.len();	×
NEW 211	let mut dp = vec![vec![0; len_b + 1]; len_a + 1];	×
212
NEW 213	for i in 0..=len_a {	×
NEW 214	dp[i][0] = i;	×
NEW 215	}	×
NEW 216	for j in 0..=len_b {	×
NEW 217	dp[0][j] = j;	×
NEW 218	}	×
219
NEW 220	for i in 1..=len_a {	×
NEW 221	for j in 1..=len_b {	×
NEW 222	let cost = if a.iter().nth(i - 1).unwrap().is_same(b.iter().nth(j - 1).unwrap()) {	×
NEW 223	0	×
224	} else {
NEW 225	1	×
226	};
NEW 227	dp[i][j] = *[	×
NEW 228	dp[i - 1][j] + 1, // Deletion	×
NEW 229	dp[i][j - 1] + 1, // Insertion	×
NEW 230	dp[i - 1][j - 1] + cost, // Substitution	×
NEW 231	]	×
NEW 232	.iter()	×
NEW 233	.min()	×
NEW 234	.unwrap();	×
235	}
236	}
237
NEW 238	dp[len_a][len_b]	×
NEW 239	}	×

tamada / oinkie / 18442569236

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous