ASP.net基于内容的音乐检索方法研究(7)
时间:2017-04-13 10:38 来源:毕业论文 作者:毕业论文 点击:次
BM算法需要预处理．也需要辅助空问．逻辑上也相对比较复杂。但是整个算法执行的效率相对较高。如果字符越多，效率越高。因此BM算法在汉字文本串匹配效率要高于英文文本串的匹配。 3.2.4 BMH算法 它是对BM算法的改进，思想是通过目标串和模式串中字符的最后一个位置对应字符的下一个字符来决定右移的字符个数。算法描述如下： (1)模式串从左向右移动，匹配自右向左进行； (2)若匹配失败发生在Pj≠Ti：，先根据BM算法计算出字符Ti的位移量，再比较下一个字符：如果下一个字符出现在模式串中，则移动的距离通过模式串决定。否则，跳过该字符从下一个字符开始重新比较。依次循环，直到匹配为止。 可以看出，该算法的最坏情况即为BM算法的情况，即右移的字符个数N>=dist[t]，故相对BM算法具有一定的优越性。 BMH算法预处理时间复杂度为O(m+o)，空间复杂度先0(o)，o是与Pattern、Text相关的有限字符集长度。查找阶段时间复杂度为O(mn)，在一般情况下，BMH算法比BM有更好的性能，它只使用了一个数组，简化了初始化过程。 3.2.5 AC算法 1975年，贝尔实验室的Alfred V．Aho和Margaret J．Corasick提出了著名的多模式匹配算法一一AC自动机匹配算法(简称AC算法)。该算法最早被使用在图书馆的书目查询程序中，取得了很好的效果。 AC算法描述（例如模式集SP={he，she，his，hers}）： 预处理阶段，模式树的各个节点作为状态，根节点作为初态，标签为模式的节点作为终态，利用转向函数g和失效函数f作为转移函数，将模式树扩展成一个树型有限自动机。见图3-1 由模式树扩展所得的AC自动机M是1个6元组：M= (Q，Σ，g，f，qo，F)其中： (1)Q是有限状态集(模式树上的节点)； (2)Σ是有穷的输入字符表(数据包中可能出现的所有字符)； (3)g是转移函数，该函数定义如下：g(S，a)：从当前状态S开始，沿着边上标签为a的路径所到的状态。假如(U，v)边上的标签为a，那么g(U，a)=v；如果根节点上出来的边上的标签没有a，则g(0，a)=O，即如果没有匹配的字符出现，自动机停留在初态； (4)f(不匹配时自动机的状态转移)也是转移函数，该函数定义如下：f(S)：当w是L(s)最长真后缀并且W是某个模式的前缀，那么f(S)就是以W为标签的那个节点； (5)qo∈Q是初态(根节点，标识符为0)； (6)F量Q是终态集(以模式为标签的节点集)。 这样，在文本字符串中查找模式字符串的过程转化成在模式树中的查找过程。查找一个文本字符串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走：若自动机能够抵达终态v，则说明T中存在模式L(v)：否则不存在模式。 图3.2.1 模式树 AC算法模式匹配的时间复杂度是O(n)，并且与模式集中模式字符串的个数和每个模式字符串的长度无关。无论模式字符串P是否出现在文本字符串T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是0(n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式字符串的长度总和。AC算法的查找效率明显高于BM算法。但是，AC算法在对文本字符串匹配的过程中没有跳跃，无法跳过不必要的比较，并且有限状态自动机算法是以空间换时间的经典算法，当模式集较大时可能产生内存膨胀问题。因此在实际的匹配过程中，AC算法不可能是性能最佳的搜索算法。 3.2.6 AC-BM算法 AC-BM算法是在Aho．Corasick算法的基础上，结合Boyer．Moore算法的跳跃思想，产生的一种多模式匹配算法。在一般情况下，由于应用了BM算法的跳跃式思文，所以不需要对文本的每个字符进行匹配。在BM算法的基础上引入了AC算法，来提高匹配速度，跳过尽可能多的字符，在模式字符串较长和较短的情况下，该算法都具有很好的性能。 (责任编辑：qin) |