基于旋律的音乐检索系统设计与实现(14)
5.3 基于距离校正的算法
输入旋律与数据库音乐的相似性可以用相关度来描述。相关度的含义是:通过对哼唱音乐进行若干次音符插入、音符删除和音符替换操作，使其与数据库音乐的某个片段右对齐匹配。此时所需要的最少操作次数被定义为二者的相关度。
本文采用了一种基于校正距离矩阵的相关度计算方法。假定哼唱音乐长度为M数据库音乐长度为N，则校正距离矩阵E的大小为M xN 。矩阵中每个元素
E(i,j)的含义是:哼唱音乐前i个字符与数据库音乐前j个字符右对齐匹配时，所需要的最少操作次数。计算方法如下:
(1)第一行元素E[l, j ] (1≤ j ≤N)的计算。如果哼唱音乐序列的第一个字符b1与数据库音乐序列的第J个字符aj相同，则不需要任何操作即可完成右对齐匹配，即E(1,j)=0;否则需要一次替换操作将b1替换成aj，才能完成右对齐匹配，即E[l, j]=1
第一列元素E(i,l)(1 ≤i ≤ M)的计算此时的哼唱音乐比数据库音乐多i-1个字符，因此必须对哼唱音乐序列进行i-1次删除操作，即将b1, b2删除。如果剩下的一个字符bi与数据库音乐序列的第一个字符a1相同，则完成右对齐匹配，即E[i,l] = i -1;否则还需要一次替换操作将b;替换成。n‘能完成右对齐匹配，即E[i,l] = (i-1)+1=i。
在矩阵边缘初始化之后，需要对矩阵内部元素E[i, j ] ( i，j均不等于1)进行计算可以通过相邻元素E[i -1, j] " E[i, j-1] , E[i-1, j-1]分别计算出E[i,j]月的可能取值，并 将三个可能值中的最小值作为E[i,月的值(因为最小值意着最少的操作次数)。具体方法如下:
通过E[i -1，j]的计算:E[i,j]与E[i -1, j]相比，仅仅是在哼唱音乐序列的最后多增加了一个字符而已，如图4. 10所示。因此只需将哼唱音乐多出的一个字符瓦删除即可，即E[i, j ]=E[i-1, j]+1。E[i j ]与E[i,j -1]相比，仅仅是在数据库音乐序列的最后多增加了一个字符。i而己，如图4.11所示。因此只需在哼唱音乐序列后面插入一个“i即可完成右对齐匹配，即E[i, j]=E[i, j-1]+l.
通过E[i - 1,j -1]计算:E[i,j]与E[i -1, j -1]相比，只是在哼唱音乐序列和数据库音乐序列的最后分别增加了一个字符。如果最后增加的这两个字符相同，则E[i,j]= E[i -1, j -1];否则需要一次替换操作才能完成右对齐匹配，即E[i, j]=E[i-1, j-1]+1。
最后，取E[i-1, j ] + 1 , E[i, j-1] + 1 , E[i-1, j-1] + sij若bj=aj，则Sij=0:否
则，Sij=1三者中的最小值作为E[i, j ]的值即可。
5.4 相关度的计算
如果哼唱音乐长度为M，数据库音乐长度为N，则校正距离矩阵E的大小为M xN。其中最后一行元素E[M,j](1≤j≤N)的含义可以解释为哼唱音乐整个序列与数据库音乐前j个字符所组成的片段右对齐匹配时，所需要的最少操作次数。随着j的不断增加，数据库音乐片段也在不断增长。针对J的所有可能取值，E[M,j](1≤j≤N)中的最小值即为哼唱音乐与数据库音乐的相关度。由于音乐的特征序列有两个，分别是音高差序列和音长比序列。因此，我们在实际中分别计算两个序列的相关度，并将结果相加后作为最终的相关度。
5.5 本章小结
本章着重介绍了字符串的匹配算法，简要的介绍了精确匹配算法然后较为重点的描述了几种模糊匹配的具体计算方法。最后本论文采用了一种距离校正的算法，可以很好地克服前面介绍的一些算法的缺点，而他本身也并不十分的复杂。