music21/omr/
correctors.rs

1//! Correcting the rhythm of a score read by optical music recognition:
2//! music21's `omr.correctors`.
3//!
4//! A measure whose notes do not fill its bar was most likely misread. The
5//! correctors look for the measure that most likely stands where it should
6//! -- another measure of the same part a likely distance away whose rhythm
7//! differs from it in likely ways (the horizontal model), or the measure
8//! at the same place in another part that tends to move with it (the
9//! vertical model) -- and put that measure's rhythm in its place, keeping
10//! its pitches.
11//!
12//! Rhythms are compared as text: each note, chord or rest of a measure is
13//! one character for its length, notes on even codes and rests on odd
14//! ones ([`measure_hash`]).
15
16use std::collections::HashMap;
17
18use crate::defaults::FloatType;
19use crate::error::{Error, Result};
20use crate::meter::TimeSignature;
21use crate::search::difflib;
22use crate::stream::{Stream, StreamElement, StreamEvent, StreamKind};
23
24pub use crate::search::difflib::{Opcode, OpcodeTag};
25
26/// A flagged measure and the measure found to correct it, with how likely
27/// the correction is: music21's `MeasureRelationship`.
28#[derive(Clone, Copy, Debug, PartialEq)]
29#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
30pub struct MeasureRelationship {
31    /// The part of the flagged measure.
32    pub flagged_measure_part: usize,
33    /// The flagged measure's index among its part's measures.
34    pub flagged_measure_index: usize,
35    /// The part of the measure correcting it.
36    pub correct_measure_part: usize,
37    /// The correcting measure's index among its part's measures.
38    pub correct_measure_index: usize,
39    /// How likely the correction is.
40    pub correction_probability: FloatType,
41}
42
43/// How many flagged measures were corrected, and by which model: music21's
44/// `PriorsIntegrationScore`.
45#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
46#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
47pub struct PriorsIntegrationScore {
48    /// Flagged measures both models found a correction for.
49    pub total: usize,
50    /// Those the horizontal model's correction was used for.
51    pub horizontal: usize,
52    /// Those the vertical model's correction was used for.
53    pub vertical: usize,
54    /// Those left as they were, which music21 never counts.
55    pub ignored: usize,
56}
57
58/// How likely a note is read right: music21's `getProbabilityOnEquality`.
59pub const PROBABILITY_ON_EQUALITY: FloatType = 0.9675;
60/// How likely a note is missed: music21's `getProbabilityOnOmission`.
61pub const PROBABILITY_ON_OMISSION: FloatType = 0.009;
62/// How likely a note is read that is not there: music21's
63/// `getProbabilityOnAddition`.
64pub const PROBABILITY_ON_ADDITION: FloatType = 0.004;
65
66/// The rhythm of a measure as text, a character for each note, chord or
67/// rest, as music21's `MeasureHash.getHashString` writes it. A measure
68/// holding voices is chordified first.
69///
70/// The character is ten times the base-2 logarithm of the length in 256ths
71/// of a quarter, from 1 to 127 -- made even for a note or chord and odd for
72/// a rest -- and that of a 64th for anything of no length. A stroke with no
73/// pitch is left out.
74///
75/// ```
76/// use music21::omr::correctors::measure_hash;
77/// use music21::tinynotation::from_tiny_notation;
78///
79/// let line = from_tiny_notation("4/4 c4 d8 r8 e2")?;
80/// let measure = line.measures()[0];
81/// assert_eq!(measure_hash(measure)?, "PFGZ");
82/// # Ok::<(), music21::Error>(())
83/// ```
84///
85/// # Errors
86///
87/// A measure of voices that cannot be chordified.
88pub fn measure_hash(measure: &Stream) -> Result<String> {
89    let flat = !measure
90        .events()
91        .iter()
92        .any(|event| matches!(event.element(), StreamElement::Stream(_)));
93    let chordified;
94    let source = if flat {
95        measure
96    } else {
97        chordified = measure.chordify()?;
98        &chordified
99    };
100    let mut hash = String::new();
101    for event in source.events() {
102        let element = event.element();
103        if !is_general_note(element) {
104            continue;
105        }
106        let length = element.quarter_length();
107        let code = if length == 0.0 {
108            Some(hash_grace())
109        } else {
110            match element {
111                StreamElement::Note(_)
112                | StreamElement::Chord(_)
113                | StreamElement::ChordSymbol(_) => Some(hash_note(length)),
114                StreamElement::Rest(_) => Some(hash_rest(length)),
115                _ => None,
116            }
117        };
118        if let Some(code) = code {
119            hash.push(code);
120        }
121    }
122    Ok(hash)
123}
124
125/// music21's `notesAndRests`: what has a duration of a note.
126fn is_general_note(element: &StreamElement) -> bool {
127    matches!(
128        element,
129        StreamElement::Note(_)
130            | StreamElement::Chord(_)
131            | StreamElement::Rest(_)
132            | StreamElement::Unpitched(_)
133            | StreamElement::PercussionChord(_)
134            | StreamElement::ChordSymbol(_)
135    )
136}
137
138/// music21's `hashQuarterLength`: ten times the base-2 logarithm of a
139/// length in 256ths of a quarter, from 1 to 127, and 1 for no length.
140pub fn hash_quarter_length(length: FloatType) -> u8 {
141    if length == 0.0 {
142        return 1;
143    }
144    let code = ((length * 256.0).log2() * 10.0) as i64;
145    code.clamp(1, 127) as u8
146}
147
148/// The character a note or chord of a length is written as: music21's
149/// `hashNote`, which is [`hash_quarter_length`] made even.
150pub fn hash_note(length: FloatType) -> char {
151    let code = hash_quarter_length(length);
152    char::from(if code.is_multiple_of(2) {
153        code
154    } else {
155        code + 1
156    })
157}
158
159/// The character a rest of a length is written as: music21's `hashRest`,
160/// which is [`hash_quarter_length`] made odd.
161pub fn hash_rest(length: FloatType) -> char {
162    let code = hash_quarter_length(length);
163    char::from(if code.is_multiple_of(2) {
164        code + 1
165    } else {
166        code
167    })
168}
169
170/// The character anything of no length is written as: music21's
171/// `hashGrace`, which writes a grace note as a 128th.
172pub fn hash_grace() -> char {
173    char::from(hash_quarter_length(0.015625))
174}
175
176/// How unlike two rhythms are, as music21's `getMeasureDifference` has it:
177/// one less their `difflib` likeness, except that the same rhythm is as
178/// unlike as can be, one.
179pub fn measure_difference(own: &str, other: &str) -> FloatType {
180    difference(&chars(own), &chars(other))
181}
182
183fn chars(hash: &str) -> Vec<char> {
184    hash.chars().collect()
185}
186
187fn difference(own: &[char], other: &[char]) -> FloatType {
188    let ratio = difflib::ratio(own, other);
189    1.0 - if ratio == 1.0 { 0.0 } else { ratio }
190}
191
192/// The steps that turn one rhythm into another: Python's `difflib` opcodes,
193/// music21's `getOpCodes`.
194pub fn opcodes(own: &str, other: &str) -> Vec<Opcode> {
195    difflib::opcodes(&chars(own), &chars(other))
196}
197
198/// How likely `other` was misread as `own`, from the steps that turn the
199/// one into the other: music21's `getProbabilityBasedOnChanges`. Each equal
200/// note is [`PROBABILITY_ON_EQUALITY`], each one missed
201/// [`PROBABILITY_ON_OMISSION`], each one added [`PROBABILITY_ON_ADDITION`],
202/// and a stretch replaced is [`probability_on_substitute`].
203pub fn probability_based_on_changes(own: &str, other: &str) -> FloatType {
204    changes(&chars(own), &chars(other))
205}
206
207fn changes(own: &[char], other: &[char]) -> FloatType {
208    changes_between(own, other, own)
209}
210
211/// How likely the measure `source` was misread as `destination`, with the
212/// steps read between `matching` and `source`: music21's
213/// `getProbabilityBasedOnChanges` with its two strings told apart.
214///
215/// music21 reads its steps off whatever its `SequenceMatcher` was set
216/// from and reads a replacement off its own hash, which are the same
217/// string in every call it makes -- [`probability_based_on_changes`] is
218/// that call -- but a caller may set the one and not the other.
219pub fn probability_based_on_changes_between(
220    matching: &str,
221    source: &str,
222    destination: &str,
223) -> FloatType {
224    changes_between(&chars(matching), &chars(source), &chars(destination))
225}
226
227fn changes_between(matching: &[char], source: &[char], destination: &[char]) -> FloatType {
228    let mut probability = 0.0;
229    for (index, step) in difflib::opcodes(matching, source).iter().enumerate() {
230        let one = one_opcode(step, source, destination);
231        if index == 0 {
232            probability = one;
233        } else {
234            probability *= one;
235        }
236    }
237    probability
238}
239
240/// How likely one of the steps that turn a rhythm into another is:
241/// music21's `differenceProbabilityForOneOpCode`.
242///
243/// `source` is the measure that would do the correcting and `destination`
244/// the measure flagged, which is how music21 names them. A stretch read
245/// alike is [`PROBABILITY_ON_EQUALITY`] for each character, a stretch
246/// replaced is [`probability_on_substitute`] of the two, a stretch the
247/// flagged measure has not got is [`PROBABILITY_ON_OMISSION`] for each and
248/// one it has over is [`PROBABILITY_ON_ADDITION`].
249pub fn probability_for_one_opcode(step: &Opcode, source: &str, destination: &str) -> FloatType {
250    one_opcode(step, &chars(source), &chars(destination))
251}
252
253fn one_opcode(step: &Opcode, source: &[char], destination: &[char]) -> FloatType {
254    match step.tag {
255        OpcodeTag::Equal => PROBABILITY_ON_EQUALITY.powf((step.j2 - step.j1) as FloatType),
256        OpcodeTag::Replace => substitute(&source[step.j1..step.j2], &destination[step.i1..step.i2]),
257        OpcodeTag::Insert => PROBABILITY_ON_OMISSION.powf((step.j2 - step.j1) as FloatType),
258        OpcodeTag::Delete => PROBABILITY_ON_ADDITION.powf((step.i2 - step.i1) as FloatType),
259    }
260}
261
262/// How likely the rhythm `source` was misread as `destination`: music21's
263/// `getProbabilityOnSubstitute`. The longer is cut to the shorter, each
264/// character cut an addition or an omission, and the rest compared
265/// character by character ([`probability_from_one_char_sub`]).
266pub fn probability_on_substitute(source: &str, destination: &str) -> FloatType {
267    substitute(&chars(source), &chars(destination))
268}
269
270fn substitute(source: &[char], destination: &[char]) -> FloatType {
271    let (mut source, mut destination) = (source, destination);
272    let mut probability = 1.0;
273    if source.len() > destination.len() {
274        let additions = source.len() - destination.len();
275        probability = PROBABILITY_ON_ADDITION.powf(additions as FloatType);
276        source = &source[..source.len() - additions];
277    } else if source.len() < destination.len() {
278        let omissions = destination.len() - source.len();
279        probability = PROBABILITY_ON_OMISSION.powf(omissions as FloatType);
280        destination = &destination[..destination.len() - omissions];
281    }
282    for (from, to) in source.iter().zip(destination) {
283        probability *= probability_from_one_char_sub(*from, *to);
284    }
285    probability
286}
287
288/// How likely one length was misread as another: music21's
289/// `getProbabilityFromOneCharSub`. A length doubled or halved any number of
290/// times is 0.0165 for each; a rest read for a note of the same length an
291/// addition, the other way an omission; a note read as a rest 0.003; and
292/// anything else an omission and an addition at once.
293pub fn probability_from_one_char_sub(source: char, destination: char) -> FloatType {
294    let difference = source as i64 - destination as i64;
295    let distance = difference.abs() as FloatType;
296    if difference == 0 {
297        1.0
298    } else if distance % 10.0 == 0.0 {
299        0.0165_f64.powf(distance / 10.0)
300    } else if difference == 6 {
301        PROBABILITY_ON_ADDITION
302    } else if difference == -6 {
303        PROBABILITY_ON_OMISSION
304    } else if distance % 2.0 != 0.0 {
305        0.003
306    } else {
307        PROBABILITY_ON_OMISSION * PROBABILITY_ON_ADDITION
308    }
309}
310
311/// The best of some probabilities, and the first that is as good: where
312/// music21 corrects a measure from.
313fn best(probabilities: &[FloatType]) -> (usize, FloatType) {
314    let most = probabilities
315        .iter()
316        .copied()
317        .fold(FloatType::NEG_INFINITY, FloatType::max);
318    let at = probabilities.iter().position(|&p| p == most).unwrap_or(0);
319    (at, most)
320}
321
322/// The rhythm of every measure of a part: music21's
323/// `SinglePart.getSequenceHashesFromMeasureStream`.
324///
325/// # Errors
326///
327/// A measure of voices that cannot be chordified.
328pub fn part_hashes(part: &Stream) -> Result<Vec<String>> {
329    ScoreCorrector::measure_events(part)
330        .into_iter()
331        .map(|index| match part.events()[index].element() {
332            StreamElement::Stream(measure) => measure_hash(measure),
333            _ => unreachable!("a measure's event holds the measure"),
334        })
335        .collect()
336}
337
338/// Which of a part's measures do not fill their bar, and so would be
339/// flagged by an optical reader: music21's
340/// `SinglePart.getIncorrectMeasureIndices`.
341///
342/// With `run_fast`, every bar is that of the first measure's time
343/// signature, or of 4/4 where none is in force; without, each measure's
344/// own. The places are counted from nought, as music21 counts them, and
345/// are not measure numbers.
346///
347/// # Errors
348///
349/// Without `run_fast`, a measure with no time signature in force, which
350/// music21 fails on.
351pub fn incorrect_measures(part: &Stream, run_fast: bool) -> Result<Vec<usize>> {
352    let measures = ScoreCorrector::measure_events(part);
353    let meter_of = |index: usize| -> Option<TimeSignature> {
354        let event = &part.events()[index];
355        let StreamElement::Stream(measure) = event.element() else {
356            return None;
357        };
358        measure
359            .events()
360            .iter()
361            .take_while(|inner| inner.offset() == 0.0)
362            .find_map(|inner| match inner.element() {
363                StreamElement::TimeSignature(meter) => Some(meter.clone()),
364                _ => None,
365            })
366            .or_else(|| part.time_signature_at(event.offset()))
367    };
368    let common_time = || TimeSignature::new(4, 4);
369    let mut meter = if run_fast {
370        match measures.first().and_then(|&index| meter_of(index)) {
371            Some(meter) => meter,
372            None => common_time()?,
373        }
374    } else {
375        common_time()?
376    };
377    let mut incorrect = Vec::new();
378    for (i, &index) in measures.iter().enumerate() {
379        if !run_fast {
380            meter = meter_of(index).ok_or_else(|| {
381                Error::Omr(format!("no time signature in force in measure {index}"))
382            })?;
383        }
384        if part.events()[index].element().quarter_length() != meter.bar_quarter_length() {
385            incorrect.push(i);
386        }
387    }
388    Ok(incorrect)
389}
390
391/// Which measure of one place across the parts most likely corrects the
392/// flagged one there: music21's `MeasureSlice.runSliceSearch`.
393///
394/// `hashes` is the rhythm of that measure in every part and `flagged`
395/// says whose is itself flagged, since a flagged measure corrects
396/// nothing; `distribution` is how often each part's measures read like
397/// the flagged part's, which is one row of
398/// [`ScoreCorrector::vertical_probability_dist`]. The likeliest is the
399/// first of those as likely, and a part that cannot correct counts as
400/// nothing at all.
401pub fn slice_search(
402    hashes: &[String],
403    flagged: &[bool],
404    distribution: &[FloatType],
405    part: usize,
406    measure: usize,
407) -> MeasureRelationship {
408    let mut probabilities = Vec::with_capacity(hashes.len());
409    for (k, hash) in hashes.iter().enumerate() {
410        let cannot = k == part || flagged.get(k).copied().unwrap_or(false);
411        if cannot {
412            probabilities.push(0.0);
413            continue;
414        }
415        let likely = probability_based_on_changes(&hashes[part], hash);
416        probabilities.push(likely * distribution.get(k).copied().unwrap_or(0.0));
417    }
418    let (at, most) = best(&probabilities);
419    MeasureRelationship {
420        flagged_measure_part: part,
421        flagged_measure_index: measure,
422        correct_measure_part: at,
423        correct_measure_index: measure,
424        correction_probability: most,
425    }
426}
427
428/// One part of a score being corrected, its measures' rhythms and those
429/// flagged: music21's `SinglePart`.
430#[derive(Clone, Debug, PartialEq)]
431#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
432pub struct SinglePart {
433    part_number: usize,
434    hashed_notes: Vec<String>,
435    incorrect_measures: Vec<usize>,
436    probability_distribution: Option<Vec<FloatType>>,
437    index_array: Option<Vec<i64>>,
438}
439
440impl SinglePart {
441    /// One part read on its own, its measures hashed and those not
442    /// filling their bar flagged: music21's `SinglePart(part, pn)`, whose
443    /// own constructor does both.
444    ///
445    /// # Errors
446    ///
447    /// A measure of voices that cannot be chordified.
448    pub fn from_part(part: &Stream, number: usize) -> Result<Self> {
449        Ok(Self {
450            part_number: number,
451            hashed_notes: part_hashes(part)?,
452            incorrect_measures: incorrect_measures(part, true)?,
453            probability_distribution: None,
454            index_array: None,
455        })
456    }
457
458    /// The part's place among the score's parts.
459    pub fn part_number(&self) -> usize {
460        self.part_number
461    }
462
463    /// The rhythm of each measure, as [`measure_hash`] writes it, as they
464    /// stood when the corrector was made or the part last corrected:
465    /// music21's `hashedNotes`.
466    pub fn hashed_notes(&self) -> &[String] {
467        &self.hashed_notes
468    }
469
470    /// The indices of the measures whose notes do not fill their bars:
471    /// music21's `incorrectMeasures`.
472    pub fn incorrect_measures(&self) -> &[usize] {
473        &self.incorrect_measures
474    }
475
476    /// For each distance from one measure to another, from one less than
477    /// the number of measures back to as many forward, the share of
478    /// measures whose rhythm is like the one that far away -- as music21
479    /// counts likeness, where the same rhythm and a wholly different one
480    /// both count, and the distance nought counts every measure: music21's
481    /// `horizontalProbabilityDist`. Worked out once and kept.
482    pub fn horizontal_probability_dist(&mut self) -> &[FloatType] {
483        if self.probability_distribution.is_none() {
484            let count = self.hashed_notes.len();
485            let hashes: Vec<Vec<char>> = self.hashed_notes.iter().map(|hash| chars(hash)).collect();
486            let mut all = vec![0.0; count * 2];
487            let mut indices = vec![0_i64; count * 2];
488            for i in 0..count {
489                for k in 0..count {
490                    let at = count + k - i;
491                    indices[at] = k as i64 - i as i64;
492                    if i == k {
493                        all[at] = count as FloatType;
494                    } else if difference(&hashes[i], &hashes[k]) == 1.0 {
495                        all[at] += 1.0;
496                    }
497                }
498            }
499            if !indices.is_empty() {
500                indices.remove(0);
501                all.remove(0);
502            }
503            self.index_array = Some(indices);
504            self.probability_distribution =
505                Some(all.iter().map(|value| value / count as FloatType).collect());
506        }
507        self.probability_distribution.as_deref().unwrap_or_default()
508    }
509
510    /// The distance from one measure to another each entry of
511    /// [`Self::horizontal_probability_dist`] is for, once it has been worked
512    /// out: music21's `indexArray`.
513    pub fn index_array(&self) -> Option<&[i64]> {
514        self.index_array.as_deref()
515    }
516
517    /// How likely a measure as far from another as `source` is from
518    /// `destination` has its rhythm: music21's `getProbabilityDistribution`.
519    pub fn probability_distribution(&mut self, source: usize, destination: usize) -> FloatType {
520        let count = self.hashed_notes.len();
521        let index = source + count - 1 - destination;
522        self.horizontal_probability_dist()[index]
523    }
524
525    /// The measure of this part most likely to correct the `i`th flagged
526    /// one: of those not flagged, the one most likely misread as it by its
527    /// changes, times how likely its distance is, the first of those as
528    /// likely: music21's `runHorizontalSearch`.
529    pub fn run_horizontal_search(&mut self, i: usize) -> MeasureRelationship {
530        self.horizontal_probability_dist();
531        let incorrect = self.incorrect_measures[i];
532        let own = chars(&self.hashed_notes[incorrect]);
533        let mut probabilities = Vec::with_capacity(self.hashed_notes.len());
534        for k in 0..self.hashed_notes.len() {
535            if self.incorrect_measures.contains(&k) {
536                probabilities.push(0.0);
537            } else {
538                let likely = changes(&own, &chars(&self.hashed_notes[k]));
539                probabilities.push(likely * self.probability_distribution(k, incorrect));
540            }
541        }
542        let (at, most) = best(&probabilities);
543        MeasureRelationship {
544            flagged_measure_part: self.part_number,
545            flagged_measure_index: incorrect,
546            correct_measure_part: self.part_number,
547            correct_measure_index: at,
548            correction_probability: most,
549        }
550    }
551
552    /// [`Self::run_horizontal_search`] for every flagged measure: music21's
553    /// `runHorizontalCorrectionModel`.
554    pub fn run_horizontal_correction_model(&mut self) -> Vec<MeasureRelationship> {
555        (0..self.incorrect_measures.len())
556            .map(|i| self.run_horizontal_search(i))
557            .collect()
558    }
559}
560
561/// A score being corrected, part by part: music21's `ScoreCorrector`.
562///
563/// ```
564/// use music21::omr::correctors::ScoreCorrector;
565/// use music21::tinynotation::from_tiny_notation;
566/// use music21::{Stream, StreamKind};
567///
568/// // The third bar is a quarter short.
569/// let part = from_tiny_notation("4/4 c4 d e f g a b c' d'4 e' f'")?;
570/// let mut score = Stream::with_kind(StreamKind::Score);
571/// score.insert(0.0, part);
572///
573/// let mut corrector = ScoreCorrector::new(score)?;
574/// assert_eq!(corrector.single_parts()[0].incorrect_measures(), [2]);
575/// corrector.run()?;
576/// assert_eq!(corrector.single_parts()[0].hashed_notes()[2], "PPPP");
577/// # Ok::<(), music21::Error>(())
578/// ```
579#[derive(Clone, Debug)]
580pub struct ScoreCorrector {
581    score: Stream,
582    single_parts: Vec<SinglePart>,
583    /// Where each part stands among the score's events.
584    part_events: Vec<usize>,
585    distribution: Option<Vec<Vec<FloatType>>>,
586    /// The rhythms of the measures at each place across the parts, as they
587    /// stood when that place was first searched.
588    slices: HashMap<usize, Vec<String>>,
589}
590
591impl ScoreCorrector {
592    /// A corrector for a score: each part's measures hashed and those not
593    /// filling the bar of the score's first time signature flagged.
594    ///
595    /// # Errors
596    ///
597    /// A measure of voices that cannot be chordified.
598    pub fn new(score: Stream) -> Result<Self> {
599        let part_events: Vec<usize> = score
600            .events()
601            .iter()
602            .enumerate()
603            .filter_map(|(index, event)| match event.element() {
604                StreamElement::Stream(inner)
605                    if matches!(inner.kind(), StreamKind::Part | StreamKind::PartStaff) =>
606                {
607                    Some(index)
608                }
609                _ => None,
610            })
611            .collect();
612        let mut corrector = Self {
613            score,
614            single_parts: Vec::new(),
615            part_events,
616            distribution: None,
617            slices: HashMap::new(),
618        };
619        for part_number in 0..corrector.part_events.len() {
620            let single = SinglePart::from_part(corrector.part(part_number), part_number)?;
621            corrector.single_parts.push(single);
622        }
623        Ok(corrector)
624    }
625
626    /// The score, as corrected so far.
627    pub fn score(&self) -> &Stream {
628        &self.score
629    }
630
631    /// The score, as corrected so far, given back.
632    pub fn into_score(self) -> Stream {
633        self.score
634    }
635
636    /// The parts being corrected: music21's `singleParts`.
637    pub fn single_parts(&self) -> &[SinglePart] {
638        &self.single_parts
639    }
640
641    /// One part, to run its horizontal model on its own.
642    pub fn single_part_mut(&mut self, part: usize) -> &mut SinglePart {
643        &mut self.single_parts[part]
644    }
645
646    /// Every part's measure rhythms: music21's `getAllHashes`.
647    pub fn all_hashes(&self) -> Vec<&[String]> {
648        self.single_parts
649            .iter()
650            .map(SinglePart::hashed_notes)
651            .collect()
652    }
653
654    /// Every part's flagged measures: music21's `getAllIncorrectMeasures`.
655    pub fn all_incorrect_measures(&self) -> Vec<&[usize]> {
656        self.single_parts
657            .iter()
658            .map(SinglePart::incorrect_measures)
659            .collect()
660    }
661
662    fn part(&self, part: usize) -> &Stream {
663        match self.score.events()[self.part_events[part]].element() {
664            StreamElement::Stream(inner) => inner,
665            _ => unreachable!("a part's event holds the part"),
666        }
667    }
668
669    /// The events of a part that are its measures.
670    fn measure_events(part: &Stream) -> Vec<usize> {
671        part.events()
672            .iter()
673            .enumerate()
674            .filter_map(|(index, event)| match event.element() {
675                StreamElement::Stream(inner) if inner.kind() == StreamKind::Measure => Some(index),
676                _ => None,
677            })
678            .collect()
679    }
680
681    fn hash_part(&self, part: usize) -> Result<Vec<String>> {
682        part_hashes(self.part(part))
683    }
684
685    /// Flags a part's measures whose notes do not fill their bar, and
686    /// gives them back: music21's `getIncorrectMeasureIndices`. With
687    /// `run_fast`, every bar is that of the first measure's time signature,
688    /// or of 4/4 where none is in force; without, each measure's own.
689    ///
690    /// # Errors
691    ///
692    /// Without `run_fast`, a measure with no time signature in force,
693    /// which music21 fails on.
694    pub fn find_incorrect_measures(&mut self, part: usize, run_fast: bool) -> Result<&[usize]> {
695        self.single_parts[part].incorrect_measures = incorrect_measures(self.part(part), run_fast)?;
696        Ok(&self.single_parts[part].incorrect_measures)
697    }
698
699    /// Every part's horizontal model: music21's
700    /// `runHorizontalCorrectionModel`.
701    pub fn run_horizontal_correction_model(&mut self) -> Vec<Vec<MeasureRelationship>> {
702        self.single_parts
703            .iter_mut()
704            .map(SinglePart::run_horizontal_correction_model)
705            .collect()
706    }
707
708    /// For each part, the share of its measures whose rhythm is like that
709    /// of the measure at the same place in each part, as music21 counts
710    /// likeness: music21's `verticalProbabilityDist`. Worked out once and
711    /// kept.
712    ///
713    /// # Errors
714    ///
715    /// Parts of different lengths, or one with no measures, which music21
716    /// fails on.
717    pub fn vertical_probability_dist(&mut self) -> Result<&[Vec<FloatType>]> {
718        if self.distribution.is_none() {
719            let mut distribution = Vec::with_capacity(self.single_parts.len());
720            for part in 0..self.single_parts.len() {
721                distribution.push(self.vertical_probability_dist_of_part(part)?);
722            }
723            self.distribution = Some(distribution);
724        }
725        Ok(self.distribution.as_deref().unwrap_or_default())
726    }
727
728    /// How often each part's measures read like one part's, that part's own
729    /// counting for one: music21's
730    /// `getVerticalProbabilityDistributionSinglePart`.
731    ///
732    /// # Errors
733    ///
734    /// A part with no measures, or one shorter than this part.
735    pub fn vertical_probability_dist_of_part(&self, part: usize) -> Result<Vec<FloatType>> {
736        let measures = self
737            .single_parts
738            .get(part)
739            .ok_or_else(|| Error::Omr(format!("no part {part}")))?
740            .hashed_notes
741            .len();
742        if measures == 0 {
743            return Err(Error::Omr(format!("part {part} has no measures")));
744        }
745        let mut sums = vec![0.0; self.single_parts.len()];
746        for measure in 0..measures {
747            for (sum, alike) in sums
748                .iter_mut()
749                .zip(self.vertical_probability_dist_of_measure(part, measure)?)
750            {
751                *sum += alike;
752            }
753        }
754        Ok(sums.iter().map(|sum| sum / measures as FloatType).collect())
755    }
756
757    /// Which parts read one measure of one part exactly alike, that part's
758    /// own counting for one: music21's
759    /// `getVerticalProbabilityDistributionSinglePartSingleMeasure`.
760    ///
761    /// # Errors
762    ///
763    /// A part or a measure there is none of.
764    pub fn vertical_probability_dist_of_measure(
765        &self,
766        part: usize,
767        measure: usize,
768    ) -> Result<Vec<FloatType>> {
769        let hash = self
770            .single_parts
771            .get(part)
772            .and_then(|single| single.hashed_notes.get(measure))
773            .ok_or_else(|| Error::Omr(format!("no measure {measure} in part {part}")))?;
774        let mut alike = Vec::with_capacity(self.single_parts.len());
775        for (other, single) in self.single_parts.iter().enumerate() {
776            if other == part {
777                alike.push(1.0);
778                continue;
779            }
780            let their = single
781                .hashed_notes
782                .get(measure)
783                .ok_or_else(|| Error::Omr(format!("no measure {measure} in part {other}")))?;
784            alike.push(if measure_difference(hash, their) == 1.0 {
785                1.0
786            } else {
787                0.0
788            });
789        }
790        Ok(alike)
791    }
792
793    /// The rhythm of one measure in every part: music21's
794    /// `MeasureSlice.getSliceHashes`, the slice its `getMeasureSlice`
795    /// makes.
796    ///
797    /// # Errors
798    ///
799    /// A measure there is none of in some part, or one of voices that
800    /// cannot be chordified.
801    pub fn slice_hashes(&mut self, measure: usize) -> Result<&[String]> {
802        if !self.slices.contains_key(&measure) {
803            let mut hashes = Vec::with_capacity(self.single_parts.len());
804            for number in 0..self.single_parts.len() {
805                let stream = self.part(number);
806                let index = *Self::measure_events(stream)
807                    .get(measure)
808                    .ok_or_else(|| Error::Omr(format!("no measure {measure} in part {number}")))?;
809                let StreamElement::Stream(inner) = stream.events()[index].element() else {
810                    unreachable!("a measure's event holds the measure");
811                };
812                hashes.push(measure_hash(inner)?);
813            }
814            self.slices.insert(measure, hashes);
815        }
816        Ok(&self.slices[&measure])
817    }
818
819    /// The measure at the same place in another part most likely to
820    /// correct a flagged one: of the parts whose measure there is not
821    /// flagged, the one most likely misread as it by its changes, times how
822    /// often the two parts' rhythms are alike, the first of those as
823    /// likely: music21's `runVerticalSearch`.
824    ///
825    /// # Errors
826    ///
827    /// As [`Self::vertical_probability_dist`], or a measure of voices that
828    /// cannot be chordified.
829    pub fn run_vertical_search(
830        &mut self,
831        measure: usize,
832        part: usize,
833    ) -> Result<MeasureRelationship> {
834        self.vertical_probability_dist()?;
835        self.slice_hashes(measure)?;
836        let flagged: Vec<bool> = self
837            .single_parts
838            .iter()
839            .map(|single| single.incorrect_measures.contains(&measure))
840            .collect();
841        let hashes = &self.slices[&measure];
842        let distribution = self.distribution.as_deref().unwrap_or_default();
843        Ok(slice_search(
844            hashes,
845            &flagged,
846            distribution.get(part).map_or(&[][..], Vec::as_slice),
847            part,
848            measure,
849        ))
850    }
851
852    /// [`Self::run_vertical_search`] for every flagged measure of every
853    /// part: music21's `runVerticalCorrectionModel`.
854    ///
855    /// # Errors
856    ///
857    /// As [`Self::run_vertical_search`].
858    pub fn run_vertical_correction_model(&mut self) -> Result<Vec<Vec<MeasureRelationship>>> {
859        self.vertical_probability_dist()?;
860        let mut all = Vec::with_capacity(self.single_parts.len());
861        for part in 0..self.single_parts.len() {
862            let flagged = self.single_parts[part].incorrect_measures.clone();
863            all.push(
864                flagged
865                    .into_iter()
866                    .map(|measure| self.run_vertical_search(measure, part))
867                    .collect::<Result<Vec<_>>>()?,
868            );
869        }
870        Ok(all)
871    }
872
873    /// Puts the contents of one measure in another's place, the notes
874    /// keeping the pitches the replaced measure's notes had, in order, as
875    /// far as they go: music21's `substituteOneMeasureContentsForAnother`.
876    ///
877    /// As music21 does, everything is appended one after another, a
878    /// measure's right barline and its voices included: a barline ends up
879    /// inside the measure, and voices one after another rather than
880    /// together. Spanners naming the replaced measure's notes name nothing
881    /// afterwards. A measure put in its own place is emptied, as music21
882    /// empties it before copying from it.
883    ///
884    /// # Errors
885    ///
886    /// A pitch whose accidental cannot be written again from its modifier.
887    ///
888    /// # Panics
889    ///
890    /// A part or measure past the last.
891    pub fn substitute_measure(
892        &mut self,
893        source_measure: usize,
894        source_part: usize,
895        destination_measure: usize,
896        destination_part: usize,
897    ) -> Result<()> {
898        let source = if (source_part, source_measure) == (destination_part, destination_measure) {
899            Stream::with_kind(StreamKind::Measure)
900        } else {
901            let stream = self.part(source_part);
902            let index = Self::measure_events(stream)[source_measure];
903            match stream.events()[index].element() {
904                StreamElement::Stream(inner) => (**inner).clone(),
905                _ => unreachable!("a measure's event holds the measure"),
906            }
907        };
908        let destination = self.part(destination_part);
909        let index = Self::measure_events(destination)[destination_measure];
910        let StreamElement::Stream(measure) = destination.events()[index].element() else {
911            unreachable!("a measure's event holds the measure");
912        };
913        let old_pitches: Vec<crate::pitch::Pitch> = measure
914            .events()
915            .iter()
916            .filter_map(|event| match event.element() {
917                StreamElement::Note(note) => Some(note.pitch().clone()),
918                _ => None,
919            })
920            .collect();
921        // What music21 iterates: the elements in order, the left barline
922        // among them at the start, and the right barline after them all.
923        let mut elements: Vec<StreamEvent> = source.events().to_vec();
924        if let Some(barline) = source.left_barline() {
925            let at = elements
926                .iter()
927                .position(|event| event.offset() > 0.0 || event.element().class_sort_order() > -5)
928                .unwrap_or(elements.len());
929            elements.insert(
930                at,
931                StreamEvent::new(0.0, StreamElement::Barline(barline.clone())),
932            );
933        }
934        if let Some(barline) = source.right_barline() {
935            elements.push(StreamEvent::new(
936                0.0,
937                StreamElement::Barline(barline.clone()),
938            ));
939        }
940        let mut contents = Stream::with_kind(StreamKind::Measure);
941        let (mut left, mut pitch_index) = (None, 0);
942        for event in elements {
943            let mut element = event.element().clone();
944            if let StreamElement::Note(note) = &mut element
945                && let Some(old) = old_pitches.get(pitch_index)
946            {
947                let mut pitch = note.pitch().clone();
948                pitch.set_octave(old.octave());
949                pitch.take_name_of(old)?;
950                note.set_pitch(pitch);
951                pitch_index += 1;
952            }
953            let offset = contents.end_offset();
954            match element {
955                // A barline at the start is the measure's left barline.
956                StreamElement::Barline(barline) if offset == 0.0 && left.is_none() => {
957                    left = Some(barline);
958                }
959                element => contents.push(element),
960            }
961        }
962        let mut replaced = measure.with_events(contents.events().to_vec());
963        replaced.set_left_barline(left);
964        replaced.set_right_barline(None);
965        let path = [self.part_events[destination_part], index];
966        self.score.replace_nested(&path, replaced);
967        Ok(())
968    }
969
970    /// Corrects each flagged measure both models found a correction for,
971    /// from the horizontal model's measure where it is more likely, and
972    /// from the vertical model's otherwise, then hashes each part's
973    /// measures again: music21's `generateCorrectedScore`. Corrections are
974    /// made in turn, so a measure corrected may correct another after it.
975    ///
976    /// # Errors
977    ///
978    /// A measure of voices that cannot be chordified.
979    pub fn generate_corrected_score(
980        &mut self,
981        horizontal: &[Vec<MeasureRelationship>],
982        vertical: &[Vec<MeasureRelationship>],
983    ) -> Result<PriorsIntegrationScore> {
984        let mut score = PriorsIntegrationScore::default();
985        for part in 0..self.single_parts.len() {
986            let out_of_range = || Error::Omr(format!("no relationships given for part {part}"));
987            let across = horizontal.get(part).ok_or_else(out_of_range)?;
988            for h in across {
989                for v in vertical.get(part).ok_or_else(out_of_range)? {
990                    if h.flagged_measure_part != v.flagged_measure_part
991                        || h.flagged_measure_index != v.flagged_measure_index
992                    {
993                        continue;
994                    }
995                    score.total += 1;
996                    let source = if h.correction_probability > v.correction_probability {
997                        score.horizontal += 1;
998                        h
999                    } else {
1000                        score.vertical += 1;
1001                        v
1002                    };
1003                    self.substitute_measure(
1004                        source.correct_measure_index,
1005                        source.correct_measure_part,
1006                        h.flagged_measure_index,
1007                        h.flagged_measure_part,
1008                    )?;
1009                }
1010            }
1011            self.single_parts[part].hashed_notes = self.hash_part(part)?;
1012        }
1013        Ok(score)
1014    }
1015
1016    /// Corrects the score by both models: music21's `run` and
1017    /// `runPriorModel`. The score corrected is [`Self::score`].
1018    ///
1019    /// # Errors
1020    ///
1021    /// As [`Self::run_vertical_correction_model`].
1022    pub fn run(&mut self) -> Result<PriorsIntegrationScore> {
1023        let horizontal = self.run_horizontal_correction_model();
1024        let vertical = self.run_vertical_correction_model()?;
1025        self.generate_corrected_score(&horizontal, &vertical)
1026    }
1027}
1028
1029#[cfg(test)]
1030mod tests {
1031    use super::*;
1032
1033    #[test]
1034    fn lengths_are_hashed_as_music21_hashes_them() {
1035        assert_eq!(hash_quarter_length(1.0), 80);
1036        assert_eq!(hash_quarter_length(0.015625), 20);
1037        assert_eq!(hash_quarter_length(0.0), 1);
1038        assert_eq!(hash_quarter_length(1000.0), 127);
1039    }
1040
1041    /// music21's `hashNote`, `hashRest` and `hashQuarterLength`
1042    /// docstrings, and the measure its `getHashString` writes `VFUF` for.
1043    #[test]
1044    fn a_note_is_written_as_music21_writes_it() -> Result<()> {
1045        assert_eq!(hash_quarter_length(1.0), 80);
1046        assert_eq!(hash_quarter_length(2.0), 90);
1047        assert_eq!(hash_note(1.0), 'P');
1048        assert_eq!(hash_note(2.0), 'Z');
1049        assert_eq!(hash_note(1.5), 'V');
1050        assert_eq!(hash_rest(1.0), 'Q');
1051        // A grace note is written as a 128th.
1052        assert_eq!(hash_grace(), char::from(hash_quarter_length(0.015625)));
1053        let mut measure = Stream::with_kind(StreamKind::Measure);
1054        for (name, length) in [("C4", 1.5), ("C4", 0.5)] {
1055            measure.push(
1056                crate::note::Note::from_name(name)?
1057                    .with_duration(crate::duration::Duration::new(length)?),
1058            );
1059        }
1060        measure.push(crate::Rest::new(crate::duration::Duration::new(1.5)?));
1061        measure.push(
1062            crate::note::Note::from_name("B4")?.with_duration(crate::duration::Duration::new(0.5)?),
1063        );
1064        assert_eq!(measure_hash(&measure)?, "VFUF");
1065        assert_eq!(measure_difference("VFUF", "VGUF"), 0.25);
1066        assert_eq!(measure_difference("VFUF", "VFUF"), 1.0);
1067        Ok(())
1068    }
1069
1070    /// music21's `differenceProbabilityForOneOpCode` docstring: one step
1071    /// of each kind, between the rhythms it names.
1072    #[test]
1073    fn one_step_of_a_correction_is_as_likely_as_music21_has_it() {
1074        let step = |tag, i1, i2, j1, j2| Opcode {
1075            tag,
1076            i1,
1077            i2,
1078            j1,
1079            j2,
1080        };
1081        assert_eq!(
1082            probability_for_one_opcode(&step(OpcodeTag::Equal, 0, 4, 0, 4), "PFPFFF", "PFPFGF"),
1083            0.876_201_303_164_062_6
1084        );
1085        assert_eq!(
1086            probability_for_one_opcode(&step(OpcodeTag::Insert, 4, 4, 4, 5), "PFPFFF", "PFPFGF"),
1087            0.009
1088        );
1089        assert_eq!(
1090            probability_for_one_opcode(&step(OpcodeTag::Replace, 2, 4, 2, 4), "PPPPP", "PPVZP"),
1091            0.000_148_5
1092        );
1093        assert_eq!(
1094            probability_for_one_opcode(&step(OpcodeTag::Delete, 0, 5, 0, 0), "e", "GFPGF"),
1095            1.024e-12
1096        );
1097        // The whole correction is every step multiplied, which is
1098        // music21's `getProbabilityBasedOnChanges`.
1099        assert_eq!(
1100            probability_based_on_changes("GFPGF", "e"),
1101            2.947_283_212_5e-14
1102        );
1103    }
1104
1105    #[test]
1106    fn a_rhythm_misread_is_as_likely_as_music21_has_it() {
1107        // Read off music21's MeasureHash methods.
1108        assert_eq!(probability_from_one_char_sub('P', 'P'), 1.0);
1109        assert_eq!(probability_from_one_char_sub('Z', 'P'), 0.0165);
1110        assert_eq!(
1111            probability_from_one_char_sub('V', 'P'),
1112            PROBABILITY_ON_ADDITION
1113        );
1114        assert_eq!(probability_from_one_char_sub('Q', 'P'), 0.003);
1115        assert_eq!(measure_difference("PPPP", "PPPP"), 1.0);
1116        assert_eq!(measure_difference("", ""), 1.0);
1117        assert_eq!(measure_difference("PP", "ZZ"), 1.0);
1118    }
1119}
music21/omr/correctors.rs

music21/omr/
correctors.rs
