music21_rs/search/
difflib.rs

1//! How alike two sequences are, as Python's `difflib.SequenceMatcher`
2//! measures it, which music21's approximate searches rank by.
3
4use std::collections::HashMap;
5
6use crate::defaults::FloatType;
7
8/// Python's `SequenceMatcher(None, a, b).ratio()`: twice the number of
9/// items in the matching blocks over the items of both, one for two empty
10/// sequences. The blocks are found as Python finds them -- the longest
11/// match first, earliest where several are as long, then the same either
12/// side of it -- and an item of `b` coming in more than one percent of a
13/// `b` of 200 items or more is junk, as Python's `autojunk` makes it.
14pub(crate) fn ratio<T: Copy + Eq + std::hash::Hash>(a: &[T], b: &[T]) -> FloatType {
15    let matches: usize = matching_blocks(a, b).iter().map(|(_, _, size)| size).sum();
16    let length = a.len() + b.len();
17    if length == 0 {
18        1.0
19    } else {
20        2.0 * matches as FloatType / length as FloatType
21    }
22}
23
24/// Where each item of `b` comes, its popular items taken out.
25fn positions<T: Copy + Eq + std::hash::Hash>(b: &[T]) -> HashMap<T, Vec<usize>> {
26    let mut b2j: HashMap<T, Vec<usize>> = HashMap::new();
27    for (index, item) in b.iter().enumerate() {
28        b2j.entry(*item).or_default().push(index);
29    }
30    if b.len() >= 200 {
31        let most = b.len() / 100 + 1;
32        b2j.retain(|_, indices| indices.len() <= most);
33    }
34    b2j
35}
36
37/// Python's `find_longest_match` within `a[alo..ahi]` and `b[blo..bhi]`,
38/// with no `isjunk`.
39fn longest_match<T: Copy + Eq + std::hash::Hash>(
40    a: &[T],
41    b: &[T],
42    b2j: &HashMap<T, Vec<usize>>,
43    (alo, ahi, blo, bhi): (usize, usize, usize, usize),
44) -> (usize, usize, usize) {
45    let (mut best_i, mut best_j, mut best_size) = (alo, blo, 0);
46    let mut j2len: HashMap<usize, usize> = HashMap::new();
47    for (i, item) in a.iter().enumerate().take(ahi).skip(alo) {
48        let mut next: HashMap<usize, usize> = HashMap::new();
49        if let Some(indices) = b2j.get(item) {
50            for &j in indices {
51                if j < blo {
52                    continue;
53                }
54                if j >= bhi {
55                    break;
56                }
57                let k = j
58                    .checked_sub(1)
59                    .and_then(|before| j2len.get(&before))
60                    .copied()
61                    .unwrap_or(0)
62                    + 1;
63                next.insert(j, k);
64                if k > best_size {
65                    (best_i, best_j, best_size) = (i + 1 - k, j + 1 - k, k);
66                }
67            }
68        }
69        j2len = next;
70    }
71    // Without `isjunk` nothing is junk -- the popular items are only left
72    // out of `b2j` -- so the match grows over whatever is equal on either
73    // side.
74    while best_i > alo && best_j > blo && a[best_i - 1] == b[best_j - 1] {
75        (best_i, best_j, best_size) = (best_i - 1, best_j - 1, best_size + 1);
76    }
77    while best_i + best_size < ahi
78        && best_j + best_size < bhi
79        && a[best_i + best_size] == b[best_j + best_size]
80    {
81        best_size += 1;
82    }
83    (best_i, best_j, best_size)
84}
85
86/// What one stretch of an [`Opcode`] does to turn the first sequence into
87/// the second: Python's opcode tags.
88#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
89#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
90pub enum OpcodeTag {
91    /// The first sequence's stretch is replaced by the second's: `replace`.
92    Replace,
93    /// The first sequence's stretch is left out: `delete`.
94    Delete,
95    /// The second sequence's stretch is put in: `insert`.
96    Insert,
97    /// The two stretches are the same: `equal`.
98    Equal,
99}
100
101impl OpcodeTag {
102    /// Python's name for the tag.
103    pub fn as_str(self) -> &'static str {
104        match self {
105            Self::Replace => "replace",
106            Self::Delete => "delete",
107            Self::Insert => "insert",
108            Self::Equal => "equal",
109        }
110    }
111}
112
113/// One step of turning one sequence into another: Python's opcode
114/// `(tag, i1, i2, j1, j2)`, the first sequence's items `i1..i2` and the
115/// second's `j1..j2`.
116#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
117#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
118pub struct Opcode {
119    /// What the step does.
120    pub tag: OpcodeTag,
121    /// Where the stretch of the first sequence starts.
122    pub i1: usize,
123    /// Where it ends.
124    pub i2: usize,
125    /// Where the stretch of the second sequence starts.
126    pub j1: usize,
127    /// Where it ends.
128    pub j2: usize,
129}
130
131/// Python's `SequenceMatcher(None, a, b).get_opcodes()`: the steps that turn
132/// `a` into `b`, between the matching blocks.
133pub(crate) fn opcodes<T: Copy + Eq + std::hash::Hash>(a: &[T], b: &[T]) -> Vec<Opcode> {
134    let mut blocks = matching_blocks(a, b);
135    blocks.push((a.len(), b.len(), 0));
136    let (mut i, mut j) = (0, 0);
137    let mut steps = Vec::new();
138    for (ai, bj, size) in blocks {
139        let tag = if i < ai && j < bj {
140            Some(OpcodeTag::Replace)
141        } else if i < ai {
142            Some(OpcodeTag::Delete)
143        } else if j < bj {
144            Some(OpcodeTag::Insert)
145        } else {
146            None
147        };
148        if let Some(tag) = tag {
149            steps.push(Opcode {
150                tag,
151                i1: i,
152                i2: ai,
153                j1: j,
154                j2: bj,
155            });
156        }
157        (i, j) = (ai + size, bj + size);
158        if size > 0 {
159            steps.push(Opcode {
160                tag: OpcodeTag::Equal,
161                i1: ai,
162                i2: i,
163                j1: bj,
164                j2: j,
165            });
166        }
167    }
168    steps
169}
170
171/// Python's `get_matching_blocks`, without its closing sentinel: each
172/// `(i, j, size)` with `a[i..i + size] == b[j..j + size]`, adjacent blocks
173/// joined.
174fn matching_blocks<T: Copy + Eq + std::hash::Hash>(a: &[T], b: &[T]) -> Vec<(usize, usize, usize)> {
175    let b2j = positions(b);
176    let mut queue = vec![(0, a.len(), 0, b.len())];
177    let mut blocks = Vec::new();
178    while let Some(range) = queue.pop() {
179        let (alo, ahi, blo, bhi) = range;
180        let (i, j, k) = longest_match(a, b, &b2j, range);
181        if k > 0 {
182            blocks.push((i, j, k));
183            if alo < i && blo < j {
184                queue.push((alo, i, blo, j));
185            }
186            if i + k < ahi && j + k < bhi {
187                queue.push((i + k, ahi, j + k, bhi));
188            }
189        }
190    }
191    blocks.sort_unstable();
192    let mut joined: Vec<(usize, usize, usize)> = Vec::new();
193    for (i, j, k) in blocks {
194        match joined.last_mut() {
195            Some((i1, j1, k1)) if *i1 + *k1 == i && *j1 + *k1 == j => *k1 += k,
196            _ => joined.push((i, j, k)),
197        }
198    }
199    joined
200}
201
202#[cfg(test)]
203mod tests {
204    use super::*;
205
206    fn chars(text: &str) -> Vec<char> {
207        text.chars().collect()
208    }
209
210    #[test]
211    fn opcodes_are_pythons() {
212        // Read off Python's SequenceMatcher(None, 'qabxcd', 'abycdf').get_opcodes().
213        let steps: Vec<(&str, usize, usize, usize, usize)> =
214            opcodes(&chars("qabxcd"), &chars("abycdf"))
215                .iter()
216                .map(|step| (step.tag.as_str(), step.i1, step.i2, step.j1, step.j2))
217                .collect();
218        assert_eq!(
219            steps,
220            [
221                ("delete", 0, 1, 0, 0),
222                ("equal", 1, 3, 0, 2),
223                ("replace", 3, 4, 2, 3),
224                ("equal", 4, 6, 3, 5),
225                ("insert", 6, 6, 5, 6),
226            ]
227        );
228        assert!(opcodes::<char>(&[], &[]).is_empty());
229    }
230
231    #[test]
232    fn a_ratio_is_pythons() {
233        // Each read off Python's difflib.SequenceMatcher(None, a, b).ratio().
234        assert_eq!(ratio(&chars("abcd"), &chars("bcde")), 0.75);
235        assert_eq!(ratio(&chars(""), &chars("")), 1.0);
236        assert_eq!(ratio(&chars("abc"), &chars("")), 0.0);
237        assert_eq!(
238            ratio(
239                &chars("private Thread currentThread;"),
240                &chars("private volatile Thread currentThread;")
241            ),
242            0.865_671_641_791_044_7
243        );
244        assert_eq!(
245            ratio(&chars("hello world"), &chars("world hello")),
246            0.454_545_454_545_454_53
247        );
248        // A long b, where Python's autojunk leaves its common letters out
249        // of the search, though a match still grows over them.
250        let long_b = chars(&"abc".repeat(100));
251        assert_eq!(
252            ratio(&chars(&"ab".repeat(150)), &long_b),
253            0.006_666_666_666_666_667
254        );
255        assert_eq!(
256            ratio(&chars(&format!("{}q", "xab".repeat(80))), &long_b),
257            0.0
258        );
259    }
260}
music21_rs/search/difflib.rs

music21_rs/search/
difflib.rs
