xil_core/
textsim.rs

1//! Python's `difflib` — Ratcliff/Obershelp similarity and
2//! `get_close_matches`.
3//!
4//! The scanner's near-miss cutoff (0.72) is a behavioural boundary, so the
5//! ratio has to agree with CPython to the last digit rather than merely be
6//! "a similarity measure". This is a direct transcription of
7//! `SequenceMatcher`, not an equivalent algorithm.
8//!
9//! Autojunk is on, as it is by default in CPython: once *b* reaches 200
10//! elements, any element occurring more than `len(b) // 100 + 1` times is
11//! dropped from the index. That rarely touches a scanner tag but decides
12//! the score of a long line of dialogue (0.295 with it, 0.873 without, for
13//! one pair of 220-character sentences).
14
15use std::collections::HashMap;
16
17/// `difflib.SequenceMatcher(None, a, b)` over character sequences.
18pub struct SequenceMatcher {
19    a: Vec<char>,
20    b: Vec<char>,
21    /// Each char of `b` to the indices where it occurs, in order.
22    b2j: HashMap<char, Vec<usize>>,
23}
24
25impl SequenceMatcher {
26    pub fn new(a: &str, b: &str) -> SequenceMatcher {
27        let a: Vec<char> = a.chars().collect();
28        let b: Vec<char> = b.chars().collect();
29        let mut b2j: HashMap<char, Vec<usize>> = HashMap::new();
30        for (j, c) in b.iter().enumerate() {
31            b2j.entry(*c).or_default().push(j);
32        }
33        let n = b.len();
34        if n >= 200 {
35            let ntest = n / 100 + 1;
36            b2j.retain(|_, idxs| idxs.len() <= ntest);
37        }
38        SequenceMatcher { a, b, b2j }
39    }
40
41    /// `find_longest_match(alo, ahi, blo, bhi)`. With no `isjunk` the
42    /// junk set is empty, so only CPython's first pair of extension passes
43    /// can move — and they do, over popular elements autojunk dropped.
44    fn find_longest_match(
45        &self,
46        alo: usize,
47        ahi: usize,
48        blo: usize,
49        bhi: usize,
50    ) -> (usize, usize, usize) {
51        let (mut besti, mut bestj, mut bestsize) = (alo, blo, 0usize);
52        let mut j2len: HashMap<usize, usize> = HashMap::new();
53        for i in alo..ahi {
54            let mut newj2len: HashMap<usize, usize> = HashMap::new();
55            if let Some(js) = self.b2j.get(&self.a[i]) {
56                for &j in js {
57                    if j < blo {
58                        continue;
59                    }
60                    if j >= bhi {
61                        break;
62                    }
63                    let k = j
64                        .checked_sub(1)
65                        .and_then(|jm| j2len.get(&jm).copied())
66                        .unwrap_or(0)
67                        + 1;
68                    newj2len.insert(j, k);
69                    if k > bestsize {
70                        besti = i + 1 - k;
71                        bestj = j + 1 - k;
72                        bestsize = k;
73                    }
74                }
75            }
76            j2len = newj2len;
77        }
78        // Extend the match outward over equal elements.
79        while besti > alo && bestj > blo && self.a[besti - 1] == self.b[bestj - 1] {
80            besti -= 1;
81            bestj -= 1;
82            bestsize += 1;
83        }
84        while besti + bestsize < ahi
85            && bestj + bestsize < bhi
86            && self.a[besti + bestsize] == self.b[bestj + bestsize]
87        {
88            bestsize += 1;
89        }
90        (besti, bestj, bestsize)
91    }
92
93    /// Total size of all matching blocks — everything `ratio` needs.
94    fn total_matches(&self) -> usize {
95        let mut queue = vec![(0usize, self.a.len(), 0usize, self.b.len())];
96        let mut matches = 0usize;
97        while let Some((alo, ahi, blo, bhi)) = queue.pop() {
98            let (i, j, k) = self.find_longest_match(alo, ahi, blo, bhi);
99            if k == 0 {
100                continue;
101            }
102            matches += k;
103            if alo < i && blo < j {
104                queue.push((alo, i, blo, j));
105            }
106            if i + k < ahi && j + k < bhi {
107                queue.push((i + k, ahi, j + k, bhi));
108            }
109        }
110        matches
111    }
112
113    /// `ratio()` — `2 * matches / (len(a) + len(b))`, or 1.0 for two empties.
114    pub fn ratio(&self) -> f64 {
115        let length = self.a.len() + self.b.len();
116        if length == 0 {
117            return 1.0;
118        }
119        2.0 * self.total_matches() as f64 / length as f64
120    }
121}
122
123/// `difflib.get_close_matches(word, possibilities, n, cutoff)`.
124///
125/// CPython sets `word` as sequence *b* and each possibility as *a*, then
126/// takes the `n` largest `(ratio, possibility)` tuples — so a tie is broken
127/// by the possibility that sorts later.
128pub fn get_close_matches(
129    word: &str,
130    possibilities: &[String],
131    n: usize,
132    cutoff: f64,
133) -> Vec<String> {
134    let mut scored: Vec<(f64, &String)> = possibilities
135        .iter()
136        .map(|x| (SequenceMatcher::new(x, word).ratio(), x))
137        .filter(|(r, _)| *r >= cutoff)
138        .collect();
139    // heapq.nlargest on (score, value) tuples: descending by score, then by
140    // value. A stable sort on the reversed comparison reproduces it.
141    scored.sort_by(|l, r| {
142        r.0.partial_cmp(&l.0)
143            .unwrap_or(std::cmp::Ordering::Equal)
144            .then_with(|| r.1.cmp(l.1))
145    });
146    scored.into_iter().take(n).map(|(_, x)| x.clone()).collect()
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152
153    /// Ratios recorded from CPython's difflib, printed at 17 significant
154    /// digits so a drift in the last bit would show.
155    ///
156    /// The literals are pasted from that output unedited — trimming them to
157    /// the shortest round-tripping form would hide where they came from, so
158    /// the precision lint is off for this table alone.
159    #[test]
160    #[allow(clippy::excessive_precision)]
161    fn ratio_matches_cpython() {
162        let cases = [
163            ("laugh", "laughs", 0.90909090909090906),
164            ("clear throat", "clears throat", 0.95999999999999996),
165            ("surprised", "surprise", 0.94117647058823528),
166            ("narration", "narrating", 0.88888888888888884),
167            ("crying", "cries", 0.54545454545454541),
168            ("sigh", "sighs", 0.88888888888888884),
169            ("cough", "coughs", 0.90909090909090906),
170            ("gasp", "gasps", 0.88888888888888884),
171            ("angry", "angry", 1.0),
172            ("happy", "exhausted", 0.2857142857142857),
173            ("chuckle", "chuckles", 0.93333333333333335),
174        ];
175        for (a, b, want) in cases {
176            let got = SequenceMatcher::new(a, b).ratio();
177            assert_eq!(got, want, "ratio({a:?}, {b:?}) = {got:.17} want {want:.17}");
178        }
179    }
180
181    #[test]
182    fn autojunk_engages_at_two_hundred() {
183        let a = "the quick brown fox jumps over the lazy dog and then keeps running through the forest until it reaches the river where it stops to drink some water before heading back home to its den in the hills beyond the valley far away";
184        let b = "the quick brown fox jumped over a lazy dog and kept running through the forest till it reached the river where it stopped to drink water before heading home to its den in the hills past the valley very far away indeed";
185        assert_eq!(SequenceMatcher::new(a, b).ratio(), 0.29545454545454547);
186        assert_eq!(SequenceMatcher::new(b, a).ratio(), 0.4409090909090909);
187    }
188
189    #[test]
190    fn empty_sequences_are_identical() {
191        assert_eq!(SequenceMatcher::new("", "").ratio(), 1.0);
192        assert_eq!(SequenceMatcher::new("", "abc").ratio(), 0.0);
193        assert_eq!(SequenceMatcher::new("abc", "").ratio(), 0.0);
194    }
195
196    #[test]
197    fn close_matches_honour_the_cutoff() {
198        let cands: Vec<String> = [
199            "laugh",
200            "chuckle",
201            "sigh",
202            "surprised",
203            "clear throat",
204            "narration",
205        ]
206        .iter()
207        .map(|s| s.to_string())
208        .collect();
209        assert_eq!(get_close_matches("laughs", &cands, 1, 0.72), vec!["laugh"]);
210        assert_eq!(
211            get_close_matches("clears throat", &cands, 1, 0.72),
212            vec!["clear throat"]
213        );
214        assert_eq!(
215            get_close_matches("surprise", &cands, 1, 0.72),
216            vec!["surprised"]
217        );
218        assert!(get_close_matches("exhausted", &cands, 1, 0.72).is_empty());
219        assert!(get_close_matches("", &cands, 1, 0.72).is_empty());
220    }
221
222    #[test]
223    fn ties_break_on_the_later_candidate() {
224        // "ab" scores the same against both; CPython's nlargest on the
225        // (score, value) tuple keeps the greater string.
226        let cands: Vec<String> = vec!["aX".into(), "aY".into()];
227        assert_eq!(get_close_matches("ab", &cands, 1, 0.4), vec!["aY"]);
228    }
229
230    #[test]
231    fn n_limits_the_result() {
232        let cands: Vec<String> = vec!["laugh".into(), "laughing".into(), "cough".into()];
233        assert_eq!(get_close_matches("laughs", &cands, 2, 0.5).len(), 2);
234        assert_eq!(get_close_matches("laughs", &cands, 1, 0.5), vec!["laugh"]);
235    }
236}
xil_core/textsim.rs

xil_core/
textsim.rs
