fuzzt 0.3.1

Implementations of string similarity metrics. Includes Hamming, Levenshtein, OSA, Damerau-Levenshtein, Jaro, Jaro-Winkler, and Sørensen-Dice.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

use crate::{
    algorithms::{SequenceMatcher, Similarity, SimilarityMetric},
    processors::{NullStringProcessor, StringProcessor},
};
use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Returns a list of the best matches to a collection of choices.
///
/// This is a convenience function for getting the choices with the highest scores.
///
/// # Arguments
///
/// * `query` - A string to match against.
/// * `choices` - A list of choices to compare against the query.
/// * `cutoff` - A score threshold. No matches with a score less than this number will be returned. Defaults to 0.7.
/// * `n` - Optional maximum for the number of elements returned. Defaults to 3.
/// * `processor` - Optional function for transforming choices before matching. If not provided, `NullStringProcessor` is used.
/// * `scorer` - Optional scoring function for extract(). If not provided, `SequenceMatcher` is used.
///
/// # Returns
///
/// * A vector of the top 'n' matches from the given choices.
///
/// # Example
///
/// ```
/// extern crate fuzzt;
/// use fuzzt::{algorithms::NormalizedLevenshtein, get_top_n, processors::NullStringProcessor};
///
/// let matches = get_top_n(
///     "apple",
///     &["apply", "apples", "ape", "applet", "applesauce"],
///     Some(0.8),
///     Some(3),
///     Some(&NullStringProcessor),
///     Some(&NormalizedLevenshtein),
/// );
/// assert_eq!(matches, ["apples", "applet", "apply"]);
/// ```
pub fn get_top_n<'a>(
    query: &str,
    choices: &[&'a str],
    cutoff: Option<f64>,
    n: Option<usize>,
    processor: Option<&dyn StringProcessor>,
    scorer: Option<&dyn SimilarityMetric>,
) -> Vec<&'a str> {
    let mut matches = BinaryHeap::new();
    let n = n.unwrap_or(3);
    let cutoff = cutoff.unwrap_or(0.7);
    let scorer = match scorer {
        Some(scorer_trait) => scorer_trait,
        None => &SequenceMatcher,
    };
    let processor = match processor {
        Some(some_processor) => some_processor,
        None => &NullStringProcessor,
    };
    let processed_query = processor.process(query);

    for &choice in choices {
        let processed_choice = processor.process(choice);
        let raw_ratio = scorer.compute_metric(processed_query.as_str(), processed_choice.as_str());
        let ratio = match raw_ratio {
            Similarity::Usize(r) => r as f64,
            Similarity::Float(r) => r,
        };
        if ratio >= cutoff {
            let int_ratio = match raw_ratio {
                Similarity::Usize(r) => r as i64,
                Similarity::Float(r) => (r * std::u32::MAX as f64) as i64,
            };
            // we're putting the word itself in reverse in so that matches with
            // the same ratio are ordered lexicographically.
            matches.push((int_ratio, Reverse(choice)));
        }
    }
    let mut rv = vec![];
    for _ in 0..n {
        if let Some((_, elt)) = matches.pop() {
            rv.push(elt.0);
        } else {
            break;
        }
    }
    rv
}

#[cfg(test)]
mod tests {
    use super::get_top_n;
    use crate::algorithms::jaro::JaroWinkler;
    use crate::algorithms::SimilarityMetric;
    use crate::processors::{LowerAlphaNumStringProcessor, StringProcessor};
    use rstest::rstest;

    #[rstest]
    #[case(Some(0.7), Some(3), None, None, &["brazil", "braziu", "trazil"])]
    #[case(Some(0.9), Some(5), None, None, &["brazil"])]
    #[case(Some(0.7), Some(2), None, Some(&JaroWinkler as &dyn SimilarityMetric), &["brazil", "braziu"])]
    #[case(Some(0.7), Some(2), Some(&LowerAlphaNumStringProcessor as &dyn StringProcessor), None, &["brazil", "BRA ZIL"])]
    fn test_get_top_n<'a>(
        #[case] cutoff: Option<f64>,
        #[case] n: Option<usize>,
        #[case] processor: Option<&dyn StringProcessor>,
        #[case] scorer: Option<&dyn SimilarityMetric>,
        #[case] expected: &[&'a str],
    ) {
        let choices = &["trazil", "BRA ZIL", "brazil", "spain", "braziu"][..];
        let query = "brazil";
        let matches = get_top_n(query, choices, cutoff, n, processor, scorer);
        assert_eq!(matches, expected);
    }
}