（3）在旋律检索中，经常把旋律的某些特征参数用字符表示，从而把特征参数的匹配转变为字符串的匹配。字符串的匹配有两类，分别是:字符串的精确匹配和模糊匹配。先将用户的音频输入提取短时能量、然后进行音符切分、从而做基音周期检测，然后提取出每个音符的音高，将哼唱信号转换成顺序的音符序列。然后采用串匹配算法和音乐库中的已知旋律特征匹配，最后提交相似检索结果列表。
5.2 字符串匹配算法
字符串匹配是最早的旋律匹配算法，也是当前应用比较广泛的算法；将近似字符串匹配算法应用到旋律匹配中，其核心思想就是通过比较两个音乐符号串来计算旋律的近似程度；普遍的做法就是将乐谱上的每一个音符，表示成为计算机中的一个抽象的符号，然后采用近似字符串比较算法比较两个符号串，从而评估两段旋律的匹配程度。旋律编码成字符串可以由很多形式，目前许多研究仍是沿用由Ghias[1]最早提出的音频等高线的方法。求出音符的音高后，利用音符之间的因高差，构建相对音高符号序列。在Ghias[1]的研究中，采用了将音高等级分为三个层次。音高差被分为3个等次，使用UDS分别表示三个层次。S表示两个音符间的音符差小于一定的值；若音高差大于设定的阈值，则分别用D和U表示。
5.2.1 精确匹配检索
字符串的精确匹配已经被充分研究，它是字符串匹配的基础。目的是设法确定在一个字符串里是否包含另一个字符串(被包含的字符串称为模式)。如果包含关系成立，则称两个字符串匹配;否则称为不匹配。下面是三种常用的精确匹配检索方法:
   (1)简单字符串匹配
    这是最直观、最容易想到的算法。在给定字符串和模式之后，简单的把模式放在字符串的各个位置进行匹配试验，每次顺序比较模式和字符串的对应字符，如果所有的字符都相同，就说明发现了一个匹配。
  (2)Knuth-Morris_ Pratt(KMP)算法
    简单字符串匹配算法的效率比较低，因为在一次比较失败后，只是简单的把模式串的位置向后移动一个字符的位置。这样做就完全丢掉了前面已经做过的字符匹配中所得到的信息，而这些匹配信息实际上是可以利用的。
假设一个要匹配的旋律模式串的形式为UDRRUDRDD，可以注意到出现在前面的UDR在后面的部分又重复出现了，如表5.1所示：
表5.1  重复的情况
0    1    2    3    4    5    6    7    8
U    D    R    R    U    D    R    D    D    
    模式串前面的连续片段“UDR”称为模式前缀，模式前缀在模式串后面重复出现的清况可以用来避免重复进行已经做过的检查。
    假如被匹配的旋律字符串为RUDRRUDRRUDRDD，匹配的位置从1开始，如图4.3
所示。匹配在进行到位置8时失败，因为已经知道模式串从位置4到6的字符与位置0到2的字符相同，所以就可以把模式串直接向后推一段而不是一个字符，从位置8开始比较。这样可以避免许多重复的比较，而且可能一次把模式串向右移动多个位置，而不是一个位置。
(3) Boyer-Moore(BM)算法
通常认为，在字符串的匹配过程中，每个字符都应该检查。但实际情况并非如此。考虑一种从右到左的比较方式，假如被匹配的旋律字符串为RUDRRURRDRDDDD，要匹配的旋律模式串为RRDRDD。首先比较位置5，匹配失败，由此可以知道从位置0到位置5，模式串与字符串是不匹配的。字符串在位置5处的字符是U，因为事先已知模式串中没有U，于是可以直接把模式串推到位置6，中间的字符不必再作检查，如表5.2所示： 基于旋律的音乐检索系统设计与实现(12):http://www.751com.cn/tongxin/lunwen_2379.html