sift/
matching.rs

1//! How far a folder of files is from a MusicBrainz release.
2//!
3//! The shape is beets': a weighted average of per-field distances in 0..1,
4//! where 0 is identical. Album title and artist weigh most; each track adds
5//! its title and length; tracks the release has and the folder lacks, or the
6//! reverse, are penalties of their own. What differs is how tracks are
7//! paired: by disc and track number when the files carry them, since that is
8//! what the numbers are for, and by cheapest title-and-length pairing only
9//! when they do not.
10
11use std::collections::HashMap;
12
13use unicode_normalization::UnicodeNormalization;
14
15use crate::meta::Track;
16use crate::musicbrainz::{Release, credit_name};
17
18const W_ALBUM: f64 = 3.0;
19const W_ARTIST: f64 = 3.0;
20const W_TITLE: f64 = 3.0;
21const W_LENGTH: f64 = 2.0;
22const W_MISSING: f64 = 0.9;
23const W_EXTRA: f64 = 0.6;
24/// Length differences below this are rounding and encoder padding.
25const LENGTH_GRACE_SECS: f64 = 10.0;
26const LENGTH_MAX_SECS: f64 = 30.0;
27
28/// Lower-case, accents stripped, punctuation dropped, `&` read as "and",
29/// a leading "the" ignored — the differences no one means.
30pub fn normalise(s: &str) -> String {
31    let folded: String = s
32        .nfkd()
33        .filter(|c| !unicode_normalization::char::is_combining_mark(*c))
34        .collect::<String>()
35        .to_lowercase()
36        .replace('&', " and ");
37    let words: Vec<&str> = folded
38        .split(|c: char| !c.is_alphanumeric())
39        .filter(|w| !w.is_empty())
40        .collect();
41    let words = match words.first() {
42        Some(&"the") if words.len() > 1 => &words[1..],
43        _ => &words[..],
44    };
45    words.join(" ")
46}
47
48/// A title without the edition markers taggers and shops append —
49/// "Monster (25th Anniversary Edition)" is "Monster" on MusicBrainz, which
50/// keeps the edition in a separate disambiguation.
51pub fn base_title(s: &str) -> String {
52    const EDITION: &[&str] = &[
53        "edition",
54        "remaster",
55        "deluxe",
56        "anniversary",
57        "expanded",
58        "bonus",
59        "reissue",
60        "version",
61        "special",
62        "collector",
63        "explicit",
64        "clean",
65        "mono",
66        "stereo",
67        "hi-res",
68        "24-bit",
69        "24bit",
70        "flac",
71        "web",
72        "vinyl",
73        "cd",
74        "lp",
75        "ep",
76    ];
77    let mut out = s.trim().to_string();
78    loop {
79        let trimmed = out.trim_end();
80        let Some(close) = trimmed.chars().last().filter(|c| *c == ')' || *c == ']') else {
81            break;
82        };
83        let open = if close == ')' { '(' } else { '[' };
84        let Some(start) = trimmed.rfind(open) else {
85            break;
86        };
87        let inner = trimmed[start + 1..trimmed.len() - 1].to_lowercase();
88        let is_edition = EDITION.iter().any(|k| {
89            inner
90                .split(|c: char| !c.is_alphanumeric() && c != '-')
91                .any(|w| w == *k || w.starts_with(k))
92        }) || inner.chars().all(|c| c.is_ascii_digit());
93        if start == 0 || !is_edition {
94            break;
95        }
96        out = trimmed[..start]
97            .trim_end()
98            .trim_end_matches(['-', ':', '–'])
99            .trim_end()
100            .to_string();
101    }
102    out
103}
104
105pub fn string_distance(a: &str, b: &str) -> f64 {
106    // Beets' `string_dist`, ported with its test suite: parts that differ
107    // between editions of the same thing (a leading "the", a bracketed
108    // version, a featured artist, "Pt. 2") cost a fraction of what the
109    // same number of different letters would.
110    static PATTERNS: std::sync::LazyLock<Vec<(regex::Regex, f64)>> =
111        std::sync::LazyLock::new(|| {
112            [
113                (r"^the ", 0.1),
114                (r"[\[\(]?(ep|single)[\]\)]?", 0.0),
115                (r"[\[\(]?(featuring|feat|ft)[\. :].+", 0.1),
116                (r"\(.*?\)", 0.3),
117                (r"\[.*?\]", 0.3),
118                (r"(, )?(pt\.|part) .+", 0.2),
119            ]
120            .into_iter()
121            .map(|(p, w)| (regex::Regex::new(p).expect("static regex"), w))
122            .collect()
123        });
124    let prepare = |s: &str| {
125        let mut s = s.to_lowercase();
126        for word in ["the", "a", "an"] {
127            if let Some(rest) = s.strip_suffix(&format!(", {word}")) {
128                s = format!("{word} {rest}");
129            }
130        }
131        s.replace('&', "and")
132    };
133    let (mut a, mut b) = (prepare(a), prepare(b));
134    let mut base = basic_distance(&a, &b);
135    let mut penalty = 0.0;
136    for (pattern, weight) in PATTERNS.iter() {
137        let (ca, cb) = (
138            pattern.replace_all(&a, "").into_owned(),
139            pattern.replace_all(&b, "").into_owned(),
140        );
141        if ca == a && cb == b {
142            continue;
143        }
144        let case = basic_distance(&ca, &cb);
145        let delta = (base - case).max(0.0);
146        if delta == 0.0 {
147            continue;
148        }
149        (a, b, base) = (ca, cb, case);
150        penalty += weight * delta;
151    }
152    base + penalty
153}
154
155/// Edit distance over letters and digits only, transliterated to ASCII,
156/// as a fraction of the longer string.
157fn basic_distance(a: &str, b: &str) -> f64 {
158    let clean = |s: &str| -> String {
159        deunicode::deunicode(s)
160            .to_lowercase()
161            .chars()
162            .filter(|c| c.is_ascii_alphanumeric())
163            .collect()
164    };
165    let (a, b) = (clean(a), clean(b));
166    if a.is_empty() && b.is_empty() {
167        return 0.0;
168    }
169    strsim::levenshtein(&a, &b) as f64 / a.chars().count().max(b.chars().count()) as f64
170}
171
172/// Beets' flat allowance, widened in proportion for long tracks. A trimmed
173/// silence or a vinyl edit moves a twenty-minute side by twenty seconds,
174/// which the flat allowance reads as a different recording; anything under
175/// about eight minutes is judged exactly as beets judges it.
176fn length_distance(local_secs: f64, remote_ms: Option<u64>) -> f64 {
177    let Some(ms) = remote_ms else { return 0.0 };
178    let remote = ms as f64 / 1000.0;
179    let grace = LENGTH_GRACE_SECS.max(remote * 0.02);
180    let max = LENGTH_MAX_SECS.max(remote * 0.06);
181    let diff = (local_secs - remote).abs();
182    ((diff - grace) / (max - grace)).clamp(0.0, 1.0)
183}
184
185#[derive(Debug, Clone)]
186pub struct Match {
187    pub release: Release,
188    pub distance: f64,
189    /// (index into the local tracks, index into `release.tracks()`)
190    pub pairs: Vec<(usize, usize)>,
191    /// Release tracks with no file.
192    pub missing: usize,
193    /// Files with no release track.
194    pub extra: usize,
195    /// What the distance is made of, each in 0..1: album title, artist,
196    /// and the mean over paired tracks of title and length.
197    pub parts: Parts,
198}
199
200#[derive(Debug, Clone, Copy, Default, serde::Serialize, serde::Deserialize)]
201pub struct Parts {
202    pub album: f64,
203    pub artist: f64,
204    pub titles: f64,
205    pub lengths: f64,
206}
207
208impl std::fmt::Display for Parts {
209    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
210        write!(
211            f,
212            "album {:.2}, artist {:.2}, titles {:.2}, lengths {:.2}",
213            self.album, self.artist, self.titles, self.lengths
214        )
215    }
216}
217
218impl Match {
219    pub fn is_complete(&self) -> bool {
220        self.missing == 0 && self.extra == 0
221    }
222}
223
224/// The value most tracks agree on.
225pub fn consensus<'a>(values: impl Iterator<Item = Option<&'a str>>) -> Option<String> {
226    let mut counts: HashMap<&str, usize> = HashMap::new();
227    for v in values.flatten() {
228        if !v.trim().is_empty() {
229            *counts.entry(v).or_default() += 1;
230        }
231    }
232    counts
233        .into_iter()
234        .max_by_key(|(v, n)| (*n, std::cmp::Reverse(v.len())))
235        .map(|(v, _)| v.to_string())
236}
237
238pub fn score(local: &[Track], release: &Release) -> Match {
239    let remote: Vec<_> = release.tracks().collect();
240    let album = consensus(local.iter().map(|t| t.album.as_deref())).unwrap_or_default();
241    let artist = consensus(
242        local
243            .iter()
244            .map(|t| t.album_artist.as_deref().or(t.artist.as_deref())),
245    )
246    .unwrap_or_default();
247
248    let d_album = string_distance(&base_title(&album), &base_title(&release.title));
249    let d_artist = if release.is_compilation()
250        && ["various artists", "various", "va"].contains(&normalise(&artist).as_str())
251    {
252        0.0
253    } else {
254        string_distance(&artist, &release.artist())
255    };
256
257    let cost = |l: usize, r: usize| -> (f64, f64) {
258        let (medium, track) = remote[r];
259        let _ = medium;
260        let title = local[l].title.as_deref().unwrap_or_default();
261        (
262            string_distance(title, &track.title),
263            length_distance(
264                local[l].duration.as_secs_f64(),
265                track.length.or(track.recording.length),
266            ),
267        )
268    };
269
270    let pairs = pair_by_number(local, release).unwrap_or_else(|| {
271        pair_by_cost(local.len(), remote.len(), |l, r| {
272            let (t, len) = cost(l, r);
273            W_TITLE * t + W_LENGTH * len
274        })
275    });
276
277    let mut num = W_ALBUM * d_album + W_ARTIST * d_artist;
278    let mut den = W_ALBUM + W_ARTIST;
279    let (mut titles, mut lengths) = (0.0, 0.0);
280    for &(l, r) in &pairs {
281        let (t, len) = cost(l, r);
282        titles += t;
283        lengths += len;
284        num += W_TITLE * t + W_LENGTH * len;
285        den += W_TITLE + W_LENGTH;
286    }
287    let paired = pairs.len().max(1) as f64;
288    let missing = remote.len() - pairs.len();
289    let extra = local.len() - pairs.len();
290    num += W_MISSING * missing as f64 + W_EXTRA * extra as f64;
291    den += W_MISSING * missing as f64 + W_EXTRA * extra as f64;
292
293    Match {
294        release: release.clone(),
295        distance: if den > 0.0 { num / den } else { 1.0 },
296        pairs,
297        missing,
298        extra,
299        parts: Parts {
300            album: d_album,
301            artist: d_artist,
302            titles: titles / paired,
303            lengths: lengths / paired,
304        },
305    }
306}
307
308/// Pair on (disc, track) when every file has a track number and no two
309/// collide. A single-disc rip with no disc tag is disc 1.
310fn pair_by_number(local: &[Track], release: &Release) -> Option<Vec<(usize, usize)>> {
311    let mut by_number = HashMap::new();
312    for (i, t) in local.iter().enumerate() {
313        let key = (t.disc.unwrap_or(1), t.track?);
314        if by_number.insert(key, i).is_some() {
315            return None;
316        }
317    }
318    let per_disc: Vec<(usize, usize)> = release
319        .tracks()
320        .enumerate()
321        .filter_map(|(r, (m, t))| by_number.get(&(m.position, t.position)).map(|&l| (l, r)))
322        .collect();
323    // Track numbers are often counted straight through the album while
324    // one side or the other splits it differently: files numbered 1–8 with
325    // no disc (or with B-side tracks 5–8 on "disc 2") against a release on
326    // one medium, or on two that each restart at 1. When no two files share
327    // a number, try the numbers as positions in the whole release.
328    let mut overall = HashMap::new();
329    let unique = local
330        .iter()
331        .enumerate()
332        .all(|(i, t)| t.track.is_some_and(|n| overall.insert(n, i).is_none()));
333    let continuous: Vec<(usize, usize)> = if unique {
334        (0..release.tracks().count())
335            .filter_map(|r| overall.get(&(r as u32 + 1)).map(|&l| (l, r)))
336            .collect()
337    } else {
338        Vec::new()
339    };
340    let pairs = if continuous.len() > per_disc.len() {
341        continuous
342    } else {
343        per_disc
344    };
345    // Numbers that match nothing are a sign they mean something else.
346    // Fall back to pairing on titles and lengths rather than trust them.
347    (pairs.len() * 2 >= local.len()).then_some(pairs)
348}
349
350/// Cheapest pairs first, each file and track used once. Not optimal in
351/// theory; indistinguishable in practice, where one pairing is far cheaper
352/// than the rest.
353fn pair_by_cost(
354    locals: usize,
355    remotes: usize,
356    cost: impl Fn(usize, usize) -> f64,
357) -> Vec<(usize, usize)> {
358    let mut all: Vec<(f64, usize, usize)> = (0..locals)
359        .flat_map(|l| (0..remotes).map(move |r| (l, r)))
360        .map(|(l, r)| (cost(l, r), l, r))
361        .collect();
362    all.sort_by(|a, b| a.0.total_cmp(&b.0));
363    let (mut used_l, mut used_r) = (vec![false; locals], vec![false; remotes]);
364    let mut pairs = Vec::new();
365    for (c, l, r) in all {
366        if used_l[l] || used_r[r] || c > (W_TITLE + W_LENGTH) * 0.6 {
367            continue;
368        }
369        used_l[l] = true;
370        used_r[r] = true;
371        pairs.push((l, r));
372    }
373    pairs.sort_unstable();
374    pairs
375}
376
377/// The credited artist for one track, falling back to the release's.
378pub fn track_artist(release: &Release, index: usize) -> String {
379    let (_, t) = release.tracks().nth(index).expect("index from pairs");
380    if t.artist_credit.is_empty() {
381        release.artist()
382    } else {
383        credit_name(&t.artist_credit)
384    }
385}
386
387#[cfg(test)]
388mod tests {
389    use super::*;
390    use std::time::Duration;
391
392    fn release() -> Release {
393        serde_json::from_value(serde_json::json!({
394            "id": "r", "title": "Geogaddi",
395            "artist-credit": [{"name": "Boards of Canada", "joinphrase": "", "artist": {"id": "a", "name": "Boards of Canada"}}],
396            "media": [{"position": 1, "tracks": [
397                {"id": "t1", "position": 1, "title": "Ready Lets Go", "length": 59000, "recording": {"id": "r1"}},
398                {"id": "t2", "position": 2, "title": "Music Is Math", "length": 321000, "recording": {"id": "r2"}},
399                {"id": "t3", "position": 3, "title": "Beware the Friendly Stranger", "length": 37000, "recording": {"id": "r3"}}
400            ]}]
401        }))
402        .unwrap()
403    }
404
405    fn track(title: &str, n: Option<u32>, secs: u64) -> Track {
406        Track {
407            title: Some(title.into()),
408            album: Some("Geogaddi".into()),
409            artist: Some("Boards Of Canada".into()),
410            track: n,
411            duration: Duration::from_secs(secs),
412            ..Default::default()
413        }
414    }
415
416    #[test]
417    fn length_allowance_grows_with_long_tracks() {
418        // A twenty-minute side 21 s short: the same recording.
419        assert_eq!(length_distance(1202.7, Some(1_224_000)), 0.0);
420        // A three-minute song 21 s off: judged as beets judges it.
421        assert!((length_distance(201.0, Some(180_000)) - 0.55).abs() < 1e-9);
422        assert_eq!(length_distance(185.0, Some(180_000)), 0.0);
423    }
424
425    #[test]
426    fn edition_markers_come_off_titles() {
427        assert_eq!(base_title("Monster (25th Anniversary Edition)"), "Monster");
428        assert_eq!(base_title("Kill For Love (Deluxe)"), "Kill For Love");
429        assert_eq!(base_title("OK Computer [Remastered] (2017)"), "OK Computer");
430        assert_eq!(
431            base_title("(What's the Story) Morning Glory?"),
432            "(What's the Story) Morning Glory?"
433        );
434        assert_eq!(base_title("Live at Leeds (Live)"), "Live at Leeds (Live)");
435        assert_eq!(
436            base_title("Music Has the Right to Children"),
437            "Music Has the Right to Children"
438        );
439    }
440
441    /// Beets' `StringDistanceTest`, case for case.
442    #[test]
443    fn string_distance_matches_beets() {
444        let d = string_distance;
445        assert_eq!(d("Some String", "Some String"), 0.0);
446        assert_ne!(d("Some String", "Totally Different"), 0.0);
447        assert_eq!(d("Some String", "Some.String!"), 0.0);
448        assert_eq!(d("Some String", "sOME sTring"), 0.0);
449        assert!(d("The Band Name", "Band Name") < d("XXX Band Name", "Band Name"));
450        assert!(d("One (Two)", "One") < d("One .Two.", "One"));
451        assert!(d("One [Two]", "One") < d("One .Two.", "One"));
452        assert_eq!(d("My Song (EP)", "My Song"), 0.0);
453        assert!(d("My Song feat. Someone", "My Song") < d("My Song blah Someone", "My Song"));
454        assert_eq!(d("The Song Title", "Song Title, The"), 0.0);
455        assert_eq!(d("A Song Title", "Song Title, A"), 0.0);
456        assert_eq!(d("An Album Title", "Album Title, An"), 0.0);
457        assert_eq!(d("", ""), 0.0);
458        for (a, b) in [("The ", ""), ("(EP)", "(EP)"), (", An", "")] {
459            assert!(d(a, b).is_finite());
460        }
461        assert_eq!(d("Untitled", "[Untitled]"), 0.0);
462        assert_eq!(d("And", "&"), 0.0);
463        assert_eq!(d("\u{e9}\u{e1}\u{f1}", "ean"), 0.0);
464    }
465
466    #[test]
467    fn normalises_the_differences_no_one_means() {
468        assert_eq!(normalise("The Beatles"), "beatles");
469        assert_eq!(normalise("Björk & Friends!"), "bjork and friends");
470        assert!(string_distance("Ready Let's Go", "Ready Lets Go") < 0.1);
471    }
472
473    #[test]
474    fn a_complete_tagged_album_is_very_close() {
475        let local = vec![
476            track("Ready Lets Go", Some(1), 59),
477            track("Music Is Math", Some(2), 321),
478            track("Beware the Friendly Stranger", Some(3), 37),
479        ];
480        let m = score(&local, &release());
481        assert!(m.distance < 0.01, "{}", m.distance);
482        assert!(m.is_complete());
483    }
484
485    #[test]
486    fn untagged_files_pair_by_title_and_length() {
487        let local = vec![
488            track("music is math", None, 320),
489            track("ready let's go", None, 60),
490            track("beware the friendly stranger", None, 38),
491        ];
492        let m = score(&local, &release());
493        assert_eq!(m.pairs, [(0, 1), (1, 0), (2, 2)]);
494        assert!(m.distance < 0.05, "{}", m.distance);
495    }
496
497    #[test]
498    fn a_second_disc_numbered_on_from_the_first_pairs_with_one_medium() {
499        let mut local = vec![
500            track("Ready Lets Go", Some(1), 59),
501            track("Music Is Math", Some(2), 321),
502            track("Beware the Friendly Stranger", Some(3), 37),
503        ];
504        local[2].disc = Some(2);
505        let m = score(&local, &release());
506        assert_eq!(m.pairs, [(0, 0), (1, 1), (2, 2)]);
507        assert!(m.is_complete());
508    }
509
510    #[test]
511    fn files_counted_straight_through_pair_with_sides_that_restart() {
512        let two_sides: Release = serde_json::from_value(serde_json::json!({
513            "id": "r", "title": "Geogaddi",
514            "artist-credit": [{"name": "Boards of Canada", "joinphrase": "", "artist": {"id": "a", "name": "Boards of Canada"}}],
515            "media": [
516                {"position": 1, "tracks": [
517                    {"id": "t1", "position": 1, "title": "Ready Lets Go", "length": 59000, "recording": {"id": "r1"}},
518                    {"id": "t2", "position": 2, "title": "Music Is Math", "length": 321000, "recording": {"id": "r2"}}
519                ]},
520                {"position": 2, "tracks": [
521                    {"id": "t3", "position": 1, "title": "Beware the Friendly Stranger", "length": 37000, "recording": {"id": "r3"}},
522                    {"id": "t4", "position": 2, "title": "Gyroscope", "length": 215000, "recording": {"id": "r4"}}
523                ]}
524            ]
525        }))
526        .unwrap();
527        let local = vec![
528            track("Ready Lets Go", Some(1), 59),
529            track("Music Is Math", Some(2), 321),
530            track("Beware the Friendly Stranger", Some(3), 37),
531            track("Gyroscope", Some(4), 215),
532        ];
533        let m = score(&local, &two_sides);
534        assert_eq!(m.pairs, [(0, 0), (1, 1), (2, 2), (3, 3)]);
535        assert!(m.is_complete());
536    }
537
538    #[test]
539    fn missing_tracks_and_the_wrong_album_cost() {
540        let local = vec![track("Ready Lets Go", Some(1), 59)];
541        let m = score(&local, &release());
542        assert_eq!(m.missing, 2);
543        let mut wrong = vec![track("Roygbiv", Some(1), 150)];
544        wrong[0].album = Some("Music Has the Right to Children".into());
545        assert!(score(&wrong, &release()).distance > 0.4);
546    }
547}
sift/matching.rs

sift/
matching.rs
