//! 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")
);
}
}
Codebase Browser
chromium