use std::cmp::Ordering;
pub fn shingle_jaccard(a: &str, b: &str) -> f32 {
const WIDTH: usize = 5;
let a = a.to_lowercase();
let b = b.to_lowercase();
let a_words: Vec<&str> = a.split_whitespace().collect();
let b_words: Vec<&str> = b.split_whitespace().collect();
if a_words.is_empty() && b_words.is_empty() {
return 1.0;
}
let width = if a_words.len() < WIDTH || b_words.len() < WIDTH {
1
} else {
WIDTH
};
let a_set = shingles(&a_words, width);
let b_set = shingles(&b_words, width);
let (mut i, mut j, mut shared) = (0, 0, 0usize);
while let (Some(x), Some(y)) = (a_set.get(i), b_set.get(j)) {
match x.cmp(y) {
Ordering::Less => i += 1,
Ordering::Greater => j += 1,
Ordering::Equal => {
shared += 1;
i += 1;
j += 1;
}
}
}
let union = a_set.len() + b_set.len() - shared;
if union == 0 {
return 1.0;
}
shared as f32 / union as f32
}
fn shingles<'s, 'w>(words: &'s [&'w str], width: usize) -> Vec<&'s [&'w str]> {
let mut out: Vec<&[&str]> = words.windows(width.max(1)).collect();
out.sort_unstable();
out.dedup();
out
}
pub fn byte_ratio(a: usize, b: usize) -> f32 {
let (small, large) = if a <= b { (a, b) } else { (b, a) };
if large == 0 {
return 1.0;
}
(small as f64 / large as f64) as f32
}
pub fn fields_ok(
requested: &[&str],
baseline: &[(&str, &str)],
candidate: &[(&str, &str)],
) -> bool {
requested.iter().all(|name| {
let Some(got) = lookup(candidate, name).map(normalize) else {
return false;
};
if got.is_empty() {
return false;
}
match lookup(baseline, name).map(normalize) {
Some(want) if !want.is_empty() => got.contains(&want),
_ => true,
}
})
}
fn lookup<'v>(fields: &[(&str, &'v str)], name: &str) -> Option<&'v str> {
fields
.iter()
.find(|(field, _)| *field == name)
.map(|(_, value)| *value)
}
fn normalize(text: &str) -> String {
let mut out = String::with_capacity(text.len());
for word in text.split_whitespace() {
if !out.is_empty() {
out.push(' ');
}
out.push_str(&word.to_lowercase());
}
out
}
#[cfg(test)]
mod tests {
#![allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
clippy::unreachable,
clippy::indexing_slicing,
clippy::string_slice
)]
use super::*;
fn article(with_footer: bool) -> String {
let mut text = String::new();
for n in 0..60 {
text.push_str(&format!(
"Paragraph {n} says the harbour rebuilt pier number {n} after winter storms. "
));
}
if with_footer {
text.push_str(
"Copyright the harbour gazette, all rights reserved, contact us, privacy.",
);
}
text
}
#[test]
fn identical_text_is_one() {
let text = article(true);
assert_eq!(shingle_jaccard(&text, &text), 1.0);
let shouted = text.to_uppercase().replace(' ', " \n ");
assert_eq!(shingle_jaccard(&text, &shouted), 1.0);
assert_eq!(shingle_jaccard("", " "), 1.0);
}
#[test]
fn disjoint_text_is_zero() {
assert_eq!(
shingle_jaccard(
&article(false),
"entirely unrelated words about something else here"
),
0.0
);
assert_eq!(shingle_jaccard("one two", "three four"), 0.0);
assert_eq!(shingle_jaccard("", "words"), 0.0);
}
#[test]
fn a_page_missing_its_footer_stays_above_0_8() {
let score = shingle_jaccard(&article(true), &article(false));
assert!(score > 0.8 && score < 1.0, "{score}");
let full = article(true);
let half: String = full
.split_whitespace()
.take(120)
.collect::<Vec<_>>()
.join(" ");
assert!(shingle_jaccard(&full, &half) < 0.5);
}
#[test]
fn short_texts_compare_word_sets() {
assert_eq!(shingle_jaccard("price 20 usd", "usd price 20"), 1.0);
assert_eq!(shingle_jaccard("a b c d", "a b"), 0.5);
}
#[test]
fn byte_ratio_is_the_smaller_over_the_larger() {
assert_eq!(byte_ratio(0, 0), 1.0);
assert_eq!(byte_ratio(100, 0), 0.0);
assert_eq!(byte_ratio(50, 200), 0.25);
assert_eq!(byte_ratio(200, 50), 0.25);
assert!(byte_ratio(usize::MAX, usize::MAX - 1).is_finite());
}
#[test]
fn a_field_dropped_fails() {
let requested = ["title", "price"];
let baseline = [("title", "Blue Kettle"), ("price", "20 USD")];
assert!(fields_ok(&requested, &baseline, &baseline));
assert!(fields_ok(
&requested,
&baseline,
&[
("title", "blue kettle, 1.7 litres"),
("price", " 20 usd ")
]
));
assert!(!fields_ok(
&requested,
&baseline,
&[("title", "Blue Kettle")]
));
assert!(!fields_ok(
&requested,
&baseline,
&[("title", "Blue Kettle"), ("price", " ")]
));
assert!(!fields_ok(
&requested,
&baseline,
&[("title", "Blue Kettle"), ("price", "25 USD")]
));
assert!(fields_ok(&["sku"], &[], &[("sku", "A1")]));
assert!(fields_ok(&[], &baseline, &[]));
}
}