music21_rs/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, 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/// Two streams aligned by their notes' hashes, the cheapest edit from one to
61/// the other: music21's `StreamAligner`.
62///
63/// Inserting or deleting a note costs as many as the values in its hash, and
64/// changing one as many values as differ.
65#[derive(Clone, Debug)]
66pub struct StreamAligner {
67    /// How notes are hashed: by default by MIDI pitch and rounded length,
68    /// each with what it was made from.
69    pub hasher: Hasher,
70    /// The target's hashes.
71    pub hashed_target: Vec<NoteHash>,
72    /// The source's hashes.
73    pub hashed_source: Vec<NoteHash>,
74    /// The cost of the cheapest edit from each opening of the target to each
75    /// of the source.
76    pub distance_matrix: Vec<Vec<i64>>,
77    /// The changes, in order.
78    pub changes: Vec<Change>,
79    /// The share of the changes that change nothing.
80    pub similarity_score: FloatType,
81}
82
83impl Default for StreamAligner {
84    fn default() -> Self {
85        Self::new()
86    }
87}
88
89impl StreamAligner {
90    /// An aligner with music21's default hasher: pitch and length, each
91    /// hash with what it was made from.
92    pub fn new() -> Self {
93        Self::with_hasher(Hasher {
94            hash_offset: false,
95            include_reference: true,
96            ..Hasher::default()
97        })
98    }
99
100    /// An aligner hashing notes as this hasher does.
101    pub fn with_hasher(hasher: Hasher) -> Self {
102        Self {
103            hasher,
104            hashed_target: Vec::new(),
105            hashed_source: Vec::new(),
106            distance_matrix: Vec::new(),
107            changes: Vec::new(),
108            similarity_score: 0.0,
109        }
110    }
111
112    /// Aligns two streams: music21's `align`.
113    ///
114    /// # Errors
115    ///
116    /// A stream with nothing to hash, or a hash the hasher refuses.
117    pub fn align(&mut self, target: &Stream, source: &Stream) -> Result<()> {
118        let target = self.hasher.hash_stream(target)?;
119        let source = self.hasher.hash_stream(source)?;
120        self.align_hashed(target, source)
121    }
122
123    /// Aligns two lists of hashes already made: music21's `align` with
124    /// `preHashed`.
125    ///
126    /// # Errors
127    ///
128    /// An empty list.
129    pub fn align_hashed(&mut self, target: Vec<NoteHash>, source: Vec<NoteHash>) -> Result<()> {
130        if target.is_empty() {
131            return Err(Error::Analysis(
132                "Cannot perform alignment with empty target stream.".to_string(),
133            ));
134        }
135        if source.is_empty() {
136            return Err(Error::Analysis(
137                "Cannot perform alignment with empty source stream.".to_string(),
138            ));
139        }
140        self.hashed_target = target;
141        self.hashed_source = source;
142        self.populate_distance_matrix();
143        self.calculate_changes()
144    }
145
146    fn populate_distance_matrix(&mut self) {
147        let (n, m) = (self.hashed_target.len(), self.hashed_source.len());
148        // music21 costs every insertion and deletion as the source's first
149        // hash does.
150        let cost = self.hashed_source[0].keys.len() as i64;
151        let mut matrix = vec![vec![0_i64; m + 1]; n + 1];
152        for i in 1..=n {
153            matrix[i][0] = matrix[i - 1][0] + cost;
154        }
155        for j in 1..=m {
156            matrix[0][j] = matrix[0][j - 1] + cost;
157        }
158        for i in 1..=n {
159            for j in 1..=m {
160                let substitution =
161                    substitution_cost(&self.hashed_target[i - 1], &self.hashed_source[j - 1]);
162                matrix[i][j] = (matrix[i - 1][j] + cost)
163                    .min(matrix[i][j - 1] + cost)
164                    .min(matrix[i - 1][j - 1] + substitution);
165            }
166        }
167        self.distance_matrix = matrix;
168    }
169
170    /// The change that leads to a place of the matrix, as music21 reads it
171    /// back: none where the cost is the cheapest neighbour's, otherwise the
172    /// cheapest, up before left before diagonal.
173    fn op_at(&self, i: usize, j: usize) -> Result<ChangeOp> {
174        let matrix = &self.distance_matrix;
175        let up = (i >= 1).then(|| matrix[i - 1][j]);
176        let left = (j >= 1).then(|| matrix[i][j - 1]);
177        let diagonal = (i >= 1 && j >= 1).then(|| matrix[i - 1][j - 1]);
178        let Some(up) = up else {
179            if left.is_none() {
180                return Err(Error::Analysis(
181                    "No movement possible from the origin".to_string(),
182                ));
183            }
184            return Ok(ChangeOp::Deletion);
185        };
186        let Some(left) = left else {
187            return Ok(ChangeOp::Insertion);
188        };
189        let diagonal = diagonal.unwrap_or(i64::MAX);
190        let moves = [up, left, diagonal];
191        let (index, cheapest) =
192            moves
193                .iter()
194                .enumerate()
195                .fold((0, i64::MAX), |best, (index, cost)| {
196                    if *cost < best.1 { (index, *cost) } else { best }
197                });
198        if matrix[i][j] == cheapest {
199            Ok(ChangeOp::NoChange)
200        } else {
201            Ok(ChangeOp::from_index(index))
202        }
203    }
204
205    fn calculate_changes(&mut self) -> Result<()> {
206        let (mut i, mut j) = (self.hashed_target.len(), self.hashed_source.len());
207        let (n, m) = (i, j);
208        // music21 reads the note before the first as Python reads index -1:
209        // the last.
210        let before = |index: usize, count: usize| if index == 0 { count - 1 } else { index - 1 };
211        let mut changes = Vec::new();
212        while i != 0 || j != 0 {
213            let op = self.op_at(i, j)?;
214            changes.push(Change {
215                target: self.hashed_target[before(i, n)].reference,
216                source: self.hashed_source[before(j, m)].reference,
217                op,
218            });
219            match op {
220                ChangeOp::Insertion => i -= 1,
221                ChangeOp::Deletion => j -= 1,
222                ChangeOp::Substitution | ChangeOp::NoChange => {
223                    i -= 1;
224                    j -= 1;
225                }
226            }
227        }
228        changes.reverse();
229        let unchanged = changes
230            .iter()
231            .filter(|change| change.op == ChangeOp::NoChange)
232            .count();
233        self.similarity_score = unchanged as FloatType / changes.len() as FloatType;
234        self.changes = changes;
235        Ok(())
236    }
237
238    /// How many changes of each kind there are: music21's `changesCount`.
239    pub fn changes_count(&self, op: ChangeOp) -> usize {
240        self.changes.iter().filter(|change| change.op == op).count()
241    }
242}
243
244/// What it costs to turn one note's hash into another's: nothing if they
245/// are the same, otherwise how many of their values differ.
246fn substitution_cost(target: &NoteHash, source: &NoteHash) -> i64 {
247    let same = target
248        .values
249        .iter()
250        .zip(&source.values)
251        .filter(|(a, b)| a == b)
252        .count();
253    if same == target.values.len() && target.values.len() == source.values.len() {
254        return 0;
255    }
256    (target.keys.len() - same) as i64
257}
258
259#[cfg(test)]
260mod tests {
261    use super::*;
262    use crate::note::Note;
263
264    fn line(names: &[&str]) -> Result<Stream> {
265        let mut stream = Stream::new();
266        for name in names {
267            stream.push(Note::from_name(name)?);
268        }
269        Ok(stream)
270    }
271
272    #[test]
273    fn streams_are_aligned_as_music21_aligns_them() -> Result<()> {
274        // music21's own tests.
275        let mut aligner = StreamAligner::new();
276        aligner.align(&line(&["C4", "D#4", "C4"])?, &line(&["C4", "D-4", "C4"])?)?;
277        assert!((aligner.similarity_score - 2.0 / 3.0).abs() < 1e-12);
278        let mut aligner = StreamAligner::new();
279        aligner.align(
280            &line(&["C4", "D4", "E4", "F4"])?,
281            &line(&["C4", "D4", "E4"])?,
282        )?;
283        assert!((aligner.similarity_score - 0.75).abs() < 1e-12);
284        Ok(())
285    }
286}
music21_rs/alpha/analysis/aligner.rs

music21_rs/alpha/analysis/
aligner.rs
