表5.2   模式串的推移
0    1    2    3    4    5    6    7    8    9    10    11    12    13
R    U    D    D    R    U    R    R    D    R    D    D    D    D
R    R    D    R    D    D                                
                        R    R    D    R    D    D    
                            
另外一种情况是，假定模式串为RURRDR，同样在位置5匹配失败。由于事先己知模式串中只有一个U，要想匹配成功，这个U只能与字符串中的位置5对齐，于是可以直接将模式串推到这个位置，再继续进行后面的比较，如图5.3所示。以上为BM算法的核心。
表5.3  模式串推移的第二种情况
0    1    2    3    4    5    6    7    8    9    10    11    12    13
R    U    D    D    R    U    R    R    D    R    D    D    D    D
R    U    R    R    D    R                                
                R    U    U    R    R    D    R
5.2.2 模糊匹配检索
    在音乐旋律检索中仅仅使用精确匹配是不够的，因为许多音乐的演奏形式是经常变化的，比如民族音乐在演奏时就会有许多变体，流行音乐的变化就更多了。同时，用户前端的输入并不能保证完全准确，肯定有许多不正确的地方，所以模糊匹配检索具有其特殊的重要性。
    一个合适的模糊匹配算法，对于音乐旋律检索的效率和结果来说是非常关键的。字符串模糊匹配的原理简单来说就是给定两个字符串，如何找到一个最经济的操作序列，使得一个字符串可以转换为另一个字符串。其中，基本的操作是插入、删除和替换。
   在一个具体的应用中，当完成从一个字符串到另一个字符串的转换时，所需要的最少操作次数被定义为二者的距离，在检索时设定一个范围，距离在此范围内的就命中，当然，根据实际的需要，各个操作还可以被赋予不同的权值，以代表各种操作可能出现的概率。
    模糊匹配算法中最经典的是RA Wagner和MJ Fischer的近似匹配算法。近几年来，针对不同长度字符串、匹配时允许出现的操作数目的多少等问题，陆续有不少相应的算法被提出，如:WM, BYP, UKK, Chang和WMM等。 基于旋律的音乐检索系统设计与实现(13):http://www.youerw.com/tongxin/lunwen_2379.html