music21/alpha/analysis/
aligner.rs

1//! Two streams aligned note by note, as an edit from one to the other:
2//! music21's `alpha.analysis.aligner`.
3
4use super::hasher::{HashReference, HashValue, Hasher, NoteHash};
5use crate::{
6    defaults::FloatType,
7    error::{Error, Result},
8    stream::Stream,
9};
10
11/// What becomes of a note from the target to the source: music21's
12/// `ChangeOps`.
13#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub enum ChangeOp {
16    /// A note in the target and not the source.
17    Insertion,
18    /// A note in the source and not the target.
19    Deletion,
20    /// A note changed.
21    Substitution,
22    /// A note the same in both.
23    NoChange,
24}
25
26impl ChangeOp {
27    /// The colour music21 shows a change in.
28    pub fn color(self) -> Option<&'static str> {
29        match self {
30            Self::Insertion => Some("green"),
31            Self::Deletion => Some("red"),
32            Self::Substitution => Some("purple"),
33            Self::NoChange => None,
34        }
35    }
36
37    fn from_index(index: usize) -> Self {
38        match index {
39            0 => Self::Insertion,
40            1 => Self::Deletion,
41            2 => Self::Substitution,
42            _ => Self::NoChange,
43        }
44    }
45}
46
47/// A change from the target to the source: the target's note, the
48/// source's, and what became of it.
49#[derive(Clone, Copy, Debug, PartialEq, Eq)]
50#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
51pub struct Change {
52    /// The target's note.
53    pub target: Option<HashReference>,
54    /// The source's note.
55    pub source: Option<HashReference>,
56    /// What became of it.
57    pub op: ChangeOp,
58}
59
60/// Where a change stands: the places music21 reads the two hashes from,
61/// and what became of the note.
62///
63/// The places are music21's own: it reads `hashedTargetStream[i - 1]` with
64/// `i` as low as nought, which Python reads as the last hash, so the place
65/// for the cell at the top or the left edge is the last of its list.
66#[derive(Clone, Copy, Debug, PartialEq, Eq)]
67#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
68pub struct ChangePlace {
69    /// Which of the target's hashes.
70    pub target: usize,
71    /// Which of the source's hashes.
72    pub source: usize,
73    /// What became of the note.
74    pub op: ChangeOp,
75}
76
77/// A hasher for an alignment: music21's `StreamAligner.getDefaultHasher`,
78/// which hashes no offset and says what each hash was made from.
79pub fn default_hasher() -> Hasher {
80    Hasher {
81        hash_offset: false,
82        include_reference: true,
83        ..Hasher::default()
84    }
85}
86
87/// A matrix of the right size for an alignment, every cost nought:
88/// music21's `setupDistanceMatrix`.
89///
90/// # Errors
91///
92/// Either side with nothing hashed.
93pub fn setup_distance_matrix(target: usize, source: usize) -> Result<Vec<Vec<i64>>> {
94    if target == 0 {
95        return Err(Error::Analysis(
96            "Cannot perform alignment with empty target stream.".to_string(),
97        ));
98    }
99    if source == 0 {
100        return Err(Error::Analysis(
101            "Cannot perform alignment with empty source stream.".to_string(),
102        ));
103    }
104    Ok(vec![vec![0_i64; source + 1]; target + 1])
105}
106
107/// What it costs to put a note in that the source has not got: music21's
108/// `insertCost`, which is how many values the hash says.
109pub fn insert_cost(hash: &NoteHash) -> i64 {
110    hash.keys.len() as i64
111}
112
113/// What it costs to take a note out that the target has not got: music21's
114/// `deleteCost`, which is the same count.
115pub fn delete_cost(hash: &NoteHash) -> i64 {
116    hash.keys.len() as i64
117}
118
119/// How many of the values two hashes say alike: music21's
120/// `calculateNumSimilarities`.
121///
122/// The target's keys are what is counted over, each read off the source by
123/// name, as music21 reads it; a key the source has not got counts for
124/// nothing.
125pub fn num_similarities(target: &NoteHash, source: &NoteHash) -> usize {
126    target
127        .keys
128        .iter()
129        .zip(&target.values)
130        .filter(|(key, value)| value_of(source, key) == Some(*value))
131        .count()
132}
133
134/// Whether two hashes say the same of a note, whatever each was made from:
135/// music21's `tupleEqualityWithoutReference`.
136pub fn hashes_equal_without_reference(target: &NoteHash, source: &NoteHash) -> bool {
137    target
138        .keys
139        .iter()
140        .zip(&target.values)
141        .all(|(key, value)| value_of(source, key) == Some(value))
142}
143
144/// The value a hash says for a key, where it says one.
145fn value_of<'a>(hash: &'a NoteHash, key: &str) -> Option<&'a HashValue> {
146    let at = hash.keys.iter().position(|theirs| theirs == key)?;
147    hash.values.get(at)
148}
149
150/// What it costs to turn one note's hash into another's: music21's
151/// `substitutionCost` -- nothing where the two say the same, otherwise how
152/// many of the values differ.
153pub fn substitution_cost(target: &NoteHash, source: &NoteHash) -> i64 {
154    if hashes_equal_without_reference(target, source) {
155        return 0;
156    }
157    (target.keys.len() - num_similarities(target, source)) as i64
158}
159
160/// The costs of the three moves onto a cell -- up, left and diagonally --
161/// each nothing where that cell is off the matrix: music21's
162/// `getPossibleMovesFromLocation`.
163pub fn moves_from_location(matrix: &[Vec<i64>], i: usize, j: usize) -> [Option<i64>; 3] {
164    let at = |i: usize, j: usize| matrix.get(i).and_then(|row| row.get(j)).copied();
165    [
166        (i >= 1).then(|| at(i - 1, j)).flatten(),
167        (j >= 1).then(|| at(i, j - 1)).flatten(),
168        (i >= 1 && j >= 1).then(|| at(i - 1, j - 1)).flatten(),
169    ]
170}
171
172/// The change that leads to a cell: music21's `getOpFromLocation` -- none
173/// where the cost standing there is the cheapest move's, otherwise the
174/// cheapest move, up before left before diagonal.
175///
176/// # Errors
177///
178/// The origin, which nothing moves onto.
179pub fn op_from_location(matrix: &[Vec<i64>], i: usize, j: usize) -> Result<ChangeOp> {
180    let moves = moves_from_location(matrix, i, j);
181    let Some(up) = moves[0] else {
182        if moves[1].is_none() {
183            return Err(Error::Value(
184                "No movement possible from the origin".to_string(),
185            ));
186        }
187        return Ok(ChangeOp::Deletion);
188    };
189    let Some(left) = moves[1] else {
190        return Ok(ChangeOp::Insertion);
191    };
192    // Where the two above are costs, so is the diagonal: music21 compares
193    // all three, which a `None` among them would refuse to do.
194    let diagonal = moves[2].unwrap_or(i64::MAX);
195    let current = matrix
196        .get(i)
197        .and_then(|row| row.get(j))
198        .copied()
199        .unwrap_or(i64::MAX);
200    let (index, cheapest) =
201        [up, left, diagonal]
202            .iter()
203            .enumerate()
204            .fold((0, i64::MAX), |best, (index, cost)| {
205                if *cost < best.1 { (index, *cost) } else { best }
206            });
207    if current == cheapest {
208        Ok(ChangeOp::NoChange)
209    } else {
210        Ok(ChangeOp::from_index(index))
211    }
212}
213
214/// The cheapest edit from the target to the source read out of a matrix
215/// already filled, each change with the places of the two hashes it is
216/// between: the by-position twin of `calculateChangesList`.
217///
218/// # Errors
219///
220/// Either side with nothing hashed, or a matrix nothing can be traced
221/// through.
222pub fn change_places(
223    matrix: &[Vec<i64>],
224    target: usize,
225    source: usize,
226) -> Result<Vec<ChangePlace>> {
227    if target == 0 || source == 0 {
228        return Err(Error::Analysis(
229            "Cannot trace an alignment of an empty stream.".to_string(),
230        ));
231    }
232    // music21 reads the hash before the first as Python reads index -1:
233    // the last.
234    let before = |index: usize, count: usize| if index == 0 { count - 1 } else { index - 1 };
235    let (mut i, mut j) = (target, source);
236    let mut places = Vec::new();
237    while i != 0 || j != 0 {
238        let op = op_from_location(matrix, i, j)?;
239        places.push(ChangePlace {
240            target: before(i, target),
241            source: before(j, source),
242            op,
243        });
244        match op {
245            ChangeOp::Insertion => i -= 1,
246            ChangeOp::Deletion => j -= 1,
247            ChangeOp::Substitution | ChangeOp::NoChange => {
248                i -= 1;
249                j -= 1;
250            }
251        }
252    }
253    places.reverse();
254    Ok(places)
255}
256
257/// How much of an edit changes nothing: music21's `similarityScore`.
258pub fn similarity_score(places: &[ChangePlace]) -> FloatType {
259    let unchanged = places
260        .iter()
261        .filter(|place| place.op == ChangeOp::NoChange)
262        .count();
263    unchanged as FloatType / places.len() as FloatType
264}
265
266/// The cheapest edit onto every opening of the two, written into a matrix
267/// already set up: music21's `populateDistanceMatrix`.
268///
269/// Inserting and deleting both cost what the source's *first* hash says,
270/// which is music21's reading and not a cost per note.
271///
272/// # Errors
273///
274/// A source with nothing hashed, or a matrix not of the size
275/// [`setup_distance_matrix`] gives.
276pub fn fill_distance_matrix(
277    matrix: &mut [Vec<i64>],
278    target: &[NoteHash],
279    source: &[NoteHash],
280) -> Result<()> {
281    let (n, m) = (target.len(), source.len());
282    let Some(first) = source.first() else {
283        return Err(Error::Analysis(
284            "Cannot perform alignment with empty source stream.".to_string(),
285        ));
286    };
287    if matrix.len() != n + 1 || matrix.iter().any(|row| row.len() != m + 1) {
288        return Err(Error::Analysis(format!(
289            "A matrix of {} by {} cannot hold the alignment of {n} with {m}",
290            matrix.len(),
291            matrix.first().map_or(0, Vec::len)
292        )));
293    }
294    let insertion = insert_cost(first);
295    let deletion = delete_cost(first);
296    for i in 1..=n {
297        matrix[i][0] = matrix[i - 1][0] + insertion;
298    }
299    for j in 1..=m {
300        matrix[0][j] = matrix[0][j - 1] + deletion;
301    }
302    for i in 1..=n {
303        for j in 1..=m {
304            let substitution = substitution_cost(&target[i - 1], &source[j - 1]);
305            matrix[i][j] = (matrix[i - 1][j] + insertion)
306                .min(matrix[i][j - 1] + deletion)
307                .min(matrix[i - 1][j - 1] + substitution);
308        }
309    }
310    Ok(())
311}
312
313/// A matrix set up and filled in one: music21's `setupDistanceMatrix` and
314/// `populateDistanceMatrix` together.
315///
316/// # Errors
317///
318/// Either side with nothing hashed.
319pub fn populate_distance_matrix(target: &[NoteHash], source: &[NoteHash]) -> Result<Vec<Vec<i64>>> {
320    let mut matrix = setup_distance_matrix(target.len(), source.len())?;
321    fill_distance_matrix(&mut matrix, target, source)?;
322    Ok(matrix)
323}
324
325/// Two streams aligned by their notes' hashes, the cheapest edit from one to
326/// the other: music21's `StreamAligner`.
327///
328/// Inserting or deleting a note costs as many as the values in its hash, and
329/// changing one as many values as differ.
330#[derive(Clone, Debug)]
331pub struct StreamAligner {
332    /// How notes are hashed: by default by MIDI pitch and rounded length,
333    /// each with what it was made from.
334    pub hasher: Hasher,
335    /// The target's hashes.
336    pub hashed_target: Vec<NoteHash>,
337    /// The source's hashes.
338    pub hashed_source: Vec<NoteHash>,
339    /// The cost of the cheapest edit from each opening of the target to each
340    /// of the source.
341    pub distance_matrix: Vec<Vec<i64>>,
342    /// The changes, in order.
343    pub changes: Vec<Change>,
344    /// The share of the changes that change nothing.
345    pub similarity_score: FloatType,
346}
347
348impl Default for StreamAligner {
349    fn default() -> Self {
350        Self::new()
351    }
352}
353
354impl StreamAligner {
355    /// An aligner with music21's default hasher: pitch and length, each
356    /// hash with what it was made from.
357    pub fn new() -> Self {
358        Self::with_hasher(default_hasher())
359    }
360
361    /// An aligner hashing notes as this hasher does.
362    pub fn with_hasher(hasher: Hasher) -> Self {
363        Self {
364            hasher,
365            hashed_target: Vec::new(),
366            hashed_source: Vec::new(),
367            distance_matrix: Vec::new(),
368            changes: Vec::new(),
369            similarity_score: 0.0,
370        }
371    }
372
373    /// Aligns two streams: music21's `align`.
374    ///
375    /// # Errors
376    ///
377    /// A stream with nothing to hash, or a hash the hasher refuses.
378    pub fn align(&mut self, target: &Stream, source: &Stream) -> Result<()> {
379        let target = self.hasher.hash_stream(target)?;
380        let source = self.hasher.hash_stream(source)?;
381        self.align_hashed(target, source)
382    }
383
384    /// Aligns two lists of hashes already made: music21's `align` with
385    /// `preHashed`.
386    ///
387    /// # Errors
388    ///
389    /// An empty list.
390    pub fn align_hashed(&mut self, target: Vec<NoteHash>, source: Vec<NoteHash>) -> Result<()> {
391        if target.is_empty() {
392            return Err(Error::Analysis(
393                "Cannot perform alignment with empty target stream.".to_string(),
394            ));
395        }
396        if source.is_empty() {
397            return Err(Error::Analysis(
398                "Cannot perform alignment with empty source stream.".to_string(),
399            ));
400        }
401        self.hashed_target = target;
402        self.hashed_source = source;
403        self.populate_distance_matrix()?;
404        self.calculate_changes()
405    }
406
407    fn populate_distance_matrix(&mut self) -> Result<()> {
408        self.distance_matrix = populate_distance_matrix(&self.hashed_target, &self.hashed_source)?;
409        Ok(())
410    }
411
412    fn calculate_changes(&mut self) -> Result<()> {
413        let places = change_places(
414            &self.distance_matrix,
415            self.hashed_target.len(),
416            self.hashed_source.len(),
417        )?;
418        self.similarity_score = similarity_score(&places);
419        self.changes = places
420            .iter()
421            .map(|place| Change {
422                target: self.hashed_target[place.target].reference,
423                source: self.hashed_source[place.source].reference,
424                op: place.op,
425            })
426            .collect();
427        Ok(())
428    }
429
430    /// How many changes of each kind there are: music21's `changesCount`.
431    pub fn changes_count(&self, op: ChangeOp) -> usize {
432        self.changes.iter().filter(|change| change.op == op).count()
433    }
434}
435
436#[cfg(test)]
437mod tests {
438    use super::*;
439    use crate::note::Note;
440
441    fn line(names: &[&str]) -> Result<Stream> {
442        let mut stream = Stream::new();
443        for name in names {
444            stream.push(Note::from_name(name)?);
445        }
446        Ok(stream)
447    }
448
449    /// A line of notes, each as long as it is given.
450    fn lengths(names: &[(&str, FloatType)]) -> Result<Stream> {
451        let mut stream = Stream::new();
452        for (name, length) in names {
453            let mut note = Note::from_name(name)?;
454            note.set_duration(crate::duration::Duration::new(*length)?);
455            stream.push(note);
456        }
457        Ok(stream)
458    }
459
460    #[test]
461    fn the_matrix_is_filled_as_music21_fills_it() -> Result<()> {
462        // music21's own `populateDistanceMatrix` examples.
463        let hasher = default_hasher();
464        let filled = |target: &Stream, source: &Stream| -> Result<Vec<Vec<i64>>> {
465            populate_distance_matrix(&hasher.hash_stream(target)?, &hasher.hash_stream(source)?)
466        };
467        let two = line(&["C#4", "C4"])?;
468        assert_eq!(
469            filled(&two, &two)?,
470            vec![vec![0, 2, 4], vec![2, 0, 2], vec![4, 2, 0]]
471        );
472        assert_eq!(
473            filled(&two, &line(&["C#4"])?)?,
474            vec![vec![0, 2], vec![2, 0], vec![4, 2]]
475        );
476        assert_eq!(
477            filled(
478                &line(&["C#4", "C4", "E3"])?,
479                &lengths(&[("D5", 3.0), ("C#4", 1.0), ("E3", 1.0)])?,
480            )?,
481            vec![
482                vec![0, 2, 4, 6],
483                vec![2, 2, 2, 4],
484                vec![4, 4, 3, 3],
485                vec![6, 6, 5, 3],
486            ]
487        );
488        Ok(())
489    }
490
491    #[test]
492    fn a_cell_says_which_moves_lead_onto_it() -> Result<()> {
493        // music21 writes its own product table into the matrix and reads
494        // the moves back off it.
495        let matrix: Vec<Vec<i64>> = (0..=4).map(|i| (0..=3).map(|j| i * j).collect()).collect();
496        assert_eq!(moves_from_location(&matrix, 0, 0), [None, None, None]);
497        assert_eq!(
498            moves_from_location(&matrix, 1, 1),
499            [Some(0), Some(0), Some(0)]
500        );
501        assert_eq!(
502            moves_from_location(&matrix, 4, 3),
503            [Some(9), Some(8), Some(6)]
504        );
505        assert_eq!(
506            moves_from_location(&matrix, 2, 2),
507            [Some(2), Some(2), Some(1)]
508        );
509        assert_eq!(moves_from_location(&matrix, 0, 2), [None, Some(0), None]);
510        assert_eq!(moves_from_location(&matrix, 3, 0), [Some(0), None, None]);
511        assert!(op_from_location(&matrix, 0, 0).is_err());
512        Ok(())
513    }
514
515    #[test]
516    fn a_cell_says_what_change_leads_onto_it() -> Result<()> {
517        // music21's own `getOpFromLocation` example, on the matrix its
518        // four-note target and three-note source fill.
519        let hasher = default_hasher();
520        let mut matrix = populate_distance_matrix(
521            &hasher.hash_stream(&line(&["C4", "D4", "C4", "E4"])?)?,
522            &hasher.hash_stream(&line(&["C4", "D4", "C4"])?)?,
523        )?;
524        assert_eq!(
525            matrix,
526            vec![
527                vec![0, 2, 4, 6],
528                vec![2, 0, 2, 4],
529                vec![4, 2, 0, 2],
530                vec![6, 4, 2, 0],
531                vec![8, 6, 4, 2],
532            ]
533        );
534        assert_eq!(op_from_location(&matrix, 4, 3)?, ChangeOp::Insertion);
535        assert_eq!(op_from_location(&matrix, 2, 2)?, ChangeOp::NoChange);
536        assert_eq!(op_from_location(&matrix, 0, 2)?, ChangeOp::Deletion);
537        matrix[0][0] = 1;
538        assert_eq!(op_from_location(&matrix, 1, 1)?, ChangeOp::Substitution);
539        Ok(())
540    }
541
542    #[test]
543    fn two_hashes_are_compared_as_music21_compares_them() -> Result<()> {
544        // music21's own `substitutionCost` examples: the same note, a
545        // note of another pitch, and a note of another pitch and length.
546        let hasher = default_hasher();
547        let one =
548            |stream: &Stream| -> Result<NoteHash> { Ok(hasher.hash_stream(stream)?.remove(0)) };
549        let c4 = one(&line(&["C4"])?)?;
550        let same = one(&line(&["C4"])?)?;
551        assert!(hashes_equal_without_reference(&c4, &same));
552        assert_eq!(num_similarities(&c4, &same), 2);
553        assert_eq!(substitution_cost(&c4, &same), 0);
554        let d4 = one(&line(&["D4"])?)?;
555        assert!(!hashes_equal_without_reference(&c4, &d4));
556        assert_eq!(num_similarities(&c4, &d4), 1);
557        assert_eq!(substitution_cost(&c4, &d4), 1);
558        let e4 = one(&line(&["E4"])?)?;
559        let e_sharp = one(&lengths(&[("E#4", 2.0)])?)?;
560        assert_eq!(num_similarities(&e4, &e_sharp), 0);
561        assert_eq!(substitution_cost(&e4, &e_sharp), 2);
562        assert_eq!(insert_cost(&c4), 2);
563        assert_eq!(delete_cost(&c4), 2);
564        Ok(())
565    }
566
567    #[test]
568    fn a_change_says_which_hashes_it_is_between() -> Result<()> {
569        // Every change music21 lists is between one hash of each side,
570        // and the twin says which.
571        let mut aligner = StreamAligner::new();
572        let target = line(&["C4", "D4", "E4", "F4"])?;
573        let source = line(&["C4", "D4", "E4"])?;
574        aligner.align(&target, &source)?;
575        let places = change_places(
576            &aligner.distance_matrix,
577            aligner.hashed_target.len(),
578            aligner.hashed_source.len(),
579        )?;
580        assert_eq!(places.len(), aligner.changes.len());
581        for (place, change) in places.iter().zip(&aligner.changes) {
582            assert_eq!(place.op, change.op);
583            assert_eq!(aligner.hashed_target[place.target].reference, change.target);
584            assert_eq!(aligner.hashed_source[place.source].reference, change.source);
585        }
586        assert!((similarity_score(&places) - 0.75).abs() < 1e-12);
587        Ok(())
588    }
589
590    #[test]
591    fn streams_are_aligned_as_music21_aligns_them() -> Result<()> {
592        // music21's own tests.
593        let mut aligner = StreamAligner::new();
594        aligner.align(&line(&["C4", "D#4", "C4"])?, &line(&["C4", "D-4", "C4"])?)?;
595        assert!((aligner.similarity_score - 2.0 / 3.0).abs() < 1e-12);
596        let mut aligner = StreamAligner::new();
597        aligner.align(
598            &line(&["C4", "D4", "E4", "F4"])?,
599            &line(&["C4", "D4", "E4"])?,
600        )?;
601        assert!((aligner.similarity_score - 0.75).abs() < 1e-12);
602        Ok(())
603    }
604}
music21/alpha/analysis/aligner.rs

music21/alpha/analysis/
aligner.rs
