diff options
Diffstat (limited to 'src/lib.rs')
| -rw-r--r-- | src/lib.rs | 1307 |
1 files changed, 1307 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..8118277 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,1307 @@ +//! This library implements string similarity metrics. + +#![forbid(unsafe_code)] +#![allow( + // these casts are sometimes needed. They restrict the length of input iterators + // but there isn't really any way around this except for always working with + // 128 bit types + clippy::cast_possible_wrap, + clippy::cast_sign_loss, + clippy::cast_precision_loss, + // not practical + clippy::needless_pass_by_value, + clippy::similar_names, + // noisy + clippy::missing_errors_doc, + clippy::missing_panics_doc, + clippy::must_use_candidate, + // todo https://github.com/rapidfuzz/strsim-rs/issues/59 + clippy::range_plus_one +)] + +use std::char; +use std::cmp::{max, min}; +use std::collections::HashMap; +use std::convert::TryFrom; +use std::error::Error; +use std::fmt::{self, Display, Formatter}; +use std::hash::Hash; +use std::mem; +use std::str::Chars; + +#[derive(Debug, PartialEq)] +pub enum StrSimError { + DifferentLengthArgs, +} + +impl Display for StrSimError { + fn fmt(&self, fmt: &mut Formatter) -> Result<(), fmt::Error> { + let text = match self { + StrSimError::DifferentLengthArgs => "Differing length arguments provided", + }; + + write!(fmt, "{text}") + } +} + +impl Error for StrSimError {} + +pub type HammingResult = Result<usize, StrSimError>; + +/// Calculates the number of positions in the two sequences where the elements +/// differ. Returns an error if the sequences have different lengths. +pub fn generic_hamming<Iter1, Iter2, Elem1, Elem2>(a: Iter1, b: Iter2) -> HammingResult +where + Iter1: IntoIterator<Item = Elem1>, + Iter2: IntoIterator<Item = Elem2>, + Elem1: PartialEq<Elem2>, +{ + let (mut ita, mut itb) = (a.into_iter(), b.into_iter()); + let mut count = 0; + loop { + match (ita.next(), itb.next()) { + (Some(x), Some(y)) => { + if x != y { + count += 1; + } + } + (None, None) => return Ok(count), + _ => return Err(StrSimError::DifferentLengthArgs), + } + } +} + +/// Calculates the number of positions in the two strings where the characters +/// differ. Returns an error if the strings have different lengths. +/// +/// ``` +/// use strsim::{hamming, StrSimError::DifferentLengthArgs}; +/// +/// assert_eq!(Ok(3), hamming("hamming", "hammers")); +/// +/// assert_eq!(Err(DifferentLengthArgs), hamming("hamming", "ham")); +/// ``` +pub fn hamming(a: &str, b: &str) -> HammingResult { + generic_hamming(a.chars(), b.chars()) +} + +/// Calculates the Jaro similarity between two sequences. The returned value +/// is between 0.0 and 1.0 (higher value means more similar). +pub fn generic_jaro<'a, 'b, Iter1, Iter2, Elem1, Elem2>(a: &'a Iter1, b: &'b Iter2) -> f64 +where + &'a Iter1: IntoIterator<Item = Elem1>, + &'b Iter2: IntoIterator<Item = Elem2>, + Elem1: PartialEq<Elem2>, +{ + let a_len = a.into_iter().count(); + let b_len = b.into_iter().count(); + + if a_len == 0 && b_len == 0 { + return 1.0; + } else if a_len == 0 || b_len == 0 { + return 0.0; + } + + let mut search_range = max(a_len, b_len) / 2; + search_range = search_range.saturating_sub(1); + + // combine memory allocations to reduce runtime + let mut flags_memory = vec![false; a_len + b_len]; + let (a_flags, b_flags) = flags_memory.split_at_mut(a_len); + + let mut matches = 0_usize; + + for (i, a_elem) in a.into_iter().enumerate() { + // prevent integer wrapping + let min_bound = if i > search_range { + i - search_range + } else { + 0 + }; + + let max_bound = min(b_len, i + search_range + 1); + + for (j, b_elem) in b.into_iter().enumerate().take(max_bound) { + if min_bound <= j && a_elem == b_elem && !b_flags[j] { + a_flags[i] = true; + b_flags[j] = true; + matches += 1; + break; + } + } + } + + let mut transpositions = 0_usize; + if matches != 0 { + let mut b_iter = b_flags.iter().zip(b); + for (a_flag, ch1) in a_flags.iter().zip(a) { + if *a_flag { + loop { + if let Some((b_flag, ch2)) = b_iter.next() { + if !*b_flag { + continue; + } + + if ch1 != ch2 { + transpositions += 1; + } + break; + } + } + } + } + } + transpositions /= 2; + + if matches == 0 { + 0.0 + } else { + ((matches as f64 / a_len as f64) + + (matches as f64 / b_len as f64) + + ((matches - transpositions) as f64 / matches as f64)) + / 3.0 + } +} + +struct StringWrapper<'a>(&'a str); + +impl<'a, 'b> IntoIterator for &'a StringWrapper<'b> { + type Item = char; + type IntoIter = Chars<'b>; + + fn into_iter(self) -> Self::IntoIter { + self.0.chars() + } +} + +/// Calculates the Jaro similarity between two strings. The returned value +/// is between 0.0 and 1.0 (higher value means more similar). +/// +/// ``` +/// use strsim::jaro; +/// +/// assert!((0.392 - jaro("Friedrich Nietzsche", "Jean-Paul Sartre")).abs() < +/// 0.001); +/// ``` +pub fn jaro(a: &str, b: &str) -> f64 { + generic_jaro(&StringWrapper(a), &StringWrapper(b)) +} + +/// Like Jaro but gives a boost to sequences that have a common prefix. +pub fn generic_jaro_winkler<'a, 'b, Iter1, Iter2, Elem1, Elem2>(a: &'a Iter1, b: &'b Iter2) -> f64 +where + &'a Iter1: IntoIterator<Item = Elem1>, + &'b Iter2: IntoIterator<Item = Elem2>, + Elem1: PartialEq<Elem2>, +{ + let sim = generic_jaro(a, b); + + if sim > 0.7 { + let prefix_length = a + .into_iter() + .take(4) + .zip(b) + .take_while(|(a_elem, b_elem)| a_elem == b_elem) + .count(); + + sim + 0.1 * prefix_length as f64 * (1.0 - sim) + } else { + sim + } +} + +/// Like Jaro but gives a boost to strings that have a common prefix. +/// +/// ``` +/// use strsim::jaro_winkler; +/// +/// assert!((0.866 - jaro_winkler("cheeseburger", "cheese fries")).abs() < +/// 0.001); +/// ``` +pub fn jaro_winkler(a: &str, b: &str) -> f64 { + generic_jaro_winkler(&StringWrapper(a), &StringWrapper(b)) +} + +/// Calculates the minimum number of insertions, deletions, and substitutions +/// required to change one sequence into the other. +/// +/// ``` +/// use strsim::generic_levenshtein; +/// +/// assert_eq!(3, generic_levenshtein(&[1,2,3], &[1,2,3,4,5,6])); +/// ``` +pub fn generic_levenshtein<'a, 'b, Iter1, Iter2, Elem1, Elem2>(a: &'a Iter1, b: &'b Iter2) -> usize +where + &'a Iter1: IntoIterator<Item = Elem1>, + &'b Iter2: IntoIterator<Item = Elem2>, + Elem1: PartialEq<Elem2>, +{ + let b_len = b.into_iter().count(); + + let mut cache: Vec<usize> = (1..b_len + 1).collect(); + + let mut result = b_len; + + for (i, a_elem) in a.into_iter().enumerate() { + result = i + 1; + let mut distance_b = i; + + for (j, b_elem) in b.into_iter().enumerate() { + let cost = usize::from(a_elem != b_elem); + let distance_a = distance_b + cost; + distance_b = cache[j]; + result = min(result + 1, min(distance_a, distance_b + 1)); + cache[j] = result; + } + } + + result +} + +/// Calculates the minimum number of insertions, deletions, and substitutions +/// required to change one string into the other. +/// +/// ``` +/// use strsim::levenshtein; +/// +/// assert_eq!(3, levenshtein("kitten", "sitting")); +/// ``` +pub fn levenshtein(a: &str, b: &str) -> usize { + generic_levenshtein(&StringWrapper(a), &StringWrapper(b)) +} + +/// Calculates a normalized score of the Levenshtein algorithm between 0.0 and +/// 1.0 (inclusive), where 1.0 means the strings are the same. +/// +/// ``` +/// use strsim::normalized_levenshtein; +/// +/// assert!((normalized_levenshtein("kitten", "sitting") - 0.57142).abs() < 0.00001); +/// assert!((normalized_levenshtein("", "") - 1.0).abs() < 0.00001); +/// assert!(normalized_levenshtein("", "second").abs() < 0.00001); +/// assert!(normalized_levenshtein("first", "").abs() < 0.00001); +/// assert!((normalized_levenshtein("string", "string") - 1.0).abs() < 0.00001); +/// ``` +pub fn normalized_levenshtein(a: &str, b: &str) -> f64 { + if a.is_empty() && b.is_empty() { + return 1.0; + } + 1.0 - (levenshtein(a, b) as f64) / (a.chars().count().max(b.chars().count()) as f64) +} + +/// Like Levenshtein but allows for adjacent transpositions. Each substring can +/// only be edited once. +/// +/// ``` +/// use strsim::osa_distance; +/// +/// assert_eq!(3, osa_distance("ab", "bca")); +/// ``` +pub fn osa_distance(a: &str, b: &str) -> usize { + let b_len = b.chars().count(); + // 0..=b_len behaves like 0..b_len.saturating_add(1) which could be a different size + // this leads to significantly worse code gen when swapping the vectors below + let mut prev_two_distances: Vec<usize> = (0..b_len + 1).collect(); + let mut prev_distances: Vec<usize> = (0..b_len + 1).collect(); + let mut curr_distances: Vec<usize> = vec![0; b_len + 1]; + + let mut prev_a_char = char::MAX; + let mut prev_b_char = char::MAX; + + for (i, a_char) in a.chars().enumerate() { + curr_distances[0] = i + 1; + + for (j, b_char) in b.chars().enumerate() { + let cost = usize::from(a_char != b_char); + curr_distances[j + 1] = min( + curr_distances[j] + 1, + min(prev_distances[j + 1] + 1, prev_distances[j] + cost), + ); + if i > 0 && j > 0 && a_char != b_char && a_char == prev_b_char && b_char == prev_a_char + { + curr_distances[j + 1] = min(curr_distances[j + 1], prev_two_distances[j - 1] + 1); + } + + prev_b_char = b_char; + } + + mem::swap(&mut prev_two_distances, &mut prev_distances); + mem::swap(&mut prev_distances, &mut curr_distances); + prev_a_char = a_char; + } + + // access prev_distances instead of curr_distances since we swapped + // them above. In case a is empty this would still contain the correct value + // from initializing the last element to b_len + prev_distances[b_len] +} + +/* Returns the final index for a value in a single vector that represents a fixed +2d grid */ +fn flat_index(i: usize, j: usize, width: usize) -> usize { + j * width + i +} + +/// Like optimal string alignment, but substrings can be edited an unlimited +/// number of times, and the triangle inequality holds. +/// +/// ``` +/// use strsim::generic_damerau_levenshtein; +/// +/// assert_eq!(2, generic_damerau_levenshtein(&[1,2], &[2,3,1])); +/// ``` +pub fn generic_damerau_levenshtein<Elem>(a_elems: &[Elem], b_elems: &[Elem]) -> usize +where + Elem: Eq + Hash + Clone, +{ + let a_len = a_elems.len(); + let b_len = b_elems.len(); + + if a_len == 0 { + return b_len; + } + if b_len == 0 { + return a_len; + } + + let width = a_len + 2; + let mut distances = vec![0; (a_len + 2) * (b_len + 2)]; + let max_distance = a_len + b_len; + distances[0] = max_distance; + + for i in 0..(a_len + 1) { + distances[flat_index(i + 1, 0, width)] = max_distance; + distances[flat_index(i + 1, 1, width)] = i; + } + + for j in 0..(b_len + 1) { + distances[flat_index(0, j + 1, width)] = max_distance; + distances[flat_index(1, j + 1, width)] = j; + } + + let mut elems: HashMap<Elem, usize> = HashMap::with_capacity(64); + + for i in 1..(a_len + 1) { + let mut db = 0; + + for j in 1..(b_len + 1) { + let k = match elems.get(&b_elems[j - 1]) { + Some(&value) => value, + None => 0, + }; + + let insertion_cost = distances[flat_index(i, j + 1, width)] + 1; + let deletion_cost = distances[flat_index(i + 1, j, width)] + 1; + let transposition_cost = + distances[flat_index(k, db, width)] + (i - k - 1) + 1 + (j - db - 1); + + let mut substitution_cost = distances[flat_index(i, j, width)] + 1; + if a_elems[i - 1] == b_elems[j - 1] { + db = j; + substitution_cost -= 1; + } + + distances[flat_index(i + 1, j + 1, width)] = min( + substitution_cost, + min(insertion_cost, min(deletion_cost, transposition_cost)), + ); + } + + elems.insert(a_elems[i - 1].clone(), i); + } + + distances[flat_index(a_len + 1, b_len + 1, width)] +} + +#[derive(Clone, Copy, PartialEq, Eq)] +struct RowId { + val: isize, +} + +impl Default for RowId { + fn default() -> Self { + Self { val: -1 } + } +} + +#[derive(Default, Clone)] +struct GrowingHashmapMapElemChar<ValueType> { + key: u32, + value: ValueType, +} + +/// specialized hashmap to store user provided types +/// this implementation relies on a couple of base assumptions in order to simplify the implementation +/// - the hashmap does not have an upper limit of included items +/// - the default value for the `ValueType` can be used as a dummy value to indicate an empty cell +/// - elements can't be removed +/// - only allocates memory on first write access. +/// This improves performance for hashmaps that are never written to +struct GrowingHashmapChar<ValueType> { + used: i32, + fill: i32, + mask: i32, + map: Option<Vec<GrowingHashmapMapElemChar<ValueType>>>, +} + +impl<ValueType> Default for GrowingHashmapChar<ValueType> +where + ValueType: Default + Clone + Eq, +{ + fn default() -> Self { + Self { + used: 0, + fill: 0, + mask: -1, + map: None, + } + } +} + +impl<ValueType> GrowingHashmapChar<ValueType> +where + ValueType: Default + Clone + Eq + Copy, +{ + fn get(&self, key: u32) -> ValueType { + self.map + .as_ref() + .map_or_else(|| Default::default(), |map| map[self.lookup(key)].value) + } + + fn get_mut(&mut self, key: u32) -> &mut ValueType { + if self.map.is_none() { + self.allocate(); + } + + let mut i = self.lookup(key); + if self + .map + .as_ref() + .expect("map should have been created above")[i] + .value + == Default::default() + { + self.fill += 1; + // resize when 2/3 full + if self.fill * 3 >= (self.mask + 1) * 2 { + self.grow((self.used + 1) * 2); + i = self.lookup(key); + } + + self.used += 1; + } + + let elem = &mut self + .map + .as_mut() + .expect("map should have been created above")[i]; + elem.key = key; + &mut elem.value + } + + fn allocate(&mut self) { + self.mask = 8 - 1; + self.map = Some(vec![GrowingHashmapMapElemChar::default(); 8]); + } + + /// lookup key inside the hashmap using a similar collision resolution + /// strategy to `CPython` and `Ruby` + fn lookup(&self, key: u32) -> usize { + let hash = key; + let mut i = hash as usize & self.mask as usize; + + let map = self + .map + .as_ref() + .expect("callers have to ensure map is allocated"); + + if map[i].value == Default::default() || map[i].key == key { + return i; + } + + let mut perturb = key; + loop { + i = (i * 5 + perturb as usize + 1) & self.mask as usize; + + if map[i].value == Default::default() || map[i].key == key { + return i; + } + + perturb >>= 5; + } + } + + fn grow(&mut self, min_used: i32) { + let mut new_size = self.mask + 1; + while new_size <= min_used { + new_size <<= 1; + } + + self.fill = self.used; + self.mask = new_size - 1; + + let old_map = std::mem::replace( + self.map + .as_mut() + .expect("callers have to ensure map is allocated"), + vec![GrowingHashmapMapElemChar::<ValueType>::default(); new_size as usize], + ); + + for elem in old_map { + if elem.value != Default::default() { + let j = self.lookup(elem.key); + let new_elem = &mut self.map.as_mut().expect("map created above")[j]; + new_elem.key = elem.key; + new_elem.value = elem.value; + self.used -= 1; + if self.used == 0 { + break; + } + } + } + + self.used = self.fill; + } +} + +struct HybridGrowingHashmapChar<ValueType> { + map: GrowingHashmapChar<ValueType>, + extended_ascii: [ValueType; 256], +} + +impl<ValueType> HybridGrowingHashmapChar<ValueType> +where + ValueType: Default + Clone + Copy + Eq, +{ + fn get(&self, key: char) -> ValueType { + let value = key as u32; + if value <= 255 { + let val_u8 = u8::try_from(value).expect("we check the bounds above"); + self.extended_ascii[usize::from(val_u8)] + } else { + self.map.get(value) + } + } + + fn get_mut(&mut self, key: char) -> &mut ValueType { + let value = key as u32; + if value <= 255 { + let val_u8 = u8::try_from(value).expect("we check the bounds above"); + &mut self.extended_ascii[usize::from(val_u8)] + } else { + self.map.get_mut(value) + } + } +} + +impl<ValueType> Default for HybridGrowingHashmapChar<ValueType> +where + ValueType: Default + Clone + Copy + Eq, +{ + fn default() -> Self { + HybridGrowingHashmapChar { + map: GrowingHashmapChar::default(), + extended_ascii: [Default::default(); 256], + } + } +} + +fn damerau_levenshtein_impl<Iter1, Iter2>(s1: Iter1, len1: usize, s2: Iter2, len2: usize) -> usize +where + Iter1: Iterator<Item = char> + Clone, + Iter2: Iterator<Item = char> + Clone, +{ + // The implementations is based on the paper + // `Linear space string correction algorithm using the Damerau-Levenshtein distance` + // from Chunchun Zhao and Sartaj Sahni + // + // It has a runtime complexity of `O(N*M)` and a memory usage of `O(N+M)`. + let max_val = max(len1, len2) as isize + 1; + + let mut last_row_id = HybridGrowingHashmapChar::<RowId>::default(); + + let size = len2 + 2; + let mut fr = vec![max_val; size]; + let mut r1 = vec![max_val; size]; + let mut r: Vec<isize> = (max_val..max_val + 1) + .chain(0..(size - 1) as isize) + .collect(); + + for (i, ch1) in s1.enumerate().map(|(i, ch1)| (i + 1, ch1)) { + mem::swap(&mut r, &mut r1); + let mut last_col_id: isize = -1; + let mut last_i2l1 = r[1]; + r[1] = i as isize; + let mut t = max_val; + + for (j, ch2) in s2.clone().enumerate().map(|(j, ch2)| (j + 1, ch2)) { + let diag = r1[j] + isize::from(ch1 != ch2); + let left = r[j] + 1; + let up = r1[j + 1] + 1; + let mut temp = min(diag, min(left, up)); + + if ch1 == ch2 { + last_col_id = j as isize; // last occurence of s1_i + fr[j + 1] = r1[j - 1]; // save H_k-1,j-2 + t = last_i2l1; // save H_i-2,l-1 + } else { + let k = last_row_id.get(ch2).val; + let l = last_col_id; + + if j as isize - l == 1 { + let transpose = fr[j + 1] + (i as isize - k); + temp = min(temp, transpose); + } else if i as isize - k == 1 { + let transpose = t + (j as isize - l); + temp = min(temp, transpose); + } + } + + last_i2l1 = r[j + 1]; + r[j + 1] = temp; + } + last_row_id.get_mut(ch1).val = i as isize; + } + + r[len2 + 1] as usize +} + +/// Like optimal string alignment, but substrings can be edited an unlimited +/// number of times, and the triangle inequality holds. +/// +/// ``` +/// use strsim::damerau_levenshtein; +/// +/// assert_eq!(2, damerau_levenshtein("ab", "bca")); +/// ``` +pub fn damerau_levenshtein(a: &str, b: &str) -> usize { + damerau_levenshtein_impl(a.chars(), a.chars().count(), b.chars(), b.chars().count()) +} + +/// Calculates a normalized score of the Damerau–Levenshtein algorithm between +/// 0.0 and 1.0 (inclusive), where 1.0 means the strings are the same. +/// +/// ``` +/// use strsim::normalized_damerau_levenshtein; +/// +/// assert!((normalized_damerau_levenshtein("levenshtein", "löwenbräu") - 0.27272).abs() < 0.00001); +/// assert!((normalized_damerau_levenshtein("", "") - 1.0).abs() < 0.00001); +/// assert!(normalized_damerau_levenshtein("", "flower").abs() < 0.00001); +/// assert!(normalized_damerau_levenshtein("tree", "").abs() < 0.00001); +/// assert!((normalized_damerau_levenshtein("sunglasses", "sunglasses") - 1.0).abs() < 0.00001); +/// ``` +pub fn normalized_damerau_levenshtein(a: &str, b: &str) -> f64 { + if a.is_empty() && b.is_empty() { + return 1.0; + } + + let len1 = a.chars().count(); + let len2 = b.chars().count(); + let dist = damerau_levenshtein_impl(a.chars(), len1, b.chars(), len2); + 1.0 - (dist as f64) / (max(len1, len2) as f64) +} + +/// Returns an Iterator of char tuples. +fn bigrams(s: &str) -> impl Iterator<Item = (char, char)> + '_ { + s.chars().zip(s.chars().skip(1)) +} + +/// Calculates a Sørensen-Dice similarity distance using bigrams. +/// See <https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient>. +/// +/// ``` +/// use strsim::sorensen_dice; +/// +/// assert_eq!(1.0, sorensen_dice("", "")); +/// assert_eq!(0.0, sorensen_dice("", "a")); +/// assert_eq!(0.0, sorensen_dice("french", "quebec")); +/// assert_eq!(1.0, sorensen_dice("ferris", "ferris")); +/// assert_eq!(0.8888888888888888, sorensen_dice("feris", "ferris")); +/// ``` +pub fn sorensen_dice(a: &str, b: &str) -> f64 { + // implementation guided by + // https://github.com/aceakash/string-similarity/blob/f83ba3cd7bae874c20c429774e911ae8cff8bced/src/index.js#L6 + + let a: String = a.chars().filter(|&x| !char::is_whitespace(x)).collect(); + let b: String = b.chars().filter(|&x| !char::is_whitespace(x)).collect(); + + if a == b { + return 1.0; + } + + if a.len() < 2 || b.len() < 2 { + return 0.0; + } + + let mut a_bigrams: HashMap<(char, char), usize> = HashMap::new(); + + for bigram in bigrams(&a) { + *a_bigrams.entry(bigram).or_insert(0) += 1; + } + + let mut intersection_size = 0_usize; + + for bigram in bigrams(&b) { + a_bigrams.entry(bigram).and_modify(|bi| { + if *bi > 0 { + *bi -= 1; + intersection_size += 1; + } + }); + } + + (2 * intersection_size) as f64 / (a.len() + b.len() - 2) as f64 +} + +#[cfg(test)] +mod tests { + use super::*; + + macro_rules! assert_delta { + ($x:expr, $y:expr) => { + assert_delta!($x, $y, 1e-5); + }; + ($x:expr, $y:expr, $d:expr) => { + if ($x - $y).abs() > $d { + panic!( + "assertion failed: actual: `{}`, expected: `{}`: \ + actual not within < {} of expected", + $x, $y, $d + ); + } + }; + } + + #[test] + fn bigrams_iterator() { + let mut bi = bigrams("abcde"); + + assert_eq!(Some(('a', 'b')), bi.next()); + assert_eq!(Some(('b', 'c')), bi.next()); + assert_eq!(Some(('c', 'd')), bi.next()); + assert_eq!(Some(('d', 'e')), bi.next()); + assert_eq!(None, bi.next()); + } + + fn assert_hamming_dist(dist: usize, str1: &str, str2: &str) { + assert_eq!(Ok(dist), hamming(str1, str2)); + } + + #[test] + fn hamming_empty() { + assert_hamming_dist(0, "", "") + } + + #[test] + fn hamming_same() { + assert_hamming_dist(0, "hamming", "hamming") + } + + #[test] + fn hamming_numbers() { + assert_eq!(Ok(1), generic_hamming(&[1, 2, 4], &[1, 2, 3])); + } + + #[test] + fn hamming_diff() { + assert_hamming_dist(3, "hamming", "hammers") + } + + #[test] + fn hamming_diff_multibyte() { + assert_hamming_dist(2, "hamming", "h香mmüng"); + } + + #[test] + fn hamming_unequal_length() { + assert_eq!( + Err(StrSimError::DifferentLengthArgs), + generic_hamming("ham".chars(), "hamming".chars()) + ); + } + + #[test] + fn hamming_names() { + assert_hamming_dist(14, "Friedrich Nietzs", "Jean-Paul Sartre") + } + + #[test] + fn jaro_both_empty() { + assert_eq!(1.0, jaro("", "")); + } + + #[test] + fn jaro_first_empty() { + assert_eq!(0.0, jaro("", "jaro")); + } + + #[test] + fn jaro_second_empty() { + assert_eq!(0.0, jaro("distance", "")); + } + + #[test] + fn jaro_same() { + assert_eq!(1.0, jaro("jaro", "jaro")); + } + + #[test] + fn jaro_multibyte() { + assert_delta!(0.818, jaro("testabctest", "testöঙ香test"), 0.001); + assert_delta!(0.818, jaro("testöঙ香test", "testabctest"), 0.001); + } + + #[test] + fn jaro_diff_short() { + assert_delta!(0.767, jaro("dixon", "dicksonx"), 0.001); + } + + #[test] + fn jaro_diff_one_character() { + assert_eq!(0.0, jaro("a", "b")); + } + + #[test] + fn jaro_same_one_character() { + assert_eq!(1.0, jaro("a", "a")); + } + + #[test] + fn generic_jaro_diff() { + assert_eq!(0.0, generic_jaro(&[1, 2], &[3, 4])); + } + + #[test] + fn jaro_diff_one_and_two() { + assert_delta!(0.83, jaro("a", "ab"), 0.01); + } + + #[test] + fn jaro_diff_two_and_one() { + assert_delta!(0.83, jaro("ab", "a"), 0.01); + } + + #[test] + fn jaro_diff_no_transposition() { + assert_delta!(0.822, jaro("dwayne", "duane"), 0.001); + } + + #[test] + fn jaro_diff_with_transposition() { + assert_delta!(0.944, jaro("martha", "marhta"), 0.001); + assert_delta!(0.6, jaro("a jke", "jane a k"), 0.001); + } + + #[test] + fn jaro_names() { + assert_delta!( + 0.392, + jaro("Friedrich Nietzsche", "Jean-Paul Sartre"), + 0.001 + ); + } + + #[test] + fn jaro_winkler_both_empty() { + assert_eq!(1.0, jaro_winkler("", "")); + } + + #[test] + fn jaro_winkler_first_empty() { + assert_eq!(0.0, jaro_winkler("", "jaro-winkler")); + } + + #[test] + fn jaro_winkler_second_empty() { + assert_eq!(0.0, jaro_winkler("distance", "")); + } + + #[test] + fn jaro_winkler_same() { + assert_eq!(1.0, jaro_winkler("Jaro-Winkler", "Jaro-Winkler")); + } + + #[test] + fn jaro_winkler_multibyte() { + assert_delta!(0.89, jaro_winkler("testabctest", "testöঙ香test"), 0.001); + assert_delta!(0.89, jaro_winkler("testöঙ香test", "testabctest"), 0.001); + } + + #[test] + fn jaro_winkler_diff_short() { + assert_delta!(0.813, jaro_winkler("dixon", "dicksonx"), 0.001); + assert_delta!(0.813, jaro_winkler("dicksonx", "dixon"), 0.001); + } + + #[test] + fn jaro_winkler_diff_one_character() { + assert_eq!(0.0, jaro_winkler("a", "b")); + } + + #[test] + fn jaro_winkler_same_one_character() { + assert_eq!(1.0, jaro_winkler("a", "a")); + } + + #[test] + fn jaro_winkler_diff_no_transposition() { + assert_delta!(0.84, jaro_winkler("dwayne", "duane"), 0.001); + } + + #[test] + fn jaro_winkler_diff_with_transposition() { + assert_delta!(0.961, jaro_winkler("martha", "marhta"), 0.001); + assert_delta!(0.6, jaro_winkler("a jke", "jane a k"), 0.001); + } + + #[test] + fn jaro_winkler_names() { + assert_delta!( + 0.452, + jaro_winkler("Friedrich Nietzsche", "Fran-Paul Sartre"), + 0.001 + ); + } + + #[test] + fn jaro_winkler_long_prefix() { + assert_delta!(0.866, jaro_winkler("cheeseburger", "cheese fries"), 0.001); + } + + #[test] + fn jaro_winkler_more_names() { + assert_delta!(0.868, jaro_winkler("Thorkel", "Thorgier"), 0.001); + } + + #[test] + fn jaro_winkler_length_of_one() { + assert_delta!(0.738, jaro_winkler("Dinsdale", "D"), 0.001); + } + + #[test] + fn jaro_winkler_very_long_prefix() { + assert_delta!( + 0.98519, + jaro_winkler("thequickbrownfoxjumpedoverx", "thequickbrownfoxjumpedovery") + ); + } + + #[test] + fn levenshtein_empty() { + assert_eq!(0, levenshtein("", "")); + } + + #[test] + fn levenshtein_same() { + assert_eq!(0, levenshtein("levenshtein", "levenshtein")); + } + + #[test] + fn levenshtein_diff_short() { + assert_eq!(3, levenshtein("kitten", "sitting")); + } + + #[test] + fn levenshtein_diff_with_space() { + assert_eq!(5, levenshtein("hello, world", "bye, world")); + } + + #[test] + fn levenshtein_diff_multibyte() { + assert_eq!(3, levenshtein("öঙ香", "abc")); + assert_eq!(3, levenshtein("abc", "öঙ香")); + } + + #[test] + fn levenshtein_diff_longer() { + let a = "The quick brown fox jumped over the angry dog."; + let b = "Lorem ipsum dolor sit amet, dicta latine an eam."; + assert_eq!(37, levenshtein(a, b)); + } + + #[test] + fn levenshtein_first_empty() { + assert_eq!(7, levenshtein("", "sitting")); + } + + #[test] + fn levenshtein_second_empty() { + assert_eq!(6, levenshtein("kitten", "")); + } + + #[test] + fn normalized_levenshtein_diff_short() { + assert_delta!(0.57142, normalized_levenshtein("kitten", "sitting")); + } + + #[test] + fn normalized_levenshtein_for_empty_strings() { + assert_delta!(1.0, normalized_levenshtein("", "")); + } + + #[test] + fn normalized_levenshtein_first_empty() { + assert_delta!(0.0, normalized_levenshtein("", "second")); + } + + #[test] + fn normalized_levenshtein_second_empty() { + assert_delta!(0.0, normalized_levenshtein("first", "")); + } + + #[test] + fn normalized_levenshtein_identical_strings() { + assert_delta!(1.0, normalized_levenshtein("identical", "identical")); + } + + #[test] + fn osa_distance_empty() { + assert_eq!(0, osa_distance("", "")); + } + + #[test] + fn osa_distance_same() { + assert_eq!(0, osa_distance("damerau", "damerau")); + } + + #[test] + fn osa_distance_first_empty() { + assert_eq!(7, osa_distance("", "damerau")); + } + + #[test] + fn osa_distance_second_empty() { + assert_eq!(7, osa_distance("damerau", "")); + } + + #[test] + fn osa_distance_diff() { + assert_eq!(3, osa_distance("ca", "abc")); + } + + #[test] + fn osa_distance_diff_short() { + assert_eq!(3, osa_distance("damerau", "aderua")); + } + + #[test] + fn osa_distance_diff_reversed() { + assert_eq!(3, osa_distance("aderua", "damerau")); + } + + #[test] + fn osa_distance_diff_multibyte() { + assert_eq!(3, osa_distance("öঙ香", "abc")); + assert_eq!(3, osa_distance("abc", "öঙ香")); + } + + #[test] + fn osa_distance_diff_unequal_length() { + assert_eq!(6, osa_distance("damerau", "aderuaxyz")); + } + + #[test] + fn osa_distance_diff_unequal_length_reversed() { + assert_eq!(6, osa_distance("aderuaxyz", "damerau")); + } + + #[test] + fn osa_distance_diff_comedians() { + assert_eq!(5, osa_distance("Stewart", "Colbert")); + } + + #[test] + fn osa_distance_many_transpositions() { + assert_eq!(4, osa_distance("abcdefghijkl", "bacedfgihjlk")); + } + + #[test] + fn osa_distance_diff_longer() { + let a = "The quick brown fox jumped over the angry dog."; + let b = "Lehem ipsum dolor sit amet, dicta latine an eam."; + assert_eq!(36, osa_distance(a, b)); + } + + #[test] + fn osa_distance_beginning_transposition() { + assert_eq!(1, osa_distance("foobar", "ofobar")); + } + + #[test] + fn osa_distance_end_transposition() { + assert_eq!(1, osa_distance("specter", "spectre")); + } + + #[test] + fn osa_distance_restricted_edit() { + assert_eq!(4, osa_distance("a cat", "an abct")); + } + + #[test] + fn damerau_levenshtein_empty() { + assert_eq!(0, damerau_levenshtein("", "")); + } + + #[test] + fn damerau_levenshtein_same() { + assert_eq!(0, damerau_levenshtein("damerau", "damerau")); + } + + #[test] + fn damerau_levenshtein_first_empty() { + assert_eq!(7, damerau_levenshtein("", "damerau")); + } + + #[test] + fn damerau_levenshtein_second_empty() { + assert_eq!(7, damerau_levenshtein("damerau", "")); + } + + #[test] + fn damerau_levenshtein_diff() { + assert_eq!(2, damerau_levenshtein("ca", "abc")); + } + + #[test] + fn damerau_levenshtein_diff_short() { + assert_eq!(3, damerau_levenshtein("damerau", "aderua")); + } + + #[test] + fn damerau_levenshtein_diff_reversed() { + assert_eq!(3, damerau_levenshtein("aderua", "damerau")); + } + + #[test] + fn damerau_levenshtein_diff_multibyte() { + assert_eq!(3, damerau_levenshtein("öঙ香", "abc")); + assert_eq!(3, damerau_levenshtein("abc", "öঙ香")); + } + + #[test] + fn damerau_levenshtein_diff_unequal_length() { + assert_eq!(6, damerau_levenshtein("damerau", "aderuaxyz")); + } + + #[test] + fn damerau_levenshtein_diff_unequal_length_reversed() { + assert_eq!(6, damerau_levenshtein("aderuaxyz", "damerau")); + } + + #[test] + fn damerau_levenshtein_diff_comedians() { + assert_eq!(5, damerau_levenshtein("Stewart", "Colbert")); + } + + #[test] + fn damerau_levenshtein_many_transpositions() { + assert_eq!(4, damerau_levenshtein("abcdefghijkl", "bacedfgihjlk")); + } + + #[test] + fn damerau_levenshtein_diff_longer() { + let a = "The quick brown fox jumped over the angry dog."; + let b = "Lehem ipsum dolor sit amet, dicta latine an eam."; + assert_eq!(36, damerau_levenshtein(a, b)); + } + + #[test] + fn damerau_levenshtein_beginning_transposition() { + assert_eq!(1, damerau_levenshtein("foobar", "ofobar")); + } + + #[test] + fn damerau_levenshtein_end_transposition() { + assert_eq!(1, damerau_levenshtein("specter", "spectre")); + } + + #[test] + fn damerau_levenshtein_unrestricted_edit() { + assert_eq!(3, damerau_levenshtein("a cat", "an abct")); + } + + #[test] + fn normalized_damerau_levenshtein_diff_short() { + assert_delta!( + 0.27272, + normalized_damerau_levenshtein("levenshtein", "löwenbräu") + ); + } + + #[test] + fn normalized_damerau_levenshtein_for_empty_strings() { + assert_delta!(1.0, normalized_damerau_levenshtein("", "")); + } + + #[test] + fn normalized_damerau_levenshtein_first_empty() { + assert_delta!(0.0, normalized_damerau_levenshtein("", "flower")); + } + + #[test] + fn normalized_damerau_levenshtein_second_empty() { + assert_delta!(0.0, normalized_damerau_levenshtein("tree", "")); + } + + #[test] + fn normalized_damerau_levenshtein_identical_strings() { + assert_delta!( + 1.0, + normalized_damerau_levenshtein("sunglasses", "sunglasses") + ); + } + + #[test] + fn sorensen_dice_all() { + // test cases taken from + // https://github.com/aceakash/string-similarity/blob/f83ba3cd7bae874c20c429774e911ae8cff8bced/src/spec/index.spec.js#L11 + + assert_delta!(1.0, sorensen_dice("a", "a")); + assert_delta!(0.0, sorensen_dice("a", "b")); + assert_delta!(1.0, sorensen_dice("", "")); + assert_delta!(0.0, sorensen_dice("a", "")); + assert_delta!(0.0, sorensen_dice("", "a")); + assert_delta!(1.0, sorensen_dice("apple event", "apple event")); + assert_delta!(0.90909, sorensen_dice("iphone", "iphone x")); + assert_delta!(0.0, sorensen_dice("french", "quebec")); + assert_delta!(1.0, sorensen_dice("france", "france")); + assert_delta!(0.2, sorensen_dice("fRaNce", "france")); + assert_delta!(0.8, sorensen_dice("healed", "sealed")); + assert_delta!( + 0.78788, + sorensen_dice("web applications", "applications of the web") + ); + assert_delta!( + 0.92, + sorensen_dice( + "this will have a typo somewhere", + "this will huve a typo somewhere" + ) + ); + assert_delta!( + 0.60606, + sorensen_dice( + "Olive-green table for sale, in extremely good condition.", + "For sale: table in very good condition, olive green in colour." + ) + ); + assert_delta!( + 0.25581, + sorensen_dice( + "Olive-green table for sale, in extremely good condition.", + "For sale: green Subaru Impreza, 210,000 miles" + ) + ); + assert_delta!( + 0.14118, + sorensen_dice( + "Olive-green table for sale, in extremely good condition.", + "Wanted: mountain bike with at least 21 gears." + ) + ); + assert_delta!( + 0.77419, + sorensen_dice("this has one extra word", "this has one word") + ); + } +} |