Source Code for Module jazzparser.data.db_mirrors.distance

 1  """Edit distance between chord sequences. 
 2   
 3  """ 
 4  """ 
 5  ============================== License ======================================== 
 6   Copyright (C) 2008, 2010-12 University of Edinburgh, Mark Granroth-Wilding 
 7    
 8   This file is part of The Jazz Parser. 
 9    
10   The Jazz Parser is free software: you can redistribute it and/or modify 
11   it under the terms of the GNU General Public License as published by 
12   the Free Software Foundation, either version 3 of the License, or 
13   (at your option) any later version. 
14    
15   The Jazz Parser is distributed in the hope that it will be useful, 
16   but WITHOUT ANY WARRANTY; without even the implied warranty of 
17   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
18   GNU General Public License for more details. 
19    
20   You should have received a copy of the GNU General Public License 
21   along with The Jazz Parser.  If not, see <http://www.gnu.org/licenses/>. 
22   
23  ============================ End license ====================================== 
24   
25  """ 
26  __author__ = "Mark Granroth-Wilding <mark.granroth-wilding@ed.ac.uk>"  
27   
28  from jazzparser.utils.distance import levenshtein_distance, align 
29   
30 -def chord_sequence_match_score(seq1, seq2): 
31      """ 
32      Computes the edit distance between two chord sequences to score the  
33      extent of the matching between the two sequences between 0 and 1. 
34       
35      Each sequence should be a list of L{jazzparser.data.db_mirrors.Chord}s. 
36      The metric is key-independent. The distance will be tried for every  
37      transposition of one of the sequences and the closest match will be  
38      used. 
39       
40      """ 
41      costs = [] 
42      for transpose in range(12): 
43          # Give a half-point to alignments of roots without labels or vice versa 
44          def _subst_cost(crd1, crd2): 
45              cost = 0 
46              if (crd1.root+transpose) % 12 == crd2.root: 
47                  cost += -1 
48              if crd1.type == crd2.type: 
49                  cost += -1 
50              return cost 
51           
52          # Try aligning the two sequences 
53          align_cost = levenshtein_distance(seq1, seq2,  
54                                            delins_cost=0,  
55                                            subst_cost_fun=_subst_cost) 
56          costs.append((transpose,align_cost)) 
57       
58      transposition, align_cost = min(costs, key=lambda x:x[1]) 
59      align_score = float(-align_cost) / 2 
60       
61      # Compute f-score of optimal alignment 
62      precision = align_score / len(seq1) 
63      recall = align_score / len(seq2) 
64      f_score = 2.0 * precision * recall / (precision+recall) 
65       
66      return f_score,transposition 
67   
68 -def chord_sequence_alignment(seq1, seq2, transposition=0): 
69      """ 
70      Performs the same alignment as L{chord_sequence_match_score}, but  
71      returns the actual alignment of chords. 
72       
73      The alignment assumes that the first sequence is transposed by  
74      C{transposition}. 
75       
76      """ 
77      # Give a half-point to alignments of roots without labels or vice versa 
78      def _subst_cost(crd1, crd2): 
79          cost = 0 
80          if (crd1.root+transposition) % 12 == crd2.root: 
81              cost += -1 
82          if crd1.type == crd2.type: 
83              cost += -1 
84          return cost 
85       
86      # Try aligning the two sequences 
87      alignment = align(seq1, seq2, delins_cost=0, subst_cost=_subst_cost) 
88       
89      return alignment 
90